Genau bestimmen, ob/wann/wo eine sich bewegende Linie einen sich bewegenden Punkt schneidet

November 3, 2021

Genau bestimmen, ob/wann/wo eine sich bewegende Linie einen sich bewegenden Punkt schneidet
Ziel
Intuition
Modell
Lösung
Verallgemeinerung
Zusammenfassung
Discuss on Reddit
Archiv

gepostet von Craig Gidney am 5. Februar 2013

Ich versuche, Beispielprojekte beizufügen, wenn ich Bibliotheken veröffentliche. Im Fall der verderblichen Sammlungen war das Beispielprojekt eigentlich ein einfaches Spiel, das auf dem Schneiden von Linien mit dem Mauszeiger basierte:

Als Teil des Schreibens des Beispiels musste ich das Problem lösen, zu bestimmen, ob, wann und wo der Mauszeiger über eine Linie gestrichen wurde (oder andersherum). Meine übliche Referenz für Geometriealgorithmen enthielt keine Lösung, also habe ich selbst eine entwickelt.

In diesem Beitrag werde ich eine analytische Lösung für das Problem erläutern. Die Lösung ist in einer kleinen Menge Quellcode implementiert (etwa 150 Zeilen, Kommentare und unterstützende Methoden/Typen mitgezählt), der auch auf github verfügbar ist.

Ziel

Es stellt sich heraus, dass die Frage „Hat der Mauszeiger die sich bewegende Linie geschnitten?“ eines dieser magischen mathematischen Probleme ist, das mit einigen relativ einfachen Einschränkungen beginnt und dann beim Lösen ziemlich kompliziert zu werden scheint, aber dann hebt sich fast alles auf oder kombiniert sich in den letzten Schritten und man erhält etwas absurd Einfaches. (Wenn man dann zurückgeht, um sich die Lösung anzusehen, stellt sich heraus, dass es die ganze Zeit einen einfachen Weg gab.)

Als Referenz und zur Motivation werde ich das Wesentliche der Implementierung gleich hier abladen, bevor ich es erkläre. Die unterstrichenen Wörter sind Links zum entsprechenden Code auf 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);}

Ich weiß nicht, wie es Ihnen geht, aber die Tatsache, dass der obige Code das Problem löst, erstaunt mich. Es scheint zu einfach zu sein, und doch zu unverbunden. Sollte es nicht so etwas wie Eckfälle geben? Außerdem, woher kommen diese einfachen Kreuzprodukte? Wie hilft es, sie in ein quadratisches Polynom einzugeben? Das… muss erklärt werden.

Intuition

Betrachten wir zunächst einige der Fälle, die uns begegnen könnten, um ein intuitives Gefühl für das Problem zu bekommen. Die Animation unten zeigt verschiedene mögliche Linienbewegungen:

Einfach: beide Endpunkte bewegen sich mit der gleichen Geschwindigkeit und nur entlang des Normalenvektors der Linie.
Seitwärts: ein entarteter Fall, bei dem sich die Linie entlang ihrer eigenen Länge bewegt.
Anheben: ein Endpunkt bewegt sich horizontal, während sich der andere vertikal bewegt („Anheben“ und Absenken der Linie).
Tauchen: ein Endpunkt bewegt sich diagonal („taucht“ durch die Mitte), während der andere sich vertikal bewegt.

Various sweep cases

Beachte, dass eine Linie einen Punkt 0, 1 oder 2 Mal überstreichen kann, da sich ihre Endpunkte mit einer konstanten Geschwindigkeit von einer Position zur anderen bewegen. Der Fall „Anheben“ enthält praktischerweise alle drei Möglichkeiten. Das ist intuitiv der Grund, warum die Lösung eine quadratische Gleichung beinhaltet (die 0, 1 oder 2 verschiedene reelle Wurzeln haben kann).

Eine weitere nützliche Erkenntnis ist, dass einige der Fälle, wie die Linie, die sich mit einer konstanten Geschwindigkeit bewegt oder still steht, entarteten quadratischen Gleichungen entsprechen, bei denen der Koeffizient höchster Ordnung Null ist (d.h. oder sogar ). Wir müssen diese Art von Fällen in die Tests einbeziehen.

Modell

Damit ein Liniensegment von nach einen Punkt enthält, müssen zwei Bedingungen erfüllt sein. Erstens muss der „Offset“-Vektor von nach parallel zum „Delta“-Vektor von nach sein. Wir können dies mathematisch darstellen, indem wir verlangen, dass ihr Kreuzprodukt Null ist: $(c-p) \times (q-p) = 0$ . Dies garantiert, dass auf der Linie liegt, die man erhält, wenn man das Liniensegment in beide Richtungen verlängert (oder dass man ein entartetes Ein-Punkt-Liniensegment hat). Zweitens muss die skalare Projektion des Offset-Vektors auf den Delta-Vektor im richtigen Bereich liegen: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Dies garantiert, dass an keinem der Endpunkte des Segments vorbeigeht.

Wenn die Zeit von bis vergeht, hat unser Liniensegment einen Punkt nur dann durchlaufen, wenn es einen Zeitpunkt gibt, an dem das aktuelle Liniensegment enthält. Da sich die Endpunkte unseres Linienabschnitts mit einer konstanten Geschwindigkeit bewegen, ist der Weg, dem sie folgen, ebenfalls ein Linienabschnitt. Ein Endpunkt, der sich von nach bewegt, befindet sich zum Zeitpunkt an dem linear interpolierten Punkt $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ . Beachten Sie, dass ich als abkürze, um Platz zu sparen. Wenn wir unsere beweglichen Punkte in die Formeln „Linienabschnitt enthält Punkt“ einsetzen, müssen wir finden, das $0 \leq t \leq 1$ und $(c - (p_0 + p_d \cdot t)) \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ und $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$ .

Beachte, dass „irgendein Kreuzprodukt muss gleich 0″ nicht die einzige Möglichkeit ist, das Problem zu formulieren. Man kann sich das Problem auch so vorstellen, dass man ein und ein findet, die beide im Bereich liegen, so dass das Ergebnis der Kreuzung der beiden Endpunkte auf ihrem Weg durch und der Kreuzung zwischen den Endpunkten durch ist. Mathematisch bedeutet das . Die Variablen und entsprechen in etwa dem „wann“ und „wo“ ein Schnittpunkt auftritt. Allerdings ist es schwieriger, das Problem in dieser Form zu lösen, weil anfangs nicht isoliert ist, also werde ich das Kreuzprodukt verwenden (anders als beim ersten Mal…).

Lösung

Das Kreuzprodukt und das Punktprodukt haben einige sehr schöne Eigenschaften, die es einfacher machen, zu isolieren. Erstens verteilen sie die Addition, d.h. $u \times (v + w) = u \times v + u \times w$ und $u \cdot (v + w) = u \cdot v + u \cdot w$ . Zweitens kann die Skalierung vor oder nach einem der beiden Produkte erfolgen, d. h. $(c \cdot u) \times v = c \cdot (u \times v)$ und $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , wobei eine reelle Zahl ist. Schließlich ist das Punktprodukt kommutativ, das heißt $u \cdot v = v \cdot u$ , während das Kreuzprodukt antikommutativ ist, das heißt $u \times v = -v \times u$ .

Wenn wir dieses Wissen über das Produkt anwenden, und wenn wir wissen, dass wir bestimmte Unterausdrücke als einzelne Variablen behandeln müssen, können wir unsere Kreuzprodukt-ist-null-Gleichung in eine quadratische Gleichung umwandeln:

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

(Das ist viel einfacher als der Weg, den ich beim ersten Mal genommen habe.)

Ah, jetzt ist klar, woher die Form der Codelösung stammt. Wir begannen mit einem Kreuzprodukt, das gleich Null war (was bedeutet, dass der Vektor von der Geraden zum Punkt parallel zur Geraden verlief) und mussten das Produkt aufteilen, um die Summen der Terme zu isolieren, die verschiedene Potenzen von beinhalten. Dies führt natürlich zu einer quadratischen Gleichung mit Koeffizienten, die Kreuzprodukte enthalten. Toll!

Bei dieser Gleichung handelt es sich um eine sehr „robuste“ Gleichung, weil wir auf dem Weg dorthin nie etwas über die Vektoren oder Skalare angenommen haben. Zum Beispiel teilen wir nie durch eine Variable (oder heben sie implizit auf), so dass wir keine lauernden Nicht-Null-Bedingungen eingeführt haben.

Mit der vereinfachten Gleichung ist die Bestimmung der möglichen Werte von nur eine Standardaufgabe zum Lösen quadratischer Polynome. Wir müssen Eckfälle mit Nullen behandeln, was den Code etwas komplizierter macht, aber das ist nur langweiliges Fall-zu-Fall-Zeug, so dass ich einfach darauf verweise.

Wenn wir einen möglichen Wert von kennen, können wir genau herausfinden, wo die Kollision aufgetreten ist, indem wir die bereits erwähnte Plug-in-to-Line-Segment-Point-Containment-Formel verwenden: $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}$ . Ich nenne diese Formel die „Lerp-Projektion“ von auf die Linie zum Zeitpunkt , weil sie das Verhältnis liefert, um das man vom Startpunkt der Linie zu ihrem Endpunkt lerpen muss, um zurückzubekommen. Es ist eine praktische kleine Methode zum Extrahieren:

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}

Schließlich müssen wir, sobald wir und haben, überprüfen, ob sie im Bereich liegen. Wenn außerhalb des Bereichs liegt, wird die Kollision während des aktuellen Zeitschritts nicht stattfinden. Wenn außerhalb des Bereichs liegt, wird die Kollision auf der verlängerten Linie stattfinden, aber nicht auf dem Liniensegment. Da und beschreiben, wie weit man lerpen muss, um herauszufinden, wann/wo die Kollision stattgefunden hat, ist es auch eine nützliche Information, die an den Aufrufer zurückgegeben werden kann.

Verallgemeinerung

Ein wichtiges Detail, das ich noch nicht erwähnt habe, ist, dass ein sich bewegender Mauszeiger offensichtlich nicht einem Punkt entspricht. Glücklicherweise können wir die Bewegung des Mauszeigers im letzten Zeitschritt einfach aufheben (vorausgesetzt, sie ist linear), indem wir sie von der Bewegung des Liniensegments abziehen. Dadurch wird das System nicht nur auf ein lösbares System reduziert, sondern die resultierenden – und -Werte sind auch ohne jede Art von inverser Transformation gültig. Die Verwendung sieht wie folgt aus:

// 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);}

Eine mögliche Komplikation sind entartete Liniensegmente, die keine Länge haben (bei denen beide Endpunkte gleich sind). Der Code behandelt diesen Fall nicht explizit, sondern tut so, als ob das Schneiden einer Linie, die eigentlich ein Punkt ist, unmöglich wäre. Die Berechnung von , wenn sie erreicht wird, wird durch Null geteilt. Das Ergebnis (entweder -unendlich, +unendlich oder NaN) wird die Bereichsprüfung nicht bestehen.

Ein weiterer Aspekt, den ich nicht behandelt habe, ist der „Schnittwinkel“. In der Animation, die die verschiedenen Fälle zeigt, werden die roten Schnitte ausgerichtet, indem die Geschwindigkeiten der beiden Endpunkte um geteilt werden (wenn die resultierende Geschwindigkeit 0 ist, wird ein zufälliger Winkel gewählt). Ich habe aber auch andere Ansätze wie „der Schnittwinkel ist die Geschwindigkeit des Punktes“ verwendet. Im Grunde geht es darum, das zu verwenden, was gut aussieht und sich natürlich anfühlt, anstatt zu versuchen, die wahre Bedeutung von „Schnittwinkel“ herauszufinden.

Zusammenfassung

Dieses Problem wird trivial, sobald man etwas Wissen aus der linearen Algebra anwendet. Ich denke, das ist nicht allzu überraschend, da lineare Algebra (und Polynome) überall auftauchen, besonders in der Geometrie.

Eine natürliche Verallgemeinerung dieses Problems ist die Einbeziehung von Dicken. Auf Bildschirmen gezeichnete Linien sind schließlich nicht unendlich dünn. Eine Dicke ist auch ein guter Weg, um die Auswirkungen von Fließkommafehlern zu reduzieren, die während verschiedener Zeitschritte in verschiedene Richtungen gerundet werden. Eine weitere nützliche Änderung wäre die Fähigkeit, parabolische Pfade zu behandeln, da sich Spielobjekte oft im freien Fall befinden. Andererseits ist es wahrscheinlich einfacher, „dicke Linien“ als Polygone mit konstanten Zeitschritten zu behandeln.

–

Discuss on Reddit

–

Twisted Oak Studios bietet Beratung und Entwicklung für interaktive High-Tech-Projekte. Schauen Sie sich unser Portfolio an, oder rufen Sie uns an, wenn Sie etwas haben, bei dem Sie denken, dass ein paar wirklich tolle Ingenieure Ihnen helfen sollten.

Savage Rose

Genau bestimmen, ob/wann/wo eine sich bewegende Linie einen sich bewegenden Punkt schneidet | Twisted Oak Studios Blog