Je passe sur la première partie, trouver des intersections de ligne dans le plan c'est sans grand intérêt.
La seconde partie est beaucoup, beaucoup plus intéressante. J'ai vainement cherché une solution élégante avant d'en trouver une sur Reddit. Je vous l'explique.
À supposer que l'on trouve une position de départ p et une vitesse v qui permette de percuter tous les grêlons, en se plaçant dans le référentiel de notre projectile, ce sont tous les grêlons qui vont converger jusqu'à l'atteindre, chacun à son tour. Autrement dit, pour un grêlon (p0, v0), la droite (p0, v0 - v) passe par notre position de départ p. Et il en est de même pour les autres grêlons.
Par conséquent, les trajectoires corrigées des trois premiers grêlons (p0, v0 -v), (p1, v1 -v) et (p2, v2 -v) se coupent deux à deux en p. Il est temps d'ouvrir une parenthèse sur les droites sécantes.
Des droites sécantes
Dans l'espace, contrairement au plan, des droites peuvent être identiques, parallèles, sécantes ou... rien de tout ça.
Étant données deux droites caractérisées chacune par un point et un vecteur directeur l0 = (p0, v0) et l1 = (p1, v1), la première chose à vérifier est qu'elles ne sont ni identiques ni parallèles. Autrement dit, que leurs vecteurs directeurs ne sont pas colinéaires. Une façon de faire consiste à prendre leur produit vectoriel, qui ne doit pas être nul.
Si ces droites ne sont pas parallèles, les droites vectorielles associées (O, v0) et (O, v1), définissent un plan vectoriel. Ce plan vectoriel peut être caractérisé par un vecteur normal facile à construire par le produit vectoriel des vecteurs directeurs de ces deux droites : n = v0 ^ v1.
Le plan affine parallèle à ce plan vectoriel et incluant d0 a pour équation vectorielle r ⋅ n = p0 ⋅ n. Le plan affine incluant d1 a quant a lui pour équation vectorielle r ⋅ n = p1 ⋅ n.
Ces plans sont identiques si et seulement si p0 ⋅ n = p1 ⋅ n. Autrement dit, en revenant à la définition de ce vecteur normal n, si (p0 - p1) ⋅ (v0 ^ v1) = 0. Si ces plans sont identiques, les droites sont coplanaire, et n'étant pas parallèles, elles sont donc sécantes. Réciproquement, si les droites sont coplanaires, les plans sont identiques.
Retour au problème
Puisque le problème a une solution, les trajectoires corrigées de deux grêlons (p0, v0 - v) et (p1, v1 - v) sont sécantes. Bon, ok, à condition qu'elles ne soient pas identiques : si c'était le cas on prendrait juste une autre grêlon, on en a plein à notre disposition. Mais vous pouvez vérifier sur vos données, ce cas ne se présente pas. Par conséquent :
Pour résoudre ça simplement, il y a une astuce. On va utiliser une base vectorielle ainsi définie, avec des vecteurs conçus que chacun d'entre eux soit orthogonal à deux vecteurs des équations précédentes :
u0 = A1 ^ A2
u1 = A2 ^ A0
u2 = A0 ^ A1
Et écrire la vitesse que nous cherchons sur cette base : v = a0 u0 + a1 u1 + a2 u2. Les équations précédentes deviennent désormais :
La vitesse, c'est bien, mais c'est surtout la position de départ qu'on nous demande. On va dire que c'est facile à déduire désormais : c'est l'intersection des trajectoires corrigées des deux premiers grêlons. Par exemple, on peut en prendre d'autres si on veut.
Sauf que non, ce n'est vraiment pas trivial à calculer, l'intersection de deux droites sécantes dans l'espace. Il y a encore une astuce, et celle-là est vraiment de moi. Je vous la donnerai plus tard, là je suis fatigué de raconter mes aventures mathématiques.
# 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.
Sommaire
Bon, c'est un problème de géométrie.
Je passe sur la première partie, trouver des intersections de ligne dans le plan c'est sans grand intérêt.
La seconde partie est beaucoup, beaucoup plus intéressante. J'ai vainement cherché une solution élégante avant d'en trouver une sur Reddit. Je vous l'explique.
À supposer que l'on trouve une position de départ p et une vitesse v qui permette de percuter tous les grêlons, en se plaçant dans le référentiel de notre projectile, ce sont tous les grêlons qui vont converger jusqu'à l'atteindre, chacun à son tour. Autrement dit, pour un grêlon
(p0, v0), la droite(p0, v0 - v)passe par notre position de départ p. Et il en est de même pour les autres grêlons.Par conséquent, les trajectoires corrigées des trois premiers grêlons
(p0, v0 -v), (p1, v1 -v)et(p2, v2 -v)se coupent deux à deux en p. Il est temps d'ouvrir une parenthèse sur les droites sécantes.Des droites sécantes
Dans l'espace, contrairement au plan, des droites peuvent être identiques, parallèles, sécantes ou... rien de tout ça.
Étant données deux droites caractérisées chacune par un point et un vecteur directeur
l0 = (p0, v0)etl1 = (p1, v1), la première chose à vérifier est qu'elles ne sont ni identiques ni parallèles. Autrement dit, que leurs vecteurs directeurs ne sont pas colinéaires. Une façon de faire consiste à prendre leur produit vectoriel, qui ne doit pas être nul.Si ces droites ne sont pas parallèles, les droites vectorielles associées
(O, v0)et(O, v1), définissent un plan vectoriel. Ce plan vectoriel peut être caractérisé par un vecteur normal facile à construire par le produit vectoriel des vecteurs directeurs de ces deux droites :n = v0 ^ v1.Le plan affine parallèle à ce plan vectoriel et incluant
d0a pour équation vectorieller ⋅ n = p0 ⋅ n. Le plan affine incluantd1a quant a lui pour équation vectorieller ⋅ n = p1 ⋅ n.Ces plans sont identiques si et seulement si
p0 ⋅ n = p1 ⋅ n. Autrement dit, en revenant à la définition de ce vecteur normal n, si(p0 - p1) ⋅ (v0 ^ v1) = 0. Si ces plans sont identiques, les droites sont coplanaire, et n'étant pas parallèles, elles sont donc sécantes. Réciproquement, si les droites sont coplanaires, les plans sont identiques.Retour au problème
Puisque le problème a une solution, les trajectoires corrigées de deux grêlons
(p0, v0 - v)et(p1, v1 - v)sont sécantes. Bon, ok, à condition qu'elles ne soient pas identiques : si c'était le cas on prendrait juste une autre grêlon, on en a plein à notre disposition. Mais vous pouvez vérifier sur vos données, ce cas ne se présente pas. Par conséquent :En réorganisant un peu et en utilisant les propriété du produit mixte :
Donnons un nom à ces termes constants :
On a donc :
Plus de droites
De la même façon, en utilisant une droite de plus, posons :
On a maintenant trois équations sur v :
Pour résoudre ça simplement, il y a une astuce. On va utiliser une base vectorielle ainsi définie, avec des vecteurs conçus que chacun d'entre eux soit orthogonal à deux vecteurs des équations précédentes :
Et écrire la vitesse que nous cherchons sur cette base :
v = a0 u0 + a1 u1 + a2 u2. Les équations précédentes deviennent désormais :On peut reconnaître ici le produit mixte de nos vecteurs
A0et compagnie, que l'on va nommerA* = A0 ⋅ (A1 ^ A2), ce qui donne :Et finalement nos coefficients :
Récapitulons
Avec les trois premiers grêlons, on calcule les vecteurs et scalaires constants suivants :
Puis les vecteurs suivants :
Et enfin les coefficients suivants :
La vitesse de notre projectile doit être :
Et la position alors ?
La vitesse, c'est bien, mais c'est surtout la position de départ qu'on nous demande. On va dire que c'est facile à déduire désormais : c'est l'intersection des trajectoires corrigées des deux premiers grêlons. Par exemple, on peut en prendre d'autres si on veut.
Sauf que non, ce n'est vraiment pas trivial à calculer, l'intersection de deux droites sécantes dans l'espace. Il y a encore une astuce, et celle-là est vraiment de moi. Je vous la donnerai plus tard, là je suis fatigué de raconter mes aventures mathématiques.