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

november 3, 2021

Determining exactly if/when/where a moving line intersected a moving point
Bestemming
Intuïtie
Model
Oplossing
Generaliseren
Samenvatting
Discussieer op Reddit
Archief

posted by Craig Gidney on February 5, 2013

Ik probeer voorbeeldprojecten op te nemen wanneer ik bibliotheken publiceer. In het geval van bederfelijke verzamelingen was het voorbeeldproject eigenlijk een eenvoudig spel gebaseerd op het snijden van lijnen met de muisaanwijzer:

Als onderdeel van het schrijven van het voorbeeld moest ik het probleem oplossen om te bepalen of, wanneer, en waar de muisaanwijzer over een lijn werd geveegd (of vice versa). Mijn gebruikelijke referentie voor geometrie-algoritmen bevatte geen oplossing, dus ontwikkelde ik er zelf een.

In deze post zal ik een analytische oplossing voor het probleem uitleggen. De oplossing is geïmplementeerd in een kleine hoeveelheid broncode (ongeveer 150 regels, commentaar en ondersteunende methoden/typen meegerekend), ook beschikbaar op github.

Bestemming

Het blijkt dat “sneed de muisaanwijzer de bewegende lijn door?” een van die magische wiskundeproblemen is die begint met een aantal relatief eenvoudige beperkingen, dan vrij ingewikkeld lijkt te worden als je het oplost, maar dan annuleert of combineert bijna alles in de laatste paar stappen en eindig je met iets absurd eenvoudigs. (Dan, als je terug gaat om de oplossing te bekijken, blijkt dat er een gemakkelijke weg was de hele tijd.)

Voor referentie en motivatie, ga ik gewoon het vlees van de uitvoering hier dumpen, alvorens het uit te leggen. Onderstreepte woorden zijn links naar de bijbehorende code op 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);}

Ik weet niet hoe het met u zit, maar het feit dat de bovenstaande code het probleem oplost verbaast me. Het lijkt te eenvoudig, en toch te ongerelateerd. Zouden er geen, zeg maar, hoekgevallen moeten zijn? Plus, waar komen die eenvoudige kruisproducten vandaan? Hoe helpt het om ze in een kwadratisch polynoom te stoppen? Dit… zal moeten worden uitgelegd.

Intuïtie

Laten we beginnen met enkele gevallen die we kunnen tegenkomen, om een intuïtief gevoel voor het probleem te krijgen. De animatie hieronder toont verschillende mogelijke lijnbewegingen:

Eenvoudig: beide eindpunten bewegen met dezelfde snelheid, en alleen langs de normaalvector van de lijn.
Zijwaarts: een ontaard geval waarin de lijn langs zijn eigen lengte beweegt.
Opheffen: één eindpunt beweegt horizontaal terwijl het andere verticaal beweegt (‘opheffen’ en neerlaten van de lijn).
Duiken: het ene eindpunt beweegt diagonaal (‘duikt’ door het midden) terwijl het andere verticaal beweegt.

Verschillende veeggevallen

Merk op dat een lijn een punt 0, 1 of 2 keer kan vegen omdat de eindpunten in een constante snelheid van de ene positie naar de andere bewegen. Het geval “Raise” bevat handig alle drie mogelijkheden. Dit is intuïtief de reden waarom de oplossing een kwadratische vergelijking is (die 0, 1, of 2 verschillende reële wortels kan hebben).

Een ander nuttig besef is dat sommige gevallen, zoals de lijn die met een constante snelheid beweegt of stilstaat, zullen overeenkomen met ontaarde kwadratische vergelijkingen waar de hoogste orde coëfficiënt nul is (d.w.z. of zelfs ). We moeten dit soort gevallen in de tests opnemen.

Model

Om een lijnstuk van naar een punt te laten bevatten, moet aan twee voorwaarden worden voldaan. Ten eerste moet de “offset”-vector van naar evenwijdig zijn aan de “delta”-vector van naar . We kunnen dit wiskundig weergeven door te eisen dat hun kruisproduct nul is: $(c-p) \times (q-p) = 0$ . Dit garandeert dat op de lijn ligt die je krijgt door het lijnstuk in beide richtingen te verlengen (of dat je een ontaard enkelpuntig lijnstuk hebt). Ten tweede moet de scalaire projectie van de offsetvector op de deltavector in het juiste bereik liggen: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1$ . Dit garandeert dat niet voorbij een van de eindpunten van het lijnstuk ligt.

Als de tijd van naar gaat, zal ons lijnstuk een punt hebben geveegd als en slechts als er een tijdstip is waar het huidige lijnstuk bevat. Omdat de eindpunten van ons lijnstuk met een constante snelheid bewegen, is het pad dat zij volgen ook een lijnstuk. Een eindpunt dat zich verplaatst van naar zal op het lineair geïnterpoleerde punt $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ op tijdstip zijn. Merk op dat ik ga afkorten als om ruimte te besparen. Door onze bewegende punten in onze ‘lijnstuk bevat punt’ formules te stoppen vinden we dat voldoet aan $0 \leq t \leq 1$ en $(c - (p_0 + p_d \cdot t)) \((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0$ en $0 \leq s = \frac{(c-(p_0 + p_d \cdot t)) \((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}$ .

Merk op dat “een bepaald kruisproduct moet gelijk zijn aan 0” niet de enige manier is om het probleem op te lossen. Het is ook zinvol om het te zien als het vinden van een en , beide in het bereik , zodanig dat het resultaat is van het lieren van beide eindpunten over hun pad door en dan lieren tussen de eindpunten door . Wiskundig betekent dat . De variabelen en komen ruwweg overeen met “wanneer” en “waar” een snijpunt optreedt. Het is echter moeilijker om het probleem in deze vorm op te lossen, omdat in eerste instantie niet geïsoleerd is, dus zal ik het kruisproduct gebruiken om op te lossen (in tegenstelling tot de eerste keer…).

Oplossing

Het kruisproduct en het scalair product hebben een aantal zeer prettige eigenschappen die het gemakkelijker zullen maken om te isoleren. Ten eerste verdelen ze de optelling, dus $u \times (v + w) = u \times v + u \times w$ en $u \cdot (v + w) = u \cdot v + u \cdot w$ . Ten tweede kan er geschaald worden voor of na een van beide producten, dus $(c u) \times v = c \cdot (u \times v)$ en $(c u) \cdot v = c \cdot (u \cdot v)$ , waarbij een reëel getal is. Tenslotte is het scalair product commutatief, dus $u \cdot v = v \cdot u$ , terwijl het crossproduct anticommutatief is, dus $u \times v = -v \times u$ .

Door deze productkennis toe te passen, en door achteraf te weten dat we bepaalde deeluitdrukkingen als afzonderlijke variabelen moeten behandelen, kunnen we onze kruisproduct-is-nulvergelijking omzetten in een kwadratische vergelijking:

$begin{align*} 0 =(c - (p_0 + p_d \t)) \maal ((q_0 + q_d \dot t)-(p_0 + p_d \d t)) \waar; a = c - p_0 waar; b = -p_d waar; c = q_0 - p_0 waar; waar; b = -p_d waar; c = q_0 - p_0 waar; d = -(q_d - p_d) = a maal c + a maal d + b maal c + b maal d = t = t = t^2 (b maal d) + t = (a maal d) + t = t = (b maal d) + t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t = t + t = t = t = t = t = t = t = t = t = t = t \maal d + b maal c) + (a maal c) Einde{align*}$

(Dit is hilarisch eenvoudiger dan de route die ik de eerste keer nam.)

Ah, nu is het duidelijk waar de vorm van de code-oplossing vandaan kwam. We begonnen met een kruisproduct gelijk aan nul (met de bewering dat de vector van de lijn naar het punt evenwijdig was met de lijn) en moesten het product opsplitsen om sommen van termen met verschillende machten van te isoleren. Dit levert natuurlijk een kwadratische vergelijking op met coëfficiënten met kruisproducten. Netjes!

Merk op dat dit een zeer “robuuste” vergelijking is, omdat we onderweg nooit iets over de vectoren of scalaren hebben aangenomen. We hebben bijvoorbeeld nooit gedeeld (of impliciet geannuleerd) door een variabele, dus we hebben geen op de loer liggende niet-nul voorwaarden geïntroduceerd.

Met de vereenvoudigde vergelijking is het bepalen van de mogelijke waarden van gewoon standaard “los kwadratisch polynoom op” spul. We moeten omgaan met hoekgevallen met nullen, wat de code een beetje ingewikkelder maakt, maar het is gewoon saai geval per geval spul, dus ik zal gewoon linken naar het.

Zodra we een mogelijke waarde van weten, kunnen we uitvinden waar de botsing zich precies voordeed met behulp van de plug-t-into-lijn-segment-punt-beperkingsformule die een tijdje terug werd genoemd: $s = c-(p_0 + p_d t)) \((q_0 + q_d t)-(p_0 + p_d t))}{((q_0 + q_d t)-(p_0 + p_d t))^2}$ . Ik noem deze formule de “lerp projectie” van op de lijn op tijdstip , want het geeft de verhouding om mee te lerperen, van het beginpunt van de lijn naar het eindpunt, om terug te krijgen. Het is een handige kleine methode om te extraheren:

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}

Eindelijk, als we en hebben, moeten we controleren of ze in het bereik liggen. Als buiten het bereik ligt, zal de botsing niet optreden tijdens de huidige tijdstap. Als buiten bereik is, dan zal de botsing optreden op de verlengde lijn, maar niet op het lijnstuk. Aangezien en beschrijven hoeveel te lerp om te vinden wanneer/waar de botsing plaatsvond, is het ook nuttige informatie om terug te geven aan de aanroeper.

Generaliseren

Een belangrijk detail dat ik nog niet genoemd heb is dat een bewegende muisaanwijzer natuurlijk niet overeenkomt met een punt. Gelukkig kunnen we de beweging van de muisaanwijzer over de laatste tijdstap (in de veronderstelling dat deze lineair is) gewoon elimineren door deze af te trekken van de beweging van het lijnstuk. Dit reduceert niet alleen het systeem tot een oplosbaar systeem, maar de resulterende en waarden zijn geldig zonder enige vorm van inverse transformatie. Het gebruik ziet er als volgt uit:

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

Een mogelijke complicatie zijn ontaarde lijnstukken die geen lengte hebben (waarbij beide eindpunten gelijk zijn). De code behandelt dit geval niet expliciet, maar zal doen alsof het snijden van een lijnstuk dat eigenlijk een punt is, onmogelijk is. De berekening van , als die bereikt wordt, zal delen door nul. Het resultaat (ofwel – oneindig, + oneindig, of NaN) zal de bereikcontrole niet doorstaan.

Een ander aspect dat ik nog niet heb behandeld is de ‘snijhoek’. In de animatie van de verschillende gevallen zijn de rode sneden georiënteerd door de snelheden van de twee eindpunten te lerpen met (als de resulterende snelheid 0 is, wordt een willekeurige hoek gekozen). Maar ik heb ook alternatieve benaderingen gebruikt zoals “de snijhoek is de snelheid van het punt”. Eigenlijk is het een kwestie van gebruiken wat er goed uitziet en natuurlijk aanvoelt, in plaats van te proberen de ware betekenis van “snijhoek” te achterhalen.

Samenvatting

Dit probleem wordt triviaal zodra je wat kennis uit de lineaire algebra toepast. Dat is niet zo verwonderlijk, want lineaire algebra (en veeltermen) kom je overal tegen, vooral in de meetkunde.

Een natuurlijke veralgemening van dit probleem is het opnemen van diktes. Lijnen op beeldschermen zijn immers niet oneindig dun. Het hebben van een dikte is ook een goede manier om het effect te verminderen van drijvende kommafouten die in verschillende richtingen worden afgerond tijdens verschillende tijdstappen. Een andere nuttige verandering zou de mogelijkheid zijn om parabolische paden te behandelen, aangezien spelobjecten vaak in vrije val zijn. Aan de andere kant denk ik dat het waarschijnlijk makkelijker is om ‘dikke lijnen’ gewoon te behandelen als polygonen met constante snelheid tijdstappen.

–

Discussieer op Reddit

–

Twisted Oak Studios biedt consulting en ontwikkeling voor high-tech interactieve projecten. Bekijk ons portfolio, of geef ons een gil als u iets heeft waarvan u denkt dat een paar echt radicale ingenieurs u zouden moeten helpen.

Archief

strilanc
Wat Quantum Computers Sneller Doen, met Caveats
Dingen Benoemen: 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
Een jaar aan meningen over Objective-C
Referencing Substrings Faster, without Leaking Memory
Niet huilen over oude code
Exploring Universal Ternary Gates
Impractical Experiments #2: Peer to Peer Fog of War beveiligen tegen Map Hacks
Exponentiële vertraging bereiken door twee keer op te tellen
Onsterfelijkheid gebruiken om toevallige terugbelcycli te doden
Tokens voor annulering (en ineenstortende futures) voor Objective-C
Visualiseren van de Eigenvectoren van een Rotatie
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: 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, Mijn fout #4: Gelijktijdig lezen
Volledige API testen met Reflectie
Een Parser Combinator in een memcpy veranderen
Paden niet als Strings behandelen
Een Toy Hash Functie breken
Iterators lui tellen
Onbegrijpelijke bugs #6: Pretendentieuze Precisie
Mijn Bug, Mijn Slechte #3: Per ongeluk Aanvallen op WarCraft 3
Collapsing Types vs Monads (vervolg)
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
Een bezoek aan Execution Labs in Montréal
Transmuting Dice, Conserving Entropy
Rule of Thumb: Vraag naar de klok
Vuistregel: Gebruik Doelbewust Verzwakte Methoden
Vuistregel: Preconditions Should be Checked Explicitly
Intersecting Linked Lists Faster
Mouse Path Smoothing for Jack Lumber
My Bug, My Bad #2: Sunk by Float
Herhaal jezelf anders
Grover’s Quantum Search Algorithm
Opvolgen van niet-Nullable Types vs C#
Optimaliseren van Just in Time met Expression Trees
Wanneer One-Way Latency doesn’t Matter
Precies bepalen of/wanneer/waar een bewegende lijn een bewegend punt snijdt
Emuleren van Actors in C# met Async/Await
Een onveranderlijke wachtrij maken met gegarandeerde constante tijd operaties
Verbeteren van Gecontroleerde Excepties
Veranderlijke Collecties: De voordelen van Removal-by-Lifetime
Ontkoppelen van gedeelde controle
Ontkoppelen van inline UI code
Linq naar Collections: Voorbij IEnumerable<T>
Publiceer uw .Net-bibliotheek als NuGet-pakket
Wanneer null niet genoeg is: een optietype voor C#
Ondoorgrondelijke bugs #5: Readonly of niet
Minkowski-sommen: voorbeelden
Mijn bug, mijn fout #1: Fractal Spheres
Working around the brittle UI Virtualization in Windows 8
Encapsulating Angles
Unfathomable Bugs #4: Keys that aren’t
Hoe zou ik überhaupt een monad (in C#) kunnen gebruiken?
Bruikbare/interessante methoden #1: Observable.WhenEach
Ondoorgrondelijke bugs #3: Je aan het lijntje houden
Anonieme implementatieklassen – een ontwerppatroon voor C#
Taken voor ActionScript 3 – Verbeteren van Event-Driven Programming
Minkowski sommen en verschillen
Niet-Nullable Types vs C#: Fixing the Billion Dollar Mistake
Unfathomable Bugs #2: Afsplitsen
Script templates en base classes
Unity font extraction
Het gebruik van “Phantom Types” om lijstlengtes te coderen in hun type
Constructieve kritiek op de Reactive Extensions API
Quaternions deel 3
Quaternions deel 2
Quaternions deel 1
Unfathomable Bugs #1: Je kunt dingen hebben! Je kunt dingen IN dingen hebben! Je kunt …
Coroutines – Meer dan je wilt weten
Asset Bundle Helper
De Visual Studio gaat weg
.Net’s tijdreizende StopWatch
Inleiding tot Catalyst

Savage Rose

Determining exactly if/when/where a moving line intersected a moving point | Twisted Oak Studios Blog