Bestämma exakt om/när/var en rörlig linje skar en rörlig punkt

november 3, 2021

Bestämma exakt om/när/var en rörlig linje skar en rörlig punkt
Destination
Intuition
Modell
Lösning
Generalisering
Sammanfattning
Diskutera på Reddit
Arkiv

postat av Craig Gidney den 5 februari 2013

Jag försöker inkludera exempelprojekt när jag publicerar bibliotek. I fallet med perishable collections var exempelprojektet faktiskt ett enkelt spel baserat på att klippa linjer med muspekaren:

Som en del av skrivandet av exemplet var jag tvungen att lösa problemet med att avgöra om, när och var muspekaren sveptes över en linje (eller vice versa). Min vanliga referens för geometrialgoritmer innehöll ingen lösning, så jag utvecklade en själv.

I det här inlägget kommer jag att förklara en analytisk lösning på problemet. Lösningen implementeras i en liten mängd källkod (cirka 150 rader, med kommentarer och stödjande metoder/typer inräknade), som också finns tillgänglig på github.

Destination

Det visar sig att ”klippte muspekaren den rörliga linjen?” är ett av de där magiska matematiska problemen som börjar med några relativt enkla begränsningar, som sedan tycks bli ganska komplicerat när du löser det, men sedan upphävs eller kombineras nästan allting i de sista stegen och du får till slut något absurt enkelt. (När man sedan går tillbaka för att titta på lösningen visar det sig att det fanns en enkel väg hela tiden.)

För referens och motivation kommer jag bara att dumpa köttet av genomförandet här, innan jag förklarar det. Understrukna ord är länkar till motsvarande kod på 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);}

Jag vet inte hur det är med dig, men det faktum att ovanstående kod löser problemet förvånar mig. Det verkar alltför enkelt, men ändå alltför orelaterat. Borde det inte finnas, liksom, hörnfall? Dessutom, var kommer dessa enkla korsprodukter ifrån? Hur hjälper det att föra in dem i ett kvadratiskt polynom? Detta… måste förklaras.

Intuition

Låt oss börja med att överväga några av de fall vi kan stöta på, för att få en intuitiv känsla för problemet. Animationen nedan visar flera olika möjliga linjebefodringar:

Enkel: båda ändpunkterna rör sig med samma hastighet och endast längs linjens normalvektor.
Sidledes: ett degenererat fall där linjen rör sig längs sin egen längd.
Upphöjning: den ena ändpunkten rör sig horisontellt medan den andra rör sig vertikalt (”höja” och sänka linjen).
Dykning: Den ena ändpunkten rör sig diagonalt (”dyker” genom mitten) medan den andra rör sig vertikalt.

Varianta svepningsfall

Bemärk att en linje kan svepa en punkt 0, 1 eller 2 gånger då dess ändpunkter rör sig i en konstant takt från en position till en annan. Fallet ”Höjning” innehåller lämpligen alla tre möjligheterna. Detta är intuitivt sett anledningen till att lösningen innefattar en kvadratisk ekvation (som kan ha 0, 1 eller 2 distinkta reella rötter).

En annan användbar insikt är att en del av fallen, som linjen som rör sig med konstant hastighet eller står stilla, kommer att motsvara degenererade kvadratiska ekvationer där koefficienten av högsta ordning är noll (dvs. eller till och med ). Vi måste inkludera denna typ av fall i testerna.

Modell

För att ett linjesträck från till ska innehålla en punkt måste två villkor vara uppfyllda. För det första måste ”offset”-vektorn från till vara parallell med ”delta”-vektorn från till . Vi kan representera detta matematiskt genom att kräva att deras korsprodukt är noll: $(c-p) \times (q-p) = 0$ . Detta garanterar att ligger på den linje man får genom att förlänga linjesträckan i båda riktningarna (eller att man har en degenererad enpunktslinjesträckning). För det andra måste den skalära projektionen av förskjutningsvektorn på deltavektorn ligga i rätt intervall: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Detta garanterar att inte är förbi någon av segmentets slutpunkter.

Som tiden går från till kommer vårt linjesegment att ha svept över en punkt om och endast om det finns en tidpunkt där det aktuella linjesegmentet innehåller . Eftersom ändpunkterna i vårt linjesegment rör sig med en konstant hastighet är den väg de följer också ett linjesegment. En ändpunkt som rör sig från till kommer att befinna sig i den linjärt interpolerade punkten $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ vid tiden . Observera att jag kommer att förkorta till för att spara utrymme. Genom att sätta in våra rörliga punkter i våra formler om att ett linjesegment innehåller en punkt får vi veta att vi måste hitta som uppfyller $0 \leq t \leq 1$ och $(c - (p_0 + p_d \cdot t)). \times ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ och $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$ .

Notera att ”någon korsprodukt måste vara lika med 0″ inte är det enda sättet att formulera problemet. Det är också meningsfullt att tänka på det som att hitta en och , båda i intervallet , så att är resultatet av att lerpa båda ändpunkterna över sin väg med och sedan lerpa mellan ändpunkterna med . Matematiskt betyder det . Variablerna och motsvarar ungefär ”när” och ”var” en skärningspunkt inträffar. Det är dock svårare att lösa problemet i den här formen, eftersom inte är isolerad till en början, så jag kommer att använda korsproduktsinramningen (till skillnad från vad jag gjorde första gången…).

Lösning

Kors- och prickprodukten har några mycket trevliga egenskaper som kommer att göra det lättare att isolera . För det första distribuerar de addition, vilket innebär $u \times (v + w) = u \times v + u \times w$ och $u \cdot (v + w) = u \cdot v + u \cdot w$ . För det andra kan skalning göras före eller efter någon av produkterna, vilket innebär $(c \cdot u) \times v = c \cdot (u \times v)$ och $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , där är ett verkligt tal. Slutligen är punktprodukten kommutativ, vilket innebär $u \cdot v = v \cdot u$ , medan korsprodukten är antikommutativ, vilket innebär $u \times v = -v \times u$ .

Med hjälp av denna produktkunskap, och med hjälp av lite efterklokhet för att veta att vi ska behandla särskilda deluttryck som individuella variabler, kan vi omvandla vår korsprodukt-är-noll ekvation till en kvadratisk ekvation:

$\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) \\\;\;\;\;\;\;\;\;\;\;\;\;\;var\;\; a = c - p_0 \\\;\;\;\;\;\;\;\;\;var\;\; b = -p_d \\\;\;\;\;\;\;\;var\;\; \;\;\;\; c = q_0 - p_0 \\;\;\;\;\;\;\;\;\;\;var\;\; 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*}$

(Detta är otroligt mycket enklare än den väg jag tog första gången.)

Ah, nu är det tydligt varifrån formen för kodlösningen kom. Vi började med en korsprodukt som var lika med noll (vilket hävdade att vektorn från linjen till punkten var parallell med linjen) och var tvungna att dela upp produkten för att isolera summor av termer som involverar olika potenser av . Detta ger naturligtvis en kvadratisk ekvation med koefficienter som involverar korsprodukter. Snyggt!

Bemärk att detta är en mycket ”robust” ekvation, eftersom vi aldrig antog något om vektorerna eller skalorna längs vägen. Till exempel dividerar vi aldrig (eller upphäver implicit) med en variabel, så vi har inte infört några lurande icke-nollvillkor.

Med den förenklade ekvationen är det bara standardmässigt att bestämma de möjliga värdena för genom att ”lösa ett kvadratiskt polynom”. Vi måste hantera hörnfall med nollor, vilket gör koden lite mer komplicerad, men det är bara tråkiga saker från fall till fall så jag länkar bara till det.

När vi väl känner till ett möjligt värde på kan vi ta reda på exakt var kollisionen inträffade genom att använda formeln för att plugga in i linje-segment-punkt-innehållning som nämndes för ett tag sedan: $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}$ . Jag kallar denna formel för ”lerp-projektionen” av på linjen vid tiden , eftersom den återger proportionen att lerpa med, från linjens startpunkt till dess slutpunkt, för att få tillbaka . Det är en praktisk liten metod för att extrahera:

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}

När vi väl har och måste vi slutligen kontrollera att de ligger inom intervallet . Om ligger utanför intervallet kommer kollisionen inte att inträffa under det aktuella tidssteget. Om ligger utanför intervallet kommer kollisionen att inträffa på den förlängda linjen, men inte på linjesegmentet. Eftersom och beskriver hur mycket man ska lerpa för att hitta när/var kollisionen inträffade är det också användbar information att återge till anroparen.

Generalisering

En viktig detalj som jag inte har nämnt ännu är att en rörlig muspekare uppenbarligen inte motsvarar en punkt. Som tur är kan vi bara upphäva muspekarens rörelse under det senaste tidssteget (om vi antar att den är linjär) genom att dra av den från linjesegmentets rörelse. Detta reducerar inte bara systemet till ett lösbart system, utan de resulterande – och -värdena är giltiga utan någon form av invers transformation. Användningen ser ut så här:

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

En potentiell komplikation är degenererade linjesegment som inte har någon längd (där båda ändpunkterna är lika långa). Koden hanterar inte uttryckligen detta fall, men kommer att agera som om det är omöjligt att klippa en linje som i själva verket är en punkt. Beräkningen av , om den nås, kommer att dividera med noll. Resultatet (antingen -infinity, +infinity eller NaN) kommer att misslyckas med intervallkontrollen.

En annan aspekt som jag inte har behandlat är ”snittvinkeln”. I animationen som visar de olika fallen är de röda snitten orienterade genom att man tar ut en lerping mellan hastigheterna för de två ändpunkterna med (när den resulterande hastigheten är 0, väljs en slumpmässig vinkel). Men jag har också använt alternativa tillvägagångssätt som ”snittvinkeln är punktens hastighet”. I grund och botten handlar det om att använda det som ser bra ut och känns naturligt i stället för att försöka ta reda på den verkliga innebörden av ”snittvinkel”.

Sammanfattning

Det här problemet blir trivialt så snart man tillämpar lite kunskap från linjär algebra. Jag antar att det inte är så förvånande, eftersom linjär algebra (och polynomier) dyker upp överallt, särskilt i geometri.

En naturlig generalisering av detta problem är att inkludera tjocklekar. Linjer som dras på skärmar är trots allt inte oändligt tunna. Att ha en tjocklek är också ett bra sätt att minska effekten av att fel med flytande punkter avrundas i olika riktningar under olika tidssteg. En annan användbar förändring skulle vara möjligheten att hantera paraboliska banor, eftersom spelobjekt ofta befinner sig i fritt fall. Å andra sidan är det nog enklare att bara behandla ”tjocka linjer” som polygoner med tidssteg med konstant hastighet.

–

Diskutera på Reddit

–

Twisted Oak Studios erbjuder konsultation och utveckling av interaktiva högteknologiska projekt. Kolla in vår portfölj eller hör av dig till oss om du har något som du tycker att några riktigt häftiga ingenjörer borde hjälpa dig med.

Arkiv

strilanc
What Quantum Computers Do Faster, with Caveats
Naming Things: Fail-Useful
Detektering av enkla cykler som bildas, snabbare
Tredje parts bit-åtagande
Angular Velocity is Simple
Collection Equality is Hard
Deadlocks in Practice: Håll inte lås när du anmäler
Brute Force Parallelization
Ett års åsikter om Objective-C
Snabbare referenstagning av understrängar utan att läcka minne
Inte gråta över gammal kod
Utforskande av universella ternära portar
Opraktisk experiment nr 2: ”Ternary Gates”: Säkra peer-to-peer-krigsdimmor mot karthackning
Att uppnå exponentiell fördröjning genom att räkna upp två gånger
Användning av odödlighet för att döda oavsiktliga återkallningscykler
Avbrytande av Tokens (och kollapsande Futures) för Mål-C
Visualisera egenvektorerna för en rotation
Collapsing Futures i Objective-C
Bug Hunting #1: Garbled Audio from End to End
Impraktiska experiment #1: Representing Numbers as Polynomials
Implementing Quantum Pseudo-Telepathy
Turn On Your Damn Warnings
Big-O Made Trivial
Unfathomable Bugs #7: The Broken Oven
Solomonoffs Mad Scientist
Årliga bloggrundan #1
Vad är inte en monad
Söka en sorterad matris snabbare
Hur man läser inbäddade ternära operatorer
För att få Sublime Text 2 att hoppa till rätt rad med Unity på OS X
Mitt fel, My Bad #4: Läsning samtidigt
Testning av hela API:n med Reflection
Optimering av en Parser Combinator till en memcpy
Behandla inte sökvägar som strängar
Brytning av en leksakshashfunktion
Räkning av Iteratorer på ett slöseriaktigt sätt
Undgrävbara buggar #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
Ett besök på Execution Labs i Montréal
Transmuting Dice, Conserving Entropy
Rule of Thumb: Fråga efter klockan
Tumsregel: Fråga efter klockan
Tumsregel: Använd avsiktligt försvagade metoder
Tumsregel: Använd klockan:
Intersecting Linked Lists Faster
Mouse Path Smoothing for Jack Lumber
My Bug, My Bad #2: Sunk by Float
Upprepa dig själv på ett annat sätt
Grovers kvantsökalgoritm
Följning av icke-nollbara typer mot C#
Optimering av Just in Time med uttrycksträd
När man-Way Latency Doesn’t Matter
Bestämma exakt om/när/var en rörlig linje korsade en rörlig punkt
Emulera aktörer i C# med Async/Await
Göra en oföränderlig kö med garanterad konstant tid för operationer
Förbättra kontrollerade undantag
Perishable Collections: Fördelarna med borttagning efter livstid
Frånkoppling av delad kontroll
Frånkoppling av inlinerad UI-kod
Linq till samlingar: Bortom IEnumerable<T>
Publicera din .Net-bibliotek som ett NuGet-paket
När null inte räcker: en alternativtyp för C#
Unfathomable Bugs #5: Readonly or not
Minkowski-summor: exempel
My Bug, My Bad #1: Fraktal Spheres
Virtualisering i Windows 8
Encapsulating Angles
Unfathomable Bugs #4: Keys that aren’t
Hur skulle jag ens kunna använda en monad (i C#)?
Nyttiga/intressanta metoder #1: Observable.WhenEach
Outgrundliga fel #3: Stringing you along
Anonyma implementeringsklasser – ett designmönster för C#
Tasker för ActionScript 3 – Förbättring av händelsestyrd programmering
Minkowskisummor och skillnader
Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
Unfathomable Bugs #2:
Skriptmallar och basklasser
Enhetligt utdrag av teckensnitt
Brukta ”fantomtyper” för att koda listlängder i deras typ
Konstruktiv kritik av Reactive Extensions API
Quaternions del 3
Quaternions del 2
Quaternions del 1
Unfathomable Bugs #1: Du kan ha saker! Man kan ha saker i saker! Du kan ha …
Coroutines – Mer än du vill veta
Asset Bundle Helper
The Visual Studio goes away
.Nets tidsresande StopWatch
Introducing Catalyst

Savage Rose

Bestämma exakt om/när/var en rörlig linje skar en rörlig punkt | Twisted Oak Studios Blog