Annak meghatározása, hogy egy mozgó vonal pontosan metszett-e/amikor/hol egy mozgó pontot | Twisted Oak Studios Blog

november 3, 2021

Determining exactly if/when/where a moving line intersected a moving point
Cél
Intuíció
Modell
megoldás
Általánosítás
Összefoglaló
Discuss on Reddit
Archív

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

posted by Craig Gidney on February 5, 2013

A könyvtárak közzétételekor igyekszem mintaprojekteket mellékelni. A romlandó gyűjtemények esetében a mintaprojekt valójában egy egyszerű játék volt, amely az egérmutatóval történő vonalvágáson alapul:

A minta megírásának részeként meg kellett oldanom annak a problémának a meghatározását, hogy az egérmutató áthúzza-e, mikor és hol egy vonalat (vagy fordítva). A geometria algoritmusokra vonatkozó szokásos referenciám nem tartalmazott megoldást, ezért magam fejlesztettem egyet.

Ebben a bejegyzésben a probléma analitikus megoldását ismertetem. A megoldás egy kis mennyiségű forráskódban van implementálva (kb. 150 sor, a megjegyzéseket és a támogató metódusokat/típusokat is beleszámítva), amely a githubon is elérhető.

Cél

Kiderül, hogy a “vágta-e az egérmutató a mozgó vonalat?” egy olyan mágikus matematikai probléma, amely néhány viszonylag egyszerű megkötéssel kezdődik, majd a megoldás során elég bonyolultnak tűnik, de aztán az utolsó néhány lépésben szinte minden megszűnik vagy egyesül, és a végén valami abszurdan egyszerűt kapunk. (Aztán, amikor visszamész, hogy átnézd a megoldást, kiderül, hogy egész idő alatt volt egy egyszerű út.)

A referencia és a motiváció kedvéért, a megvalósítás húsát ide fogom dobni, mielőtt elmagyaráznám. Az aláhúzott szavak linkek a megfelelő kódra a githubon.

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

Nem tudom, te hogy vagy vele, de az a tény, hogy a fenti kód megoldja a problémát, lenyűgöz. Túl egyszerűnek tűnik, és mégis túlságosan összefüggéstelennek. Nem kellene, hogy legyenek mondjuk sarokesetek? Ráadásul honnan vannak ezek az egyszerű keresztezett termékek? Hogyan segít a kvadratikus polinomba való betáplálásuk? Ez… magyarázatra szorul.

Intuíció

Kezdjük azzal, hogy megvizsgálunk néhány esetet, amivel találkozhatunk, hogy intuitív módon ráérezzünk a problémára. Az alábbi animáció többféle lehetséges vonalmozgást mutat be:

Egyszerű: mindkét végpont azonos sebességgel mozog, és csak a vonal normálvektora mentén.
Oldalirányban: egy elfajult eset, amikor a vonal a saját hosszában mozog.
Emelés: az egyik végpont vízszintesen mozog, míg a másik függőlegesen (“felemeli” és leengedi a vonalat).
Merülés: az egyik végpont átlósan mozog (“merül” középen), míg a másik függőlegesen.

Változatos söprési esetek

Megjegyezzük, hogy egy vonal 0, 1 vagy 2 alkalommal is söpörhet egy pontot, mivel a végpontjai állandó sebességgel mozognak egyik helyzetből a másikba. Az ‘Emelés’ eset kényelmesen tartalmazza mindhárom lehetőséget. Intuitív módon ezért van az, hogy a megoldás egy kvadratikus egyenletet foglal magában (amelynek 0, 1 vagy 2 különböző valós gyöke lehet).

Egy másik hasznos felismerés, hogy néhány eset, mint például az állandó sebességgel mozgó vagy álló egyenes, olyan degenerált kvadratikus egyenleteknek felel meg, ahol a legmagasabb rendű együttható nulla (azaz vagy akár ). Az ilyen eseteket is be kell vonnunk a tesztekbe.

Modell

Hogy a és közötti egyenes szakasz tartalmazzon egy pontot, két feltételnek kell teljesülnie. Először is, a és közötti “offset” vektornak párhuzamosnak kell lennie a és közötti “delta” vektorral. Ezt matematikailag úgy tudjuk ábrázolni, hogy a keresztproduktumuknak nullának kell lennie: $(c-p) \times (q-p) = 0$ . Ez garantálja, hogy azon az egyenesen van, amelyet a vonalszakasz mindkét irányba való meghosszabbításával kapunk (vagy hogy egy elfajult egypontos vonalszakaszunk van). Másodszor, az eltolási vektor skaláris vetülete a deltavektorra a megfelelő tartományban kell, hogy legyen: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Ez garantálja, hogy nem halad túl a szakasz egyik végpontján sem.

Amint az idő -től -ig halad, a vonalszakaszunk akkor és csak akkor söpört végig egy pontot, ha van olyan időpont, amikor az aktuális vonalszakasz -t tartalmazza. Mivel a vonalszakaszunk végpontjai állandó sebességgel mozognak, az általuk követett útvonal is egy vonalszakasz. Egy és között mozgó végpont a $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ lineárisan interpolált pontban lesz időpontban. Vegyük észre, hogy a rövidítést -nek fogom rövidíteni, hogy helyet takarítsunk meg. Ha a mozgó pontjainkat beillesztjük a “vonalszakasz tartalmaz pontot” képleteinkbe, akkor azt kapjuk, hogy meg kell találnunk , amely kielégíti a $0 \leq t \leq 1$ és $(c - (p_0 + p_d \cdot t)) feltételeket. \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ és $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$ .

Megjegyezzük, hogy a “valamilyen kereszttételnek egyenlőnek kell lennie 0-val″ nem az egyetlen módja a probléma megfogalmazásának. Annak is van értelme, ha úgy gondolunk rá, hogy olyan és értékeket találunk, amelyek mindketten a tartományban vannak, úgy, hogy az eredménye annak, hogy mindkét végpontot az útjukon keresztül -mal, majd a végpontok között -rel leroppantjuk. Matematikailag ez azt jelenti, hogy . A és változók nagyjából megfelelnek annak, hogy “mikor” és “hol” történik a metszéspont. Ebben a formában azonban nehezebb megoldani a feladatot, mert kezdetben nem izolált, ezért a keresztszorzatot fogom használni (ellentétben az első alkalommal…).

megoldás

A keresztszorzatnak és a pontszorzatnak van néhány nagyon szép tulajdonsága, ami megkönnyíti izolálását. Először is, elosztják az összeadást, vagyis $u \times (v + w) = u \times v + u \times w$ és $u \cdot (v + w) = u \cdot v + u \cdot w$ . Másodszor, a skálázás bármelyik szorzat előtt vagy után elvégezhető, vagyis $(c \cdot u) \times v = c \cdot (u \times v)$ és $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , ahol egy valós szám. Végül a pontszorzat kommutatív, azaz $u \cdot v = v \cdot u$ , míg a kereszttétel antikommutatív, azaz $u \times v = -v \times u$ .

Ezt a szorzatismeretet alkalmazva, és némi utólagos ismeret segítségével, hogy bizonyos részkifejezéseket önálló változóként kezeljünk, a kereszttermék-az-nulla egyenletünket kvadratikus egyenletté alakíthatjuk át:

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

(Ez viccesen egyszerűbb, mint az első alkalommal választott útvonal.)

Ah, most már világos, honnan jött a kódmegoldás formája. Egy nullával egyenlő kereszttételből indultunk ki (azt állítva, hogy az egyenestől a pontig tartó vektor párhuzamos az egyenessel), és fel kellett osztanunk a szorzatot, hogy elkülönítsük a különböző hatványait tartalmazó kifejezések összegeit. Ez természetesen egy olyan kvadratikus egyenletet eredményez, amelynek együtthatói keresztprodukciókat tartalmaznak. Ügyes!

Megjegyezzük, hogy ez egy nagyon “robusztus” egyenlet, mert útközben semmit sem feltételeztünk a vektorokról vagy skalárokról. Például soha nem osztunk (vagy törölünk implicit módon) egy változóval, így nem vezettünk be semmilyen lappangó nem-nulla feltételt.

Az egyszerűsített egyenlet segítségével a lehetséges értékeinek meghatározása csak a szokásos “kvadratikus polinom megoldása” dolog. A sarokeseteket nullákkal kell kezelnünk, ami egy kicsit bonyolultabbá teszi a kódot, de ez csak unalmas eseti dolgok, így csak belinkelem.

Mihelyt tudjuk egy lehetséges értékét, az előbb említett plug-t-into-line-segment-point-containment-képlet segítségével megtudhatjuk, hogy pontosan hol történt az ütközés: $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}$ . Ezt a képletet “lerp vetületének” nevezem a időpontban lévő egyenesre, mert visszaadja azt az arányt , amivel lerpelni kell az egyenes kezdőpontjától a végpontjáig, hogy visszakapjuk -et. Ez egy praktikus kis módszer a kivonáshoz:

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}

Végül, ha már megvan és , ellenőriznünk kell, hogy a tartományba esnek. Ha a tartományon kívül van, akkor az ütközés nem fog bekövetkezni az aktuális időlépés során. Ha a tartományon kívül van, akkor az ütközés a meghosszabbított vonalon fog bekövetkezni, de a vonalszakaszon nem. Mivel és leírja, hogy mennyit kell lerpelni ahhoz, hogy megtaláljuk, mikor/hol történt az ütközés, ez is hasznos információ, amit a hívónak vissza kell adni.

Általánosítás

Egy fontos részlet, amit még nem említettem, hogy a mozgó egérmutató nyilvánvalóan nem egy pontnak felel meg. Szerencsére egyszerűen ki tudjuk egyenlíteni az egérmutató mozgását az utolsó időlépésben (feltételezve, hogy az lineáris), ha levonjuk a vonalszakasz mozgásából. Ez nem csak a rendszert redukálja megoldhatóvá, de az így kapott és értékek mindenféle inverz transzformáció nélkül is érvényesek. A használat így néz ki:

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

Egy lehetséges bonyodalom a degenerált vonalszakaszok, amelyeknek nincs hossza (ahol mindkét végpont egyenlő). A kód nem kezeli kifejezetten ezt az esetet, de úgy fog viselkedni, mintha egy olyan vonal elvágása, amely valójában egy pont, lehetetlen lenne. A számítása, ha eléri, nullával fog osztani. Az eredmény (vagy -végtelen, +végtelen, vagy NaN) nem felel meg a tartományellenőrzésnek.

A másik szempont, amivel még nem foglalkoztam, a “vágási szög”. A különböző eseteket bemutató animációban a piros vágásokat a két végpont sebességei közötti lerpingeléssel orientáljuk (ha a kapott sebesség 0, akkor egy véletlenszerű szöget választunk). De használtam alternatív megközelítéseket is, mint például “a vágás szöge a pont sebessége”. Alapvetően azt használjuk, ami jól néz ki és természetesnek tűnik, ahelyett, hogy megpróbálnánk kitalálni a “vágási szög” valódi jelentését.

Összefoglaló

Ez a probléma triviálissá válik, amint alkalmazunk néhány ismeretet a lineáris algebrából. Azt hiszem, ez nem túl meglepő, hiszen a lineáris algebra (és a polinomok) mindenütt felbukkannak, különösen a geometriában.

A probléma természetes általánosítása a vastagságok bevonása. A képernyőre rajzolt vonalak végül is nem végtelenül vékonyak. A vastagság megléte jó módja annak is, hogy csökkentsük a lebegőpontos hibák hatását, amelyek különböző irányokba kerekítenek a különböző időlépések során. Egy másik hasznos változtatás lenne a parabolikus pályák kezelésének képessége, mivel a játékobjektumok gyakran szabadesésben vannak. Másrészt, azt hiszem, valószínűleg egyszerűbb, ha a “vastag vonalakat” egyszerűen poligonokként kezeljük állandó sebességű időlépésekkel.

–

Discuss on Reddit

–

A Twisted Oak Studios tanácsadást és fejlesztést kínál high-tech interaktív projektekhez. Nézd meg a portfóliónkat, vagy kiálts, ha van valami, amiben szerinted néhány igazán radikális mérnöknek kellene segítenie neked.

Archív

strilanc
Mit csinálnak gyorsabban a kvantumszámítógépek, figyelmeztetésekkel
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: Peer to Peer Fog of War biztosítása a Map Hacks ellen
Exponenciális lassulás elérése kétszeri felsorolással
A halhatatlanság használata a véletlen visszahívási ciklusok kiiktatására
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
Unfathomable Bugs #7: A törött kemence
Solomonoff őrült tudósa
Éves bloggerkörkép #1
Mi nem monád
Többször keresünk egy rendezett mátrixban
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: Egyidejű olvasás
A teljes API tesztelése Reflectionnel
Optimalizálás egy Parser Combinatorból memcpy-be
Ne kezeld az ösvényeket stringként
Törés egy játék Hash függvényben
Iterátorok lusta számolása
Megfejthetetlen hibák #6: Pretend Precision
My Bug, My Bad #3: Accidentally Attacking WarCraft 3
Collapsing Types vs Monads (followup)
Collapsing Futures: Könnyen használható, nehezen ábrázolható
Eventuális kivételek vs. programozás minimális funkcionális stílusban
A Flunf rejtélye
Magyarázd el, mintha ötös lennék: 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: Kérdezze meg az órát
A hüvelykujjszabály: Kérdezze meg az órát
A hüvelykujjszabály: Szándékosan gyengített módszerek használata
Összefogási szabály: Előfeltételeket explicit módon ellenőrizni kell
Hivatkozott listák gyorsabb összekapcsolása
Egeres útvonal simítása Jack Lumber számára
My Bug, My Bad #2: Sunk by Float
ismételd magad másképp
Grover kvantumkereső algoritmusa
Nem nullázható típusok követése vs C#
Optimalizálás Just in Time kifejezésfákkal
Mikor egy-Way Latency Doesn’t Matter
Determining exactly if/when/where a moving line intersected a moving point
Emulation 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
Decoupling shared control
Decoupling inline UI code
Linq to Collections: Beyond IEnumerable<T>
Publish your .Net könyvtár NuGet csomagként
Mikor a null nem elég: egy opciós típus a C# számára
Megfejthetetlen hibák #5: Readonly vagy sem
Minkowski összegek: példák
My Bug, My Bad #1: Fraktálgömbök
A Windows 8 törékeny felhasználói felület virtualizációjának megkerülése
Szögek bekapszulázása
Megfejthetetlen hibák #4: Kulcsok, amelyek nem
Hogyan használnék egyáltalán monádot (C#-ban)?
Hasznos/érdekes módszerek #1: Observable.WhenEach
Megtudhatatlan hibák #3: Stringing you along
Anonymous Implementation Classes – A Design Pattern for C#
Tasks for ActionScript 3 – Improving on Event-Driven Programming
Minkowski összegek és különbségek
Non-Nullable Types vs C#: A milliárd dolláros hiba kijavítása
Felfoghatatlan hibák #2: Kivágás
Skript sablonok és alaposztályok
Egységes betűtípusok kivonása
A “fantom típusok” használata a listák hosszának kódolásához a típusukba
A Reactive Extensions API konstruktív kritikája
Kvaternionok 3. rész
Kvaternionok 2. rész
Kvaternionok 1. rész
Megfejthetetlen hibák #1: Lehetnek dolgok! Lehetnek dolgok dolgokban! You can have …
Coroutines – More than you want to know
Asset Bundle Helper
A Visual Studio elmegy
.Net’s time travelling StopWatch
Introducing Catalyst

Savage Rose