Bestem præcis om/når/hvor/hvor en bevægelig linje skærer et bevægeligt punkt

november 3, 2021

Bestem præcis om/når/hvor/hvor en bevægelig linje skærer et bevægeligt punkt
Destination
Intuition
Model
Løsning
Generalisering
Summary
Diskuter på Reddit
Arkiv

postet af Craig Gidney den 5. februar 2013

Jeg forsøger at inkludere eksempelprojekter, når jeg udgiver biblioteker. I tilfældet med forgængelige samlinger var prøveprojektet faktisk et simpelt spil baseret på at skære linjer med musemarkøren:

Som en del af skrivningen af prøven måtte jeg løse problemet med at bestemme, om, hvornår og hvor musemarkøren blev fejet over en linje (eller omvendt). Min sædvanlige reference til geometrialgoritmer indeholdt ikke en løsning, så jeg udviklede selv en.

I dette indlæg vil jeg forklare en analytisk løsning på problemet. Løsningen er implementeret i en lille mængde kildekode (ca. 150 linjer, inklusive kommentarer og understøttende metoder/typer), som også er tilgængelig på github.

Destination

Det viser sig, at “skar musemarkøren den bevægelige linje?” er et af de magiske matematiske problemer, der starter med nogle relativt enkle begrænsninger, og som derefter ser ud til at blive ret kompliceret, når du løser det, men så annullerer eller kombinerer næsten alting sig i de sidste par trin, og du ender med noget absurd simpelt. (Når man så går tilbage for at kigge på løsningen, viser det sig, at der hele tiden var en nem vej.)

For reference og motivation vil jeg bare smide kødet af implementeringen lige her, før jeg forklarer den. Understregede ord er links til den tilsvarende kode 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);}

Jeg ved ikke med dig, men det faktum, at ovenstående kode løser problemet, forbløffer mig. Det virker for ligetil, og alligevel for usammenhængende. Burde der ikke være, ligesom, hjørnetilfælde? Desuden, hvor kommer de simple krydsprodukter fra? Hvordan kan det hjælpe at indføje dem i et kvadratisk polynomium? Dette… skal forklares.

Intuition

Lad os starte med at overveje nogle af de tilfælde, vi kan støde på, for at få en intuitiv fornemmelse for problemet. Animationen nedenfor viser flere forskellige mulige linjebevægelser:

Simpel: Begge endepunkter bevæger sig med samme hastighed og kun langs linjens normalvektor.
Sidelæns: Et degenereret tilfælde, hvor linjen bevæger sig langs sin egen længde.
Hævning: Det ene endepunkt bevæger sig horisontalt, mens det andet bevæger sig vertikalt (“hæver” og sænker linjen).
Dive: Det ene endepunkt bevæger sig diagonalt (‘dykker’ gennem midten), mens det andet bevæger sig vertikalt.

Varierende fejningstilfælde

Bemærk, at en linje kan feje et punkt 0, 1 eller 2 gange, da dens endepunkter bevæger sig med en konstant hastighed fra en position til en anden. Tilfældet “Raise” indeholder belejligt nok alle tre muligheder. Dette er intuitivt set grunden til, at løsningen indebærer en kvadratisk ligning (som kan have 0, 1 eller 2 forskellige reelle rødder).

En anden nyttig erkendelse er, at nogle af tilfældene, som f.eks. linjen, der bevæger sig med konstant hastighed eller står stille, vil svare til degenererede kvadratiske ligninger, hvor den højeste ordenskoefficient er nul (dvs. eller endog ). Vi er nødt til at medtage denne slags tilfælde i testene.

Model

For at et linjestykke fra til kan indeholde et punkt , skal to betingelser være opfyldt. For det første skal “offset”-vektoren fra til være parallel med “delta”-vektoren fra til . Vi kan repræsentere dette matematisk ved at kræve, at deres krydsprodukt skal være nul: $(c-p) \ gange (q-p) = 0$ . Dette garanterer, at ligger på den linje, man får ved at forlænge linjestykket i begge retninger (eller at man har et degenereret enkeltpunktslinjestykke). For det andet skal den skalare projektion af offset-vektoren på deltavektoren ligge i det rigtige område: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Dette garanterer, at ikke ligger forbi nogen af segmentets endepunkter.

Som tiden går fra til , vil vores linjesegment have fejet et punkt , hvis og kun hvis der findes et tidspunkt , hvor det aktuelle linjesegment indeholder . Da endepunkterne i vores linjesegment bevæger sig med en konstant hastighed, er den vej, de følger, også et linjesegment. Et endepunkt, der bevæger sig fra til , vil befinde sig i det lineært interpolerede punkt $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ til tidspunktet . Bemærk, at jeg for at spare plads forkorter til . Når vi sætter vores bevægelige punkter ind i vores formler for “linjestykke indeholder punkt”, kan vi se, at vi skal finde , der opfylder $0 \leq t \leq 1$ og $(c - (p_0 + p_d \cdot t)) \ gange ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ og $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$ .

Bemærk, at “et eller andet krydsprodukt skal være lig med 0″ ikke er den eneste måde at formulere problemet på. Det giver også mening at tænke på det som at finde et og , begge i intervallet , således at er resultatet af at lerpe begge endepunkter på tværs af deres vej med og derefter lerpe mellem endepunkterne med . Matematisk betyder det, at . Variablerne og svarer nogenlunde til “hvornår” og “hvor” et skæringspunkt opstår. Det er dog sværere at løse problemet i denne form, fordi ikke er isoleret i første omgang, så jeg vil bruge krydsproduktets indramning (i modsætning til første gang…).

Løsning

Krydsproduktet og punktproduktet har nogle meget fine egenskaber, som vil gøre det lettere at isolere . For det første fordeler de addition, hvilket betyder $u \times (v + w) = u \times v + u \times w$ og $u \cdot (v + w) = u \cdot v + u \cdot w$ . For det andet kan skalering foretages før eller efter begge produkter, hvilket betyder $(c \cdot u) \times v = c \cdot (u \times v)$ og $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , hvor er et reelt tal. Endelig er prikproduktet kommutativt, hvilket betyder $u \cdot v = v \cdot u$ , mens krydsproduktet er antikommutativt, hvilket betyder $u \times v = -v \times u$ .

Ved anvendelse af denne produktviden, og ved hjælp af en vis bagklogskab til at vide, at vi skal behandle bestemte underudtryk som individuelle variabler, kan vi omdanne vores krydsprodukt-er-nul-ligning til en kvadratisk ligning:

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

(Dette er uhyggeligt meget mere simpelt end den vej, jeg tog første gang.)

Ah, nu er det klart, hvor formen på kodeløsningen kom fra. Vi startede med et krydsprodukt lig nul (idet vi påstod, at vektoren fra linjen til punktet var parallel med linjen) og var nødt til at opdele produktet for at isolere summer af termer, der involverer forskellige potenser af . Dette giver naturligvis en kvadratisk ligning med koefficienter, der involverer krydsprodukter. Pænt!

Bemærk, at dette er en meget “robust” ligning, fordi vi aldrig har antaget noget om vektorerne eller skalarerne undervejs. F.eks. dividerer vi aldrig (eller annullerer implicit) med en variabel, så vi har ikke indført nogen lurende ikke-nul-tilstande.

Med den forenklede ligning er det at bestemme de mulige værdier af bare standard “løse kvadratisk polynomium”-ting. Vi er nødt til at håndtere hjørnetilfælde med nuller, hvilket gør koden lidt mere kompliceret, men det er bare kedelige case-by-case ting, så jeg vil bare linke til det.

Når vi kender en mulig værdi af , kan vi finde ud af præcis, hvor kollisionen fandt sted ved hjælp af den plug-t-into-line-segment-segment-punkt-inddæmningsformel, der blev nævnt et stykke tilbage: $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}$ . Jeg kalder denne formel for “lerp-projektionen” af på linjen til tidspunktet , fordi den returnerer den andel , som man skal lerpe med, fra linjens startpunkt til dens slutpunkt, for at få tilbage. Det er en praktisk lille metode til at udtrække:

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 endelig har og , skal vi kontrollere, at de ligger i intervallet . Hvis er uden for intervallet, vil kollisionen ikke forekomme i det aktuelle tidstrin. Hvis er uden for området, vil kollisionen ske på den forlængede linje, men ikke på linjesegmentet. Da og beskriver, hvor meget man skal lerpe for at finde ud af, hvornår/hvor kollisionen er sket, er det også nyttig information at returnere til opkalderen.

Generalisering

En vigtig detalje, som jeg endnu ikke har nævnt, er, at en bevægelig musemarkør naturligvis ikke svarer til et punkt. Heldigvis kan vi bare annullere musemarkørens bevægelse i løbet af det sidste tidstrin (hvis vi antager, at den er lineær) ved at trække den fra linjesegmentets bevægelse. Ikke alene reducerer dette systemet til et system, der kan løses, men de resulterende – og -værdier er gyldige uden nogen form for omvendt transformation. Brugen ser således ud:

// 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 potentiel komplikation er degenererede linjesegmenter, der ikke har nogen længde (hvor begge endepunkter er lige lange). Koden håndterer ikke eksplicit dette tilfælde, men vil handle som om det er umuligt at skære en linje, der i virkeligheden er et punkt. Beregningen af vil, hvis den nås, dividere med nul. Resultatet (enten -infinity, +infinity eller NaN) vil ikke bestå rækkeviddekontrollen.

Et andet aspekt, som jeg ikke har behandlet, er “skærevinklen”. I animationen, der viser de forskellige tilfælde, er de røde snit orienteret ved at lerpe mellem hastighederne for de to endepunkter med (når den resulterende hastighed er 0, vælges en tilfældig vinkel). Men jeg har også brugt alternative tilgange som “snitvinklen er punktets hastighed”. I bund og grund handler det om at bruge det, der ser godt ud og føles naturligt, i stedet for at forsøge at finde ud af den sande betydning af “snitvinkel”.

Summary

Dette problem bliver trivielt, så snart man anvender noget viden fra lineær algebra. Det er vel ikke så overraskende, da lineær algebra (og polynomier) dukker op overalt, især i geometri.

En naturlig generalisering af dette problem er at inddrage tykkelser. Linjer, der tegnes på skærme, er trods alt ikke uendeligt tynde. At have en tykkelse er også en god måde at reducere effekten af floating point-fejl, der afrundes i forskellige retninger i forskellige tidstrin. En anden nyttig ændring ville være muligheden for at håndtere paraboliske baner, da spilobjekter ofte er i frit fald. På den anden side er det nok nemmere bare at behandle “tykke linjer” som polygoner med tidstrin med konstant hastighed.

–

Diskuter på Reddit

–

Twisted Oak Studios tilbyder rådgivning og udvikling af højteknologiske interaktive projekter. Tjek vores portefølje, eller giv os et kald, hvis du har noget, som du synes, at nogle virkelig seje ingeniører bør hjælpe dig med.

Arkiv

strilanc
Hvad kvantecomputere gør hurtigere, med forbehold
Naming Things: Fail-Useful
Detecting Simple Cycles Forming, Faster
Third Party Bit Commitment
Angular Velocity is Simple
Collection Equality is Hard
Deadlocks in Practice: Hold ikke låse, mens du giver besked
Brute Force Parallelization
Et års udtalelser om Objective-C
Referencing Substrings Faster, without Leaking Memory
Not Crying Over Old Code
Exploring Universal Ternary Gates
Impraktisk eksperimenter #2: Sikring af Peer to Peer Fog of War mod Map Hacks
Afvikling af eksponentiel langsommelighed ved at opregne to gange
Anvendelse af udødelighed til at dræbe utilsigtede callbackcykler
Afbrydelsestokens (og kollapserende futures) til objektiv-C
Visualisering af egenvektorerne for en rotation
Collapsing Futures i Objective-C
Bug Hunting #1: Forvrøvlet lyd fra ende til anden
Impraktisk eksperiment #1: Repræsentation af tal som polynomier
Implementering af kvantepseudotelepati
Tænd for dine forbandede advarsler
Big-O gjort trivielt
Ubegribelige fejl #7: The Broken Oven
Solomonoffs Mad Scientist
Årlig blogging Roundup #1
Hvad er ikke en monade
Søgning af en sorteret matrix hurtigere
Hvordan man læser indlejrede ternære operatorer
Få Sublime Text 2 til at hoppe til den rigtige linje med Unity på OS X
Min fejl, My Bad #4: Reading Concurrently
Whole API Testing with Reflection
Optimering af en Parser Combinator til en 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
Et besøg på Execution Labs i Montréal
Transmuting Dice, Conserving Entropy
Rule of Thumb: Spørg efter uret
Tommelfingerregel: Spørg efter uret
Tommelfingerregel: Brug målrettet svækkede metoder
Tommelfingerregel: Brug klokken: Forudsætninger bør kontrolleres eksplicit
Intersecting Linked Lists Faster
Mouse Path Smoothing for Jack Lumber
My Bug, My Bad #2: Sænket af Float
Vis dig selv på en anden måde
Grovers kvantesøgningsalgoritme
Followup til ikke-nulbare typer vs C#
Optimering af Just in Time med udtrykstræer
Når man-Way Latency Doesn’t Matter
Bestemmelse af præcis, om/hvornår/hvor en bevægelig linje krydsede et bevægeligt punkt
Emulering af aktører i C# med Async/Await
Making an immutable queue with guaranteed constant time operations
Improving Checked Exceptions
Perishable Collections: Fordelene ved Removal-by-Lifetime
Afkobling af delt kontrol
Afkobling af inlinet UI-kode
Linq til Collections: Ud over IEnumerable<T>
Udgiv din .Net-bibliotek som en NuGet-pakke
Når null ikke er nok: en optionstype til C#
Uudgrundelige fejl #5: Readonly eller ej
Minkowski-summer: eksempler
Min fejl, min fejl #1: Fraktale kugler
Arbejde omkring den skrøbelige UI Virtualisering i Windows 8
Indkapsling af vinkler
Uudgrundelige fejl nr. 4: Nøgler, der ikke er
Hvordan skulle jeg overhovedet bruge en monade (i C#)?
Nyttige/interessante metoder #1: Observable.WhenEach
Uudgrundelige fejl #3: Stringing you along
Anonyme implementeringsklasser – et designmønster for C#
Opgaver for ActionScript 3 – forbedring af begivenhedsstyret programmering
Minkowski-summer og forskelle
Non-Nullable Types vs. C#: Fixing the Billion Dollar Mistake
Unfathomable Bugs #2: Slashing Out
Script-skabeloner og basisklasser
Unity font extraction
Brug af “Phantom Types” til at kode listelængder i deres type
Konstruktiv kritik af Reactive Extensions API
Kvaternioner del 3
Kvaternioner del 2
Kvaternioner del 1
Ubegribelige fejl nr. 1
Ubegribelige fejl nr: Du kan få ting! Man kan have ting I ting! Du kan have …
Coroutines – Mere end du vil vide
Asset Bundle Helper
The Visual Studio går væk
.Net’s tidsrejsende StopWatch
Introduktion af Catalyst

Savage Rose

Bestem præcis om/når/hvor/hvor en bevægelig linje skærer et bevægeligt punkt | Twisted Oak Studios Blog