Determinarea exactă a intersecției dintre o linie în mișcare și un punct în mișcare

noiembrie 3, 2021

Determinarea exactă a intersecției dintre o linie în mișcare și un punct în mișcare
Destinație
Intuiție
Modelul
Soluție
Generalizarea
Rezumat
Discută pe Reddit
Arhivă

postat de Craig Gidney la 5 februarie 2013

Încerc să includ exemple de proiecte atunci când public biblioteci. În cazul colecțiilor perisabile, proiectul de eșantionare a fost de fapt un joc simplu bazat pe tăierea liniilor cu indicatorul mouse-ului:

Ca parte a scrierii eșantionului, a trebuit să rezolv problema de a determina dacă, când și unde a fost măturat indicatorul mouse-ului peste o linie (sau viceversa). Referința mea obișnuită pentru algoritmi de geometrie nu conținea o soluție, așa că am dezvoltat una eu însumi.

În această postare voi explica o soluție analitică a problemei. Soluția este implementată într-o cantitate mică de cod sursă (aproximativ 150 de linii, numărând comentariile și metodele/tipurile de suport), disponibilă și pe github.

Destinație

Se pare că „a tăiat indicatorul mouse-ului linia în mișcare?” este una dintre acele probleme matematice magice care începe cu niște constrângeri relativ simple, apoi pare să devină destul de complicată pe măsură ce o rezolvi, dar apoi aproape totul se anulează sau se combină în ultimii pași și ajungi la ceva absurd de simplu. (Apoi, când te întorci să te uiți peste soluție, se dovedește că a existat o cale ușoară tot timpul.)

Pentru referință și motivație, am să arunc carnea implementării chiar aici, înainte de a o explica. Cuvintele subliniate sunt linkuri către codul corespunzător de pe 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);}

Nu știu despre voi, dar faptul că codul de mai sus rezolvă problema mă uimește. Pare prea simplu și, totuși, prea puțin legat. Nu ar trebui să existe, cum ar fi, cazuri colaterale? În plus, de unde au apărut acele produse încrucișate simple? Cum ajută introducerea lor într-un polinom quadratic? Acest lucru… va trebui să fie explicat.

Intuiție

Să începem prin a lua în considerare câteva dintre cazurile pe care le-am putea întâlni, pentru a ne face o idee intuitivă despre această problemă. Animația de mai jos prezintă mai multe mișcări posibile ale liniei:

Simplu: ambele puncte terminale se deplasează cu aceeași viteză și numai de-a lungul vectorului normal al liniei.
În lateral: un caz degenerat în care linia se deplasează de-a lungul propriei sale lungimi.
Ridicare: un punct terminal se deplasează pe orizontală în timp ce celălalt se deplasează pe verticală („ridicarea” și coborârea liniei).
Scufundare: un punct terminal se deplasează pe diagonală („scufundându-se” prin mijloc) în timp ce celălalt se deplasează pe verticală.

Diverse cazuri de măturare

Observați că o dreaptă poate mătura un punct de 0, 1 sau 2 ori pe măsură ce punctele sale terminale se deplasează cu o viteză constantă de la o poziție la alta. Cazul „Raise” conține în mod convenabil toate cele trei posibilități. Acesta este, în mod intuitiv, motivul pentru care soluția implică o ecuație pătratică (care poate avea 0, 1 sau 2 rădăcini reale distincte).

O altă constatare utilă este aceea că unele dintre cazuri, cum ar fi linia care se deplasează cu viteză constantă sau care stă pe loc, vor corespunde unor ecuații pătratice degenerate în care coeficientul de ordinul cel mai înalt este zero (adică sau chiar ). Trebuie să includem acest tip de cazuri în teste.

Modelul

Pentru ca un segment de dreaptă de la la să conțină un punct , trebuie să fie îndeplinite două condiții. În primul rând, vectorul „offset” de la la trebuie să fie paralel cu vectorul „delta” de la la . Putem reprezenta matematic acest lucru cerând ca produsul lor încrucișat să fie zero: $(c-p) \times (q-p) = 0$ . Acest lucru garantează că se află pe linia pe care o obțineți prin prelungirea segmentului de dreaptă în ambele direcții (sau că aveți un segment de dreaptă degenerat cu un singur punct). În al doilea rând, proiecția scalară a vectorului de decalaj pe vectorul delta trebuie să fie în intervalul corect: $0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2}}. \leq 1$ . Acest lucru garantează că nu este trecut de niciunul dintre punctele terminale ale segmentului.

Cum timpul trece de la la , segmentul nostru de dreaptă va fi măturat un punct dacă și numai dacă există un moment în care segmentul de dreaptă curent conține . Deoarece punctele de capăt ale segmentului nostru de dreaptă se deplasează cu o viteză constantă, traiectoria pe care o urmează este, de asemenea, un segment de dreaptă. Un punct final care se deplasează de la la se va afla în punctul interpolat liniar $lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t$ la momentul . Rețineți că voi prescurta ca pentru a economisi spațiu. Introducând punctele noastre în mișcare în formulele „segmentul de dreaptă conține un punct” ne spune că trebuie să găsim care să satisfacă $0 \leq t \leq 1$ și $(c - (p_0 + p_d \cdot t)) \times ((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} \leq 1$ .

Rețineți că „un anumit produs încrucișat trebuie să fie egal cu 0″ nu este singurul mod de a formula problema. De asemenea, are sens să ne gândim la ea ca la găsirea unui și a unui , ambii în intervalul , astfel încât să fie rezultatul lerpării ambelor puncte de capăt pe traseul lor cu și apoi lerparea între punctele de capăt cu . Matematic, aceasta înseamnă . Variabilele și corespund în linii mari „când” și „unde” are loc o intersecție. Cu toate acestea, este mai greu de rezolvat problema în această formă, deoarece nu este izolată inițial, așa că voi folosi încadrarea în produsul încrucișat (spre deosebire de prima dată…).

Soluție

Produsul încrucișat și produsul punctat au niște proprietăți foarte bune care vor face mai ușor de izolat . În primul rând, ele distribuie adunarea, ceea ce înseamnă $u \times (v + w) = u \times v + u \times w$ și $u \cdot (v + w) = u \cdot v + u \cdot w$ . În al doilea rând, scalarea se poate face înainte sau după oricare dintre produse, ceea ce înseamnă $(c \cdot u) \times v = c \cdot (u \times v)$ și $(c \cdot u) \cdot v = c \cdot (u \cdot v)$ , unde este un număr real. În sfârșit, produsul punct este comutativ, ceea ce înseamnă $u \cdot v = v \cdot u$ , în timp ce produsul încrucișat este anticomutativ, ceea ce înseamnă $u \times v = -v \times u$ .

Aplicând această cunoaștere a produsului, și folosind o anumită retrospectivă pentru a ști să tratăm anumite subexpresii ca variabile individuale, putem transforma ecuația noastră cu produsul încrucișat este zero într-o ecuație pătratică:

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

(Acest lucru este ilar mai simplu decât ruta pe care am urmat-o prima dată.)

Ah, acum este clar de unde a venit forma soluției de cod. Am pornit de la un produs încrucișat egal cu zero (afirmând că vectorul de la dreaptă la punct este paralel cu dreapta) și a trebuit să împărțim produsul pentru a izola sumele de termeni care implică diferite puteri ale lui . Astfel se obține în mod natural o ecuație pătratică cu coeficienți care implică produse încrucișate. Neat!

Rețineți că aceasta este o ecuație foarte „robustă”, deoarece nu am presupus niciodată nimic despre vectori sau scalari pe parcurs. De exemplu, nu am împărțit niciodată (sau implicit nu am anulat) cu o variabilă, deci nu am introdus nicio condiție de non-zero care să stea la pândă.

Cu ecuația simplificată, determinarea valorilor posibile ale lui este doar o chestie standard de „rezolvare a polinomiilor pătratici”. Trebuie să ne ocupăm de cazurile de colț cu zerouri, ceea ce face codul un pic mai complicat, dar sunt doar chestii plictisitoare de la caz la caz, așa că voi face doar un link către el.

După ce cunoaștem o valoare posibilă a lui , putem afla exact unde a avut loc coliziunea folosind formula „plug-t-in-into-line-segment-point-containment” menționată cu ceva timp în urmă: $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}$ . Numesc această formulă „proiecția lerp” a lui pe linia de la momentul , deoarece ea returnează proporția cu care trebuie să se facă lerp, de la punctul de început al liniei până la punctul său final, pentru a obține înapoi. Este o mică metodă la îndemână pentru a extrage:

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 cele din urmă, odată ce avem și , trebuie să verificăm dacă acestea sunt în intervalul . Dacă este în afara intervalului, atunci coliziunea nu va avea loc în timpul pasului de timp curent. Dacă este în afara intervalului, atunci coliziunea va avea loc pe linia extinsă, dar nu și pe segmentul de linie. Din moment ce și descriu cât de mult trebuie să lerp pentru a afla când/unde a avut loc coliziunea, este, de asemenea, o informație utilă pentru a o returna apelantului.

Generalizarea

Un detaliu important pe care nu l-am menționat încă este că un vârf de mouse în mișcare nu corespunde, în mod evident, unui punct. Din fericire, putem pur și simplu să anulăm mișcarea indicatorului mouse-ului în ultimul pas de timp (presupunând că este liniară) prin deducerea acesteia din mișcarea segmentului de linie. Nu numai că acest lucru reduce sistemul la unul rezolvabil, dar valorile și rezultate sunt valabile fără niciun fel de transformare inversă. Utilizarea arată astfel:

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

O potențială complicație este reprezentată de segmentele de dreaptă degenerate care nu au lungime (unde ambele puncte terminale sunt egale). Codul nu tratează în mod explicit acest caz, dar va acționa ca și cum tăierea unei linii care este de fapt un punct este imposibilă. Calculul lui , dacă este atins, va fi împărțit la zero. Rezultatul (fie -infinit, +infinit, sau NaN) va eșua la verificarea intervalului.

Un alt aspect pe care nu l-am acoperit este „unghiul de tăiere”. În animația care prezintă diferitele cazuri, tăieturile roșii sunt orientate prin lerparea între vitezele celor două puncte terminale cu (când viteza rezultată este 0, se alege un unghi aleatoriu). Dar am folosit și abordări alternative, cum ar fi „unghiul de tăiere este viteza punctului”. Practic, este vorba de a folosi orice pare bine și se simte natural în loc să încercăm să ne dăm seama de adevărata semnificație a „unghiului de tăiere”.

Rezumat

Această problemă devine trivială de îndată ce aplicăm câteva cunoștințe din algebra liniară. Cred că nu este prea surprinzător, deoarece algebra liniară (și polinoamele) apar peste tot, mai ales în geometrie.

O generalizare naturală a acestei probleme este de a include grosimile. Liniile desenate pe ecrane nu sunt infinit de subțiri, la urma urmei. A avea o grosime este, de asemenea, o modalitate bună de a reduce efectul erorilor de rotunjire în virgulă mobilă în direcții diferite în timpul diferitelor etape de timp. O altă modificare utilă ar fi capacitatea de a gestiona traiectorii parabolice, deoarece obiectele jocului sunt adesea în cădere liberă. Pe de altă parte, cred că este probabil mai ușor să tratăm pur și simplu „liniile groase” ca poligoane cu pași de timp cu viteză constantă.

–

Discută pe Reddit

–

Twisted Oak Studios oferă consultanță și dezvoltare pe proiecte interactive de înaltă tehnologie. Consultați portofoliul nostru sau dați-ne un strigăt dacă aveți ceva cu care credeți că niște ingineri cu adevărat radicali ar trebui să vă ajute.

Arhivă

strilanc
Ce fac computerele cuantice mai repede, cu avertismente
Numirea lucrurilor: Fail-Useful
Detectioning 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: Securizarea Fog of War de la egal la egal împotriva hackerilor de hărți
Obținerea încetinirii exponențiale prin numărarea de două ori
Utilizarea nemuririi pentru a ucide ciclurile de apelare accidentală
Tokens de anulare (și colapsarea viitorilor) pentru Objective-C
Vizualizarea vectorilor proprii ai unei rotații
Collapsing Futures în Objective-C
Bug Hunting #1: Garbled Audio from End to End
Experimente nepractice #1: Reprezentarea numerelor sub formă de polinoame
Implementarea pseudotelepatiei cuantice
Activați nenorocitele de avertismente
Big-O făcut trivial
Bugs insondabile #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 Precious 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
O vizită la Execution Labs din Montreal
Transmutarea zarurilor, conservarea entropiei
Regula de calcul: Întrebați de ceas
Regula degetului mare: Folosiți metode intenționat slăbite
Regula de bază: Precondițiile trebuie verificate în mod explicit
Intersectarea mai rapidă a listelor legate
Netezirea traseului mouse-ului pentru Jack Lumber
My Bug, My Bad #2: Sunk by Float
Repetă-te diferit
Grover’s Quantum Search Algorithm
Followup to Non-Nullable Types vs C#
Optimizarea Just in Time cu Expression Trees
Când un…Way Latency Doesn’t Matterly
Determinarea exactă dacă/când/unde o linie în mișcare a intersectat un punct în mișcare
Emularea actorilor în C# cu Async/Await
Crearea unei cozi imuabile cu operațiuni garantate în timp constant
Îmbunătățirea excepțiilor verificate
Colecții perisabile: The Benefits of Removal-by-Lifetime
Decuplarea controlului partajat
Decuplarea codului de interfață utilizator integrat
Linq to Collections: Dincolo de IEnumerable<T>
Publicați-vă .Net library as a NuGet package
When null is not enough: an option type for C#
Unfathomable Bugs #5: Readonly or not
Minkowski sums: examples
My Bug, My Bad #1: Sfere fractale
Lucrând cu Virtualizarea UI fragilă în Windows 8
Encapsularea unghiurilor
Bugs insondabile #4: Chei care nu sunt
Cum aș putea folosi o monadă (în C#)?
Metode utile/interesante #1: Observable.WhenEach
Infathomable Bugs #3: Stringing you along
Anonymous Implementation Classes – A Design Pattern for C#
Tasks for ActionScript 3 – Improving on Event-Driven Programming
Sume și diferențe Minkowski
Non-Nullable Types vs C#: Remedierea greșelii de un miliard de dolari
Bugs insondabile #2: Slashing Out
Șabloane de script și clase de bază
Extracția fonturilor unitare
Abusul de a folosi „Phantom Types” pentru a codifica lungimile listelor în tipul lor

Critica constructivă a API-ului Reactive Extensions
Quaternioni partea 3
Quaternioni partea 2
Quaternioni partea 1
Quaternioni partea 1
Unfathomable Bugs #1: Puteți avea lucruri! Poți avea lucruri ÎN lucruri! Poți avea …
Corutine – Mai mult decât vrei să știi
Asset Bundle Helper
Visual Studio dispare
.Net’s time traveling StopWatch
Introducerea lui Catalyst

Savage Rose

Determinarea exactă a intersecției dintre o linie în mișcare și un punct în mișcare | Twisted Oak Studios Blog