Déterminer exactement si/quand/où une ligne mobile a intersecté un point mobile

novembre 3, 2021

Déterminer exactement si/quand/où une ligne mobile a intersecté un point mobile
Destination
Intuition
Modèle
Solution
Généralisation
Résumé
Discuter sur Reddit
Archive

posé par Craig Gidney le 5 février 2013

J’essaie d’inclure des exemples de projets lorsque je publie des bibliothèques. Dans le cas des collections périssables, le projet d’échantillon était en fait un simple jeu basé sur la découpe de lignes avec le pointeur de la souris :

Dans le cadre de l’écriture de l’échantillon, j’ai dû résoudre le problème de déterminer si, quand et où le pointeur de la souris a été balayé sur une ligne (ou vice versa). Ma référence habituelle pour les algorithmes de géométrie ne contenait pas de solution, j’en ai donc développé une moi-même.

Dans ce post, je vais expliquer une solution analytique au problème. La solution est mise en œuvre dans une petite quantité de code source (environ 150 lignes, en comptant les commentaires et les méthodes/types de soutien), également disponible sur github.

Destination

Il s’avère que « le pointeur de la souris a-t-il coupé la ligne en mouvement ? » est l’un de ces problèmes mathématiques magiques qui commence avec quelques contraintes relativement simples, puis semble devenir assez compliqué à mesure que vous le résolvez, mais ensuite presque tout s’annule ou se combine dans les dernières étapes et vous vous retrouvez avec quelque chose d’absurdement simple. (Puis, quand vous revenez en arrière pour examiner la solution, il s’avère qu’il y avait un chemin facile pendant tout ce temps.)

Pour la référence et la motivation, je vais juste larguer la viande de l’implémentation juste ici, avant de l’expliquer. Les mots soulignés sont des liens vers le code correspondant sur github.

public static IEnumerable<Sweep> WhenLineSweepsPoint(LineSegment pathOfLineStartPoint, LineSegment pathOfLineEndPoint, Point point) {var a = point - pathOfLineStartPoint.Start;var b = -pathOfLineStartPoint.Delta;var c = pathOfLineEndPoint.Start - pathOfLineStartPoint.Start;var d = pathOfLineEndPoint.Delta - pathOfLineStartPoint.Delta;return from t in QuadraticRoots(b.Cross(d), a.Cross(d) + b.Cross(c), a.Cross(c)) where t >= 0 && t <= 1 let start = pathOfLineStartPoint.LerpAcross(t) let end = pathOfLineEndPoint.LerpAcross(t) let s = point.LerpProjectOnto(new LineSegment(start, end)) where s >= 0 && s <= 1 orderby t select new Sweep(timeProportion: t, acrossProportion: s);}

Je ne sais pas pour vous, mais le fait que le code ci-dessus résout le problème me stupéfie. Il semble trop simple, et pourtant trop peu lié. Il ne devrait pas y avoir, comme, des cas de coin ? De plus, d’où viennent ces simples produits croisés ? En quoi les introduire dans un polynôme quadratique peut aider ? Ceci… va devoir être expliqué.

Intuition

Commençons par considérer certains des cas que nous pourrions rencontrer, afin d’avoir une sensation intuitive du problème. L’animation ci-dessous montre plusieurs mouvements de ligne possibles :

Simple : les deux points d’extrémité se déplacent à la même vitesse, et seulement le long du vecteur normal de la ligne.
Latéral : un cas dégénéré où la ligne se déplace sur sa propre longueur.
Lever : un point d’extrémité se déplace horizontalement tandis que l’autre se déplace verticalement ( » lever » et abaisser la ligne).
Plonger : un point d’extrémité se déplace en diagonale (‘plongeant’ par le milieu) tandis que l’autre se déplace verticalement.

Divers cas de balayage

Notez qu’une ligne peut balayer un point 0, 1 ou 2 fois car ses points d’extrémité se déplacent à une vitesse constante d’une position à l’autre. Le cas » Lever » contient commodément les trois possibilités. C’est, intuitivement, la raison pour laquelle la solution implique une équation quadratique (qui peut avoir 0, 1, ou 2 racines réelles distinctes).

Une autre prise de conscience utile est que certains des cas, comme la ligne se déplaçant à une vitesse constante ou restant immobile, correspondront à des équations quadratiques dégénérées où le coefficient d’ordre le plus élevé est zéro (c’est-à-dire ou même ). Nous devons inclure ce genre de cas dans les tests.

Modèle

Pour qu’un segment de droite de à contienne un point , deux conditions doivent être satisfaites. Premièrement, le vecteur ‘offset’ de à doit être parallèle au vecteur ‘delta’ de à . Nous pouvons représenter cela mathématiquement en exigeant que leur produit en croix soit nul : $(c-p) \times (q-p) = 0$ . Cela garantit que est sur la ligne que l’on obtient en prolongeant le segment de droite dans les deux directions (ou que l’on a un segment de droite dégénéré à point unique). Deuxièmement, la projection scalaire du vecteur offset sur le vecteur delta doit être dans le bon intervalle : $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Cela garantit que ne dépasse aucun des points d’extrémité du segment.

A mesure que le temps passe de à , notre segment de droite aura balayé un point si et seulement s’il existe un instant où le segment de droite actuel contient . Comme les extrémités de notre segment de droite se déplacent à une vitesse constante, le chemin qu’elles suivent est également un segment de droite. Un point d’extrémité se déplaçant de à sera au point linéairement interpolé $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ au temps . Notez que je vais abréger en pour gagner de la place. En plaçant nos points mobiles dans nos formules « un segment de droite contient un point », nous trouvons satisfaisant $0 \leq t \leq 1$ et $(c - (p_0 + p_d \cdot t)) \ctimes ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ et $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2} \leq 1$ .

Notez que « un certain produit en croix doit être égal à 0″ n’est pas la seule façon de formuler le problème. Il est également logique d’y penser en trouvant un et un , tous deux dans l’intervalle , tels que est le résultat de lerp les deux points d’extrémité à travers leur chemin par et ensuite lerp entre les points d’extrémité par . Mathématiquement, cela signifie . Les variables et correspondent grossièrement à « quand » et « où » se produit une intersection. Cependant, il est plus difficile de résoudre le problème sous cette forme, car n’est pas initialement isolé, donc je vais utiliser le cadrage du produit en croix (contrairement à ce que j’ai fait la première fois…).

Solution

Le produit en croix et le produit scalaire ont de très belles propriétés qui vont permettre d’isoler plus facilement . Premièrement, ils distribuent l’addition, ce qui signifie $u \times (v + w) = u \times v + u \times w$ et $u \cdot (v + w) = u \cdot v + u \cdot w$ . Deuxièmement, la mise à l’échelle peut être faite avant ou après l’un ou l’autre produit, ce qui signifie $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ et $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , où est un nombre réel. Enfin, le produit scalaire est commutatif, ce qui signifie $u \cdot v = v \cdot u$ , alors que le produit en croix est anti-commutatif, ce qui signifie $u \times v = -v \times u$ .

En appliquant cette connaissance du produit, et en utilisant un peu de recul pour savoir qu’il faut traiter les sous-expressions particulières comme des variables individuelles, nous pouvons transformer notre équation du produit en croix-is-zéro en une équation quadratique :

$\begin{align*}. 0 =(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \\\N= ((c - p_0) - p_d \cdot t) \Ntimes ((q_0 - p_0) - (q_d - p_d) \cdot t) \N= (a + b \cdot t) \Ntimes (c + d \cdot t) \N;\N;\N;\N;\N ;\a = c - p_0 \\\\\\\\N;\N ; \N ; \N ; \N ; \N ; \N ; \N ; où ; \N ; b = -p_d \N ; \N ; \N ; \N ; \N ; \N ; \N ; où ; \N ; c = q_0 - p_0 \N ; \N ; \N ; \N ; \N ; \N ; \N ; où ; \N ; d = -(q_d - p_d) \\N= a \times c + a \times d \cdot t + b \times c \cdot t + b \times d \cdot t \cdot t \N= t^2 \cdot (b \times d) + t \cdot (a \times d + b \times c) + (a \times c) \end{align*}$

(C’est hilareusement plus simple que le chemin que j’ai pris la première fois.)

Ah, maintenant on comprend d’où vient la forme de la solution du code. Nous avons commencé avec un produit en croix égal à zéro (affirmant que le vecteur de la ligne au point était parallèle à la ligne) et avons dû diviser le produit afin d’isoler les sommes de termes impliquant différentes puissances de . Cela donne naturellement une équation quadratique dont les coefficients font intervenir des produits croisés. Neat!

Notez que c’est une équation très « robuste », parce que nous n’avons jamais supposé quoi que ce soit sur les vecteurs ou les scalaires en cours de route. Par exemple, nous ne divisons jamais (ou annulons implicitement) par une variable, donc nous n’avons pas introduit de conditions non nulles cachées.

Avec l’équation simplifiée, déterminer les valeurs possibles de est juste un truc standard de « résoudre un polynôme quadratique ». Nous devons gérer les cas de coin avec des zéros, ce qui rend le code un peu plus compliqué, mais c’est juste un truc ennuyeux au cas par cas, donc je vais juste faire un lien vers lui.

Une fois que nous connaissons une valeur possible de , nous pouvons trouver exactement où la collision s’est produite en utilisant la formule plug-t-into-line-segment-point-containment mentionnée un peu plus haut : $s = \frac{\i}(c-(p_0 + p_d \cdot t)) \cdot ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))}{((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t))^2}$ . J’appelle cette formule la « projection lerp » de sur la ligne au temps , car elle renvoie la proportion à lerp par, du point de départ de la ligne à son point d’arrivée, afin de retrouver . C’est une petite méthode pratique pour extraire :

public static double LerpProjectOnto(this Point point, LineSegment line) { var b = point - line.Start; var d = line.Delta; return (b * d) / (d * d); // when d == 0, result is +-infinity or NaN}

Enfin, une fois que nous avons et , nous devons vérifier qu’ils sont dans l’intervalle . Si est hors de portée, alors la collision ne se produira pas pendant le pas de temps actuel. Si est hors de portée alors la collision se produira sur la ligne étendue, mais pas sur le segment de ligne. Puisque et décrivent de combien il faut lerp pour trouver quand/où la collision s’est produite, c’est aussi une information utile à retourner à l’appelant.

Généralisation

Un détail important que je n’ai pas encore mentionné est qu’un pointeur de souris en mouvement ne correspond évidemment pas à un point. Heureusement, nous pouvons simplement annuler le mouvement du pointeur de la souris au cours du dernier pas de temps (en supposant qu’il soit linéaire) en le déduisant du mouvement du segment de ligne. Non seulement cela réduit le système à un système soluble, mais les valeurs et résultantes sont valides sans aucune sorte de transformation inverse. L’utilisation ressemble à ceci:

// time goes from t0 to t1// line segment endpoint 1 moves from p0 to p1// line segment endpoint 2 moves from q0 to q1// point moves from c0 to c1var results = from hit in WhenLineSweepsPoint(new LineSegment(p0 - c0, p1 - c1), new LineSegment(q0 - c0, q1 - c1), new Point(0, 0)) let hitPos = new LineSegment(c0, c1).LerpAcross(hit.TimeProportion) let hitTime = t0 + (t1-t0)*hit.TimeProportion select new { p = hitPos, t = hitTime }foreach (var result in results) { System.Diagnostics.Debug.WriteLine(string.Format("Hit at p={0}, t={1}", result.p, result.t);}

Une complication potentielle est les segments de ligne dégénérés qui n’ont pas de longueur (où les deux points d’extrémité sont égaux). Le code ne gère pas explicitement ce cas, mais agira comme si couper une ligne qui est en fait un point est impossible. Le calcul de , s’il est atteint, sera divisé par zéro. Le résultat (soit -infini, +infini, ou NaN) échouera à la vérification de la plage.

Un autre aspect que je n’ai pas couvert est l' »angle de coupe ». Dans l’animation montrant les différents cas, les coupes rouges sont orientées par lerping entre les vitesses des deux points d’extrémité par (lorsque la vitesse résultante est 0, un angle aléatoire est choisi). Mais j’ai aussi utilisé d’autres approches comme « l’angle de coupe est la vitesse du point ». Fondamentalement, c’est un cas d’utilisation de ce qui semble bon et se sent naturel au lieu d’essayer de comprendre la véritable signification de « l’angle de coupe ».

Résumé

Ce problème devient trivial dès que vous appliquez certaines connaissances de l’algèbre linéaire. Je suppose que ce n’est pas trop surprenant, puisque l’algèbre linéaire (et les polynômes) apparaissent partout, notamment en géométrie.

Une généralisation naturelle de ce problème est d’inclure les épaisseurs. Les lignes dessinées sur les écrans ne sont pas infiniment fines, après tout. Avoir une épaisseur est également un bon moyen de réduire l’effet des erreurs en virgule flottante arrondies dans différentes directions pendant différents pas de temps. Un autre changement utile serait la possibilité de gérer les trajectoires paraboliques, puisque les objets du jeu sont souvent en chute libre. D’un autre côté, je suppose qu’il est probablement plus facile de simplement traiter les ‘lignes épaisses’ comme des polygones avec des pas de temps à vitesse constante.

–

Discuter sur Reddit

–

Twisted Oak Studios offre des services de conseil et de développement sur des projets interactifs de haute technologie. Consultez notre portfolio, ou faites-nous signe si vous avez quelque chose pour lequel vous pensez que des ingénieurs vraiment rad devraient vous aider.

Savage Rose

Déterminer exactement si/quand/où une ligne mobile a intersecté un point mobile | Twisted Oak Studios Blog