Określanie dokładnie, czy/gdzie/gdzie ruchoma linia przecięła ruchomy punkt | Twisted Oak Studios Blog

3 listopada, 2021

Determining exactly if/when/where a moving line intersected a moving point
Destination
Intuicja
Model
Rozwiązanie
Uogólnianie
Podsumowanie
Dyskutuj na Reddit
Archiwum

Determining exactly if/when/where a moving line intersected a moving point

posted by Craig Gidney on February 5, 2013

Staram się dołączać przykładowe projekty, gdy publikuję biblioteki. W przypadku nietrwałych kolekcji, przykładowy projekt był właściwie prostą grą opartą na przecinaniu linii wskaźnikiem myszy:

Jako część pisania próbki, musiałem rozwiązać problem określenia czy, kiedy i gdzie wskaźnik myszy został przesunięty przez linię (lub odwrotnie). Moje zwykłe referencje dla algorytmów geometrii nie zawierały rozwiązania, więc opracowałem je sam.

W tym poście wyjaśnię analityczne rozwiązanie tego problemu. Rozwiązanie jest zaimplementowane w niewielkiej ilości kodu źródłowego (około 150 linii, licząc komentarze i wspierające metody/typy), dostępnego również na githubie.

Destination

Okazuje się, że „czy wskaźnik myszy przeciął poruszającą się linię?” jest jednym z tych magicznych problemów matematycznych, które zaczynają się od kilku stosunkowo prostych ograniczeń, potem wydają się dość skomplikowane w miarę rozwiązywania, ale potem prawie wszystko się znosi lub łączy w kilku ostatnich krokach i kończysz z czymś absurdalnie prostym. (Następnie, gdy wrócisz, aby spojrzeć na rozwiązanie, okazuje się, że przez cały czas była łatwa ścieżka.)

Dla odniesienia i motywacji, zamierzam po prostu wyrzucić mięso implementacji właśnie tutaj, przed wyjaśnieniem go. Podkreślone słowa są linkami do odpowiedniego kodu na 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);}

Nie wiem jak ty, ale fakt, że powyższy kod rozwiązuje problem mnie zadziwia. Wydaje się to zbyt proste, a jednocześnie zbyt niepowiązane. Czy nie powinno być, jak w przypadku narożnych przypadków? Dodatkowo, skąd się wzięły te proste iloczyny krzyżowe? Jak włożenie ich do wielomianu kwadratowego ma pomóc? To… będzie wymagało wyjaśnienia.

Intuicja

Zacznijmy od rozważenia niektórych przypadków, które możemy napotkać, aby uzyskać intuicyjne wyczucie problemu. Poniższa animacja pokazuje kilka różnych możliwych ruchów linii:

Prosty: oba punkty końcowe poruszają się z tą samą prędkością i tylko wzdłuż wektora normalnego linii.
Boczny: zdegenerowany przypadek, w którym linia porusza się wzdłuż własnej długości.
Podniesienie: jeden punkt końcowy porusza się poziomo, podczas gdy drugi porusza się pionowo („podnoszenie” i „opuszczanie” linii).
Dive: jeden punkt końcowy porusza się po przekątnej („nurkuje” przez środek), podczas gdy drugi porusza się w pionie.

Różne przypadki zamiatania

Zauważ, że prosta może zamiatać punkt 0, 1 lub 2 razy, ponieważ jej punkty końcowe poruszają się ze stałą prędkością z jednej pozycji do drugiej. Przypadek „Raise” wygodnie zawiera wszystkie trzy możliwości. Intuicyjnie, dlatego rozwiązanie wymaga równania kwadratowego (które może mieć 0, 1 lub 2 wyraźne korzenie rzeczywiste).

Innym użytecznym uświadomieniem jest to, że niektóre przypadki, takie jak linia poruszająca się ze stałą prędkością lub stojąca w miejscu, będą odpowiadały zdegenerowanym równaniom kwadratowym, w których współczynnik najwyższego rzędu wynosi zero (tj. lub nawet ). Musimy uwzględnić tego typu przypadki w testach.

Model

Aby odcinek prostej od do zawierał punkt , muszą być spełnione dwa warunki. Po pierwsze, wektor „przesunięcia” z do musi być równoległy do wektora „delta” z do . Możemy to przedstawić matematycznie wymagając, aby ich iloczyn krzyżowy wynosił zero: . To gwarantuje, że znajduje się na linii, którą otrzymamy przedłużając odcinek linii w obu kierunkach (lub że mamy zdegenerowany jednopunktowy odcinek linii). Po drugie, rzut skalarny wektora przesunięcia na wektor delta musi znajdować się we właściwym zakresie: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \1$ . Gwarantuje to, że nie minął żadnego z punktów końcowych odcinka.

As time goes from to , our line segment will have swept a point if and only if there is a time where the current line segment contains . Ponieważ punkty końcowe naszego odcinka linii poruszają się ze stałą prędkością, ścieżka, którą podążają, jest również odcinkiem linii. Punkt końcowy poruszający się od do znajdzie się w liniowo interpolowanym punkcie w czasie . Zauważ, że dla oszczędności miejsca będę skracał jako . Wstawienie naszych ruchomych punktów do naszych formuł „odcinek zawiera punkt” mówi nam, że musimy znaleźć spełniający $0 \ t \ 1$ i $(c - (p_0 + p_d \cdot t)) \((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ i $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} \1$ .

Zauważ, że „jakiś iloczyn krzyżowy musi być równy 0″ nie jest jedynym sposobem ujęcia problemu. Sensowne jest również myślenie o tym jako o znalezieniu i , obu w zakresie , takich, że jest wynikiem lerpingu obu punktów końcowych w poprzek ich drogi przez , a następnie lerpingu między punktami końcowymi przez . Matematycznie oznacza to, że . Zmienne i odpowiadają z grubsza „kiedy” i „gdzie” występuje przecięcie. Jednak trudniej jest rozwiązać problem w tej formie, ponieważ nie jest początkowo izolowany, więc będę używał obramowania iloczynu krzyżowego (w przeciwieństwie do tego, co zrobiłem za pierwszym razem…).

Rozwiązanie

Iloczyn krzyżowy i iloczyn kropkowy mają pewne bardzo miłe właściwości, które ułatwią wyizolowanie . Po pierwsze, rozdzielają dodawanie, co oznacza $u \times (v + w) = u \times v + u \times w$ i $u \cdot (v + w) = u \cdot v + u \cdot w$ . Po drugie, skalowanie można wykonać przed lub po dowolnym produkcie, co oznacza $(c \cdot u) \times v = c \cdot (u \times v)$ i $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , gdzie jest liczbą rzeczywistą. Wreszcie, iloczyn kropkowy jest komutatywny, co oznacza, że , podczas gdy iloczyn krzyżowy jest antykomutatywny, co oznacza, że .

Zastosowując tę wiedzę o iloczynie i korzystając z pewnej perspektywy czasu, aby wiedzieć, aby traktować poszczególne wyrażenia podrzędne jako indywidualne zmienne, możemy przekształcić nasze równanie typu cross-product-is-zero w równanie kwadratowe:

$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) \times (a + b \cdot t) \times (c + d \cdot t) \times (c + d \cdot t) \;\a = c - p_0 \u0026apos; b = -p_d \u0026apos; c = q_0 - p_0 \u0026apos; b = -p_d \u0026apos; c = q_0 - p_0 \u0026apos; c = q_0 - p_0 \u0026apos; c = q_0 - p_0 d = -(q_d - p_d) p_d) \= a \times c + a \times d \cdot t + b \times c \cdot t + b \times d \cdot t \= t^2 \cdot (b \times d) + t \cdot (a \times d + b \times c) + (a \times c) \end{align*}$

(To jest przezabawnie prostsze niż droga, którą obrałem za pierwszym razem.)

Ach, teraz jest jasne, skąd wzięła się forma rozwiązania kodu. Zaczęliśmy od iloczynu krzyżowego równego zero (twierdząc, że wektor od prostej do punktu był równoległy do prostej) i musieliśmy podzielić produkt, aby wyodrębnić sumy warunków obejmujące różne potęgi . To naturalnie daje równanie kwadratowe ze współczynnikami zawierającymi iloczyny krzyżowe. Neat!

Zauważ, że jest to bardzo „solidne” równanie, ponieważ nigdy nie zakładaliśmy niczego o wektorach lub skalarach po drodze. Na przykład, nigdy nie dzielimy (lub domyślnie anulujemy) przez zmienną, więc nie wprowadziliśmy żadnych czających się niezerowych warunków.

Z uproszczonym równaniem, określenie możliwych wartości jest po prostu standardową rzeczą „rozwiązywania wielomianu kwadratowego”. Musimy poradzić sobie z przypadkami narożnymi z zerami, co czyni kod nieco bardziej skomplikowanym, ale to tylko nudne rzeczy dla każdego przypadku, więc po prostu połączę się z nim.

Gdy znamy możliwą wartość , możemy dowiedzieć się dokładnie, gdzie doszło do kolizji, używając formuły plug-t-into-line-segment-point-containment, o której wspomniano wcześniej: $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}$ . Nazywam ten wzór „rzutem lerp” na linię w czasie , ponieważ zwraca on proporcję do lerp przez, od punktu początkowego linii do jej punktu końcowego, aby otrzymać z powrotem. Jest to poręczna mała metoda do wyodrębniania:

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}

Wreszcie, gdy mamy już i , musimy sprawdzić, czy są one w zakresie . Jeśli jest poza zakresem, to kolizja nie wystąpi w bieżącym kroku czasowym. Jeśli jest poza zakresem, to kolizja wystąpi na przedłużonej linii, ale nie na odcinku linii. Ponieważ i opisują, ile należy lerpnąć, aby znaleźć kiedy/gdzie wystąpiła kolizja, jest to również użyteczna informacja, którą można zwrócić do wywołującego.

Uogólnianie

Ważnym szczegółem, o którym jeszcze nie wspomniałem, jest to, że poruszający się wskaźnik myszy oczywiście nie odpowiada punktowi. Na szczęście, możemy po prostu anulować ruch wskaźnika myszy w ostatnim kroku czasowym (zakładając, że jest on liniowy) poprzez odjęcie go od ruchu segmentu linii. Nie tylko redukuje to system do jednego rozwiązywalnego, ale również wartości i są ważne bez żadnego odwrotnego przekształcenia. Użycie wygląda następująco:

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

Potencjalną komplikacją są zdegenerowane odcinki linii, które nie mają długości (gdzie oba punkty końcowe są równe). Kod nie obsługuje tego przypadku wprost, ale będzie się zachowywał tak, jakby przecięcie linii, która jest właściwie punktem, było niemożliwe. Obliczenie , jeśli zostanie osiągnięte, spowoduje podzielenie przez zero. Wynik (albo -nieskończoność, +nieskończoność, albo NaN) nie przejdzie kontroli zakresu.

Innym aspektem, którego nie uwzględniłem, jest „kąt cięcia”. W animacji pokazującej różne przypadki, czerwone cięcia są zorientowane przez lerping między prędkościami dwóch punktów końcowych o (gdy wynikowa prędkość wynosi 0, wybierany jest losowy kąt). Ale użyłem również alternatywnych podejść, takich jak „kąt cięcia jest prędkością punktu”. Zasadniczo jest to przypadek użycia tego, co wygląda dobrze i czuje się naturalnie, zamiast próbować dowiedzieć się, jakie jest prawdziwe znaczenie „kąta cięcia”.

Podsumowanie

Ten problem staje się trywialny, gdy tylko zastosujesz trochę wiedzy z algebry liniowej. Nie jest to chyba zbyt zaskakujące, ponieważ algebra liniowa (i wielomiany) pojawiają się wszędzie, zwłaszcza w geometrii.

Naturalnym uogólnieniem tego problemu jest uwzględnienie grubości. Linie rysowane na ekranach nie są przecież nieskończenie cienkie. Posiadanie grubości jest również dobrym sposobem na zmniejszenie efektu zaokrąglania błędów zmiennoprzecinkowych w różnych kierunkach podczas różnych kroków czasowych. Inną przydatną zmianą byłaby możliwość obsługi ścieżek parabolicznych, ponieważ obiekty w grze często spadają swobodnie. Z drugiej strony, chyba łatwiej jest po prostu traktować „grube linie” jako wielokąty o stałej prędkości kroków czasowych.

–

Dyskutuj na Reddit

–

Twisted Oak Studios oferuje doradztwo i rozwój w zakresie zaawansowanych technologicznie projektów interaktywnych. Sprawdź nasze portfolio, lub daj nam znać, jeśli masz coś, w czym Twoim zdaniem powinni Ci pomóc naprawdę świetni inżynierowie.

Archiwum

strilanc
What Quantum Computers Do Faster, with Caveats
Naming Things: Fail-Useful
Detecting Simple Cycles Forming, Faster
Third Party Bit Commitment
Angular Velocity is Simple
Collection Equality is Hard
Deadlocks in Practice: Don’t Hold Locks While Notifying
Brute Force Parallelization
A Year’s Worth of Opinions about Objective-C
Referencing Substrings Faster, without Leaking Memory
Not Crying Over Old Code
Exploring Universal Ternary Gates
Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
Achieving Exponential Slowdown by Enumerating Twice
Using Immortality to Kill Accidental Callback Cycles
Cancellation Tokens (and Collapsing Futures) for Objective-C
Visualizing the Eigenvectors of a Rotation
Collapsing Futures in Objective-C
Bug Hunting #1: Garbled Audio from End to End
Impractical Experiments #1: Representing Numbers as Polynomials
Implementing Quantum Pseudo-Telepathy
Turn On Your Damn Warnings
Big-O Made Trivial
Unffathomable Bugs #7: The Broken Oven
Solomonoff’s Mad Scientist
Yearly Blogging Roundup #1
What isn’t a Monad
Searching a Sorted Matrix Faster
How to Read Nested Ternary Operators
Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
My Bug, My Bad #4: Reading Concurrently
Whole API Testing with Reflection
Optimizing a Parser Combinator into a memcpy
Don’t Treat Paths Like Strings
Breaking a Toy Hash Function
Counting Iterators Lazily
Unfathomable Bugs #6: Pretend Precision
My Bug, My Bad #3: Accidentally Attacking WarCraft 3
Collapsing Types vs Monads (followup)
Collapsing Futures: Easy to Use, Hard to Represent
Eventual Exceptions vs Programming in a Minimal Functional Style
The Mystery of Flunf
Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
Computer Science Blows My Mind
A visit to Execution Labs in Montréal
Transmuting Dice, Conserving Entropy
Rule of Thumb: Ask for the Clock
Rule of Thumb: Use Purposefully Weakened Methods
Rule of thumb: Preconditions Should be Checked Explicitly
Intersecting Linked Lists Faster
Mouse Path Smoothing for Jack Lumber
My Bug, My Bad #2: Sunk by Float
Repeat Yourself Differently
Grover’s Quantum Search Algorithm
Followup to Non-Nullable Types vs C#
Optimizing Just in Time with Expression Trees
When One-Way Latency Doesn’t Matter
Determining exactly if/when/where a moving line intersected a moving point
Emulating Actors in C# with Async/Await
Making an immutable queue with guaranteed constant time operations
Improving Checked Exceptions
Perishable Collections: The Benefits of Removal-by-Lifetime
Odłączanie współdzielonej kontroli
Odłączanie inlined kodu UI
Linq to Collections: Beyond IEnumerable<T>
Opublikuj swoją bibliotekę .Net jako pakiet NuGet
Kiedy null to za mało: typ opcji dla C#
Unfathomable Bugs #5: Readonly or not
Suma Minkowskiego: przykłady
My Bug, My Bad #1: Fractal Spheres
Working around the brittle UI Virtualization in Windows 8
Encapsulating Angles
Unfathomable Bugs #4: Keys that aren’t
How I would even use a monad (in C#)?
Użyteczne/Interesujące metody #1: Observable.WhenEach
Niezrozumiałe błędy #3: Stringing you along
Anonymous Implementation Classes – A Design Pattern for C#
Zadania dla ActionScript 3 – Ulepszanie programowania sterowanego zdarzeniami
Suma i różnice Minkowskiego
Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
Unfathomable Bugs #2: Slashing Out
Szablony skryptów i klasy bazowe
Wyodrębnianie czcionki Unity
Zakaz używania „typów fantomowych” do kodowania długości list w ich typach

Konstruktywna krytyka API Reactive Extensions
Quaternions część 3
Quaternions część 2
Quaternions część 1
Niezrozumiałe błędy #1: Możesz mieć rzeczy! Możesz mieć rzeczy w rzeczach! You can have …
Coroutines – More than you want to know
Asset Bundle Helper
The Visual Studio goes away
.Net’s time traveling StopWatch
Introducing Catalyst

Savage Rose