Pour déterminer la position de départ donc, la première idée consiste à chercher l'intersection de deux trajectoires corrigées. Une intersection de droites donc. Sauf que c'est assez moche à calculer, on peut faire plus élégant.
Les trajectoires corrigées étant toutes sécantes au même point, celui qu'on recherche, en les prenant deux par deux on peut définir des plans. Il est temps d'ouvrir une petite parenthèse.
Plan défini par deux droites
Dans l'espace, deux droites peuvent définir un plan, à condition nécessaire et suffisante qu'elles soient soit parallèles mais non identiques, soit sécantes.
Soient deux droites pertinentes selon cette condition et définies chacune par un point et par un vecteur (p0, v0) et (p1, v1). On cherche à caractériser leur plan commun, par un point et un vecteur normal.
Si elles ne sont pas parallèles, leurs vecteurs directeurs v0 et v1 ne sont pas colinéaires. Leur produit vectoriel n = v0 ^ v1 est non nul et orthogonal aux deux droites et fait donc un très bon vecteur normal pour le plan cherché.
Si elles sont parallèles leurs vecteurs directeurs sont certes colinéraires, mais p0 - p1 n'est pas colinéaire à ces derniers (sinon, vous pouvez vérifier, les droites seraient identiques). On peut donc choisir n = v0 ^ (p0 - p1) comme vecteur normal pour le plan cherché.
Il nous reste à trouver un point sur le plan cherché : c'est trivial, il suffit de prendre par exemple p0 puisque ce plan contient par définition la première droite. Pour obtenir une équation de plan du type n ⋅ r = d, il suffit de prendre d = p0 ⋅ n.
En fait, nous nous intéressons seulement au cas de droites sécantes, voici donc le calcul pour obtenir l'équation du plan dans ce cas spécifique :
n = v0 ^ v1
d = p0 ⋅ n
n ⋅ r = d
Retour au problème
En prenant les trajectoires corrigées deux par deux, on peut définir un tas de plans contenant tous le point cherché. Or l'intersection de trois plans non parallèles est un point, qui sera forcément ce dernier ! Ouvrons une nouvelle parenthèse.
Intersection de plans
Allons-y pour l'intersection de trois plan non parallèles (p0, d0), (p1, d1) et (p2, d2).
Le point d'intersection, que nous allons noter r, respecte les équation des trois plans :
n0 ⋅ r = d0
n1 ⋅ r = d1
n2 ⋅ r = d2
L'astuce consiste ici à choisir une base vectorielle alternative :
u0 = n1 ^ n2
u1 = n2 ^ n0
u2 = n0 ^ n1
En exprimant la position cherchée comme combinaison de ces trois vecteurs r = a0 u 0 + a1 u1 + a2 u2, l'équation du premier plan devient :
On peut reconnaître ici le produit mixte de nos trois vecteurs normaux, un scalaire que l'on va noter U = n0 ⋅ (n1 ^ n2). Les trois équations deviennent de la même façon :
a0 U = d0
a1 U = d1
a2 U = d2
Ce qui nous donne finalement ces fameux coefficients :
a0 = d0 / U
a1 = d1 / U
a2 = d2 / U
Qui nous donnent donc le vecteur position de l'intersection de nos trois plans. Pour rappel, voici les calculs à effectuer à partir des constantes définissant les trois plans :
u0 = n1 ^ n2
u1 = n2 ^ n0
u2 = n0 ^ n1
U = n0 ⋅ (n1 ^ n2)
a0 = d0 / U
a1 = d1 / U
a2 = d2 / U
r = a0 u0 + a1 u1 + a2 u2
Re-retour au problème
En prenant trois trajectoires corrigées (p0, v0 - v), (p1, v1 - v) et (p2, v2 - v) , on sait désormais caractériser leurs plans communs deux à deux, soit trois plan. Et on sait également déterminer l'intersection de ces trois plan. Problème résolu !
[^] # Re: Géométrie vectorielle et analytique
Posté par 🚲 Tanguy Ortolo (site web personnel) . En réponse au message Advent of Code 2023, jour 24. Évalué à 3.
Pour déterminer la position de départ donc, la première idée consiste à chercher l'intersection de deux trajectoires corrigées. Une intersection de droites donc. Sauf que c'est assez moche à calculer, on peut faire plus élégant.
Les trajectoires corrigées étant toutes sécantes au même point, celui qu'on recherche, en les prenant deux par deux on peut définir des plans. Il est temps d'ouvrir une petite parenthèse.
Plan défini par deux droites
Dans l'espace, deux droites peuvent définir un plan, à condition nécessaire et suffisante qu'elles soient soit parallèles mais non identiques, soit sécantes.
Soient deux droites pertinentes selon cette condition et définies chacune par un point et par un vecteur
(p0, v0)et(p1, v1). On cherche à caractériser leur plan commun, par un point et un vecteur normal.Si elles ne sont pas parallèles, leurs vecteurs directeurs
v0etv1ne sont pas colinéaires. Leur produit vectorieln = v0 ^ v1est non nul et orthogonal aux deux droites et fait donc un très bon vecteur normal pour le plan cherché.Si elles sont parallèles leurs vecteurs directeurs sont certes colinéraires, mais
p0 - p1n'est pas colinéaire à ces derniers (sinon, vous pouvez vérifier, les droites seraient identiques). On peut donc choisirn = v0 ^ (p0 - p1)comme vecteur normal pour le plan cherché.Il nous reste à trouver un point sur le plan cherché : c'est trivial, il suffit de prendre par exemple
p0puisque ce plan contient par définition la première droite. Pour obtenir une équation de plan du typen ⋅ r = d, il suffit de prendred = p0 ⋅ n.En fait, nous nous intéressons seulement au cas de droites sécantes, voici donc le calcul pour obtenir l'équation du plan dans ce cas spécifique :
Retour au problème
En prenant les trajectoires corrigées deux par deux, on peut définir un tas de plans contenant tous le point cherché. Or l'intersection de trois plans non parallèles est un point, qui sera forcément ce dernier ! Ouvrons une nouvelle parenthèse.
Intersection de plans
Allons-y pour l'intersection de trois plan non parallèles
(p0, d0),(p1, d1)et(p2, d2).Le point d'intersection, que nous allons noter
r, respecte les équation des trois plans :L'astuce consiste ici à choisir une base vectorielle alternative :
En exprimant la position cherchée comme combinaison de ces trois vecteurs
r = a0 u 0 + a1 u1 + a2 u2, l'équation du premier plan devient :On peut reconnaître ici le produit mixte de nos trois vecteurs normaux, un scalaire que l'on va noter
U = n0 ⋅ (n1 ^ n2). Les trois équations deviennent de la même façon :Ce qui nous donne finalement ces fameux coefficients :
Qui nous donnent donc le vecteur position de l'intersection de nos trois plans. Pour rappel, voici les calculs à effectuer à partir des constantes définissant les trois plans :
Re-retour au problème
En prenant trois trajectoires corrigées
(p0, v0 - v),(p1, v1 - v)et(p2, v2 - v), on sait désormais caractériser leurs plans communs deux à deux, soit trois plan. Et on sait également déterminer l'intersection de ces trois plan. Problème résolu !