Determinare esattamente se/quando/dove una linea in movimento interseca un punto in movimento | Twisted Oak Studios Blog

Novembre 3, 2021
| Nessun commento

Determinare esattamente se/quando/dove una linea in movimento interseca un punto in movimento

posted by Craig Gidney on February 5, 2013

Provo a includere progetti di esempio quando pubblico le librerie. Nel caso delle collezioni deperibili, il progetto di esempio era in realtà un semplice gioco basato sul taglio di linee con il puntatore del mouse:

Come parte della scrittura dell’esempio, ho dovuto risolvere il problema di determinare se, quando e dove il puntatore del mouse fosse passato su una linea (o viceversa). Il mio solito riferimento per gli algoritmi di geometria non conteneva una soluzione, così ne ho sviluppata una io stesso.

In questo post spiegherò una soluzione analitica al problema. La soluzione è implementata in una piccola quantità di codice sorgente (circa 150 righe, contando i commenti e i metodi/tipi di supporto), disponibile anche su github.

Destinazione

Si è scoperto che “il puntatore del mouse ha tagliato la linea in movimento?” è uno di quei magici problemi matematici che inizia con alcuni vincoli relativamente semplici, poi sembra diventare piuttosto complicato mentre lo si risolve, ma poi quasi tutto si annulla o si combina negli ultimi passi e si finisce con qualcosa di assurdamente semplice. (Poi, quando si torna indietro per guardare la soluzione, si scopre che c’era un percorso facile per tutto il tempo.)

Per riferimento e motivazione, ho intenzione di scaricare la carne dell’implementazione proprio qui, prima di spiegarla. Le parole sottolineate sono link al codice corrispondente su 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);}

Non so voi, ma il fatto che il codice qui sopra risolva il problema mi stupisce. Sembra troppo semplice, eppure troppo slegato. Non dovrebbero esserci, tipo, dei casi d’angolo? Inoltre, da dove vengono quei semplici prodotti incrociati? Come può essere utile inserirli in un polinomio quadratico? Questo… ha bisogno di essere spiegato.

Intuizione

Iniziamo a considerare alcuni dei casi che potremmo incontrare, per avere un’idea intuitiva del problema. L’animazione qui sotto mostra diversi possibili movimenti della linea:

  • Semplice: entrambi i punti finali si muovono alla stessa velocità, e solo lungo il vettore normale della linea.
  • Laterale: un caso degenerato in cui la linea si muove lungo la sua stessa lunghezza.
  • Alza: un punto finale si muove orizzontalmente mentre l’altro si muove verticalmente (‘alzando’ e abbassando la linea).
  • Immersione: un estremo si muove diagonalmente (‘immersione’ attraverso il centro) mentre l’altro si muove verticalmente.

Vari casi di sweep

Si noti che una linea può spazzare un punto 0, 1, o 2 volte mentre i suoi estremi si muovono ad una velocità costante da una posizione all’altra. Il caso ‘Raise’ contiene convenientemente tutte e tre le possibilità. Questo, intuitivamente, è il motivo per cui la soluzione coinvolge un’equazione quadratica (che può avere 0, 1, o 2 radici reali distinte).

Un’altra realizzazione utile è che alcuni dei casi, come la linea che si muove ad una velocità costante o che sta ferma, corrisponderanno a equazioni quadratiche degeneri dove il coefficiente di ordine più alto è zero (cioè 0 x^2 + b x + c = 0 o anche 0 x^2 + 0 x + c = 0). Dobbiamo includere questo tipo di casi nei test.

Modello

Perché un segmento di linea da p a q contenga un punto c, devono essere soddisfatte due condizioni. Primo, il vettore ‘offset’ da p a c deve essere parallelo al vettore ‘delta’ da p a q. Possiamo rappresentarlo matematicamente richiedendo che il loro prodotto incrociato sia zero: (c-p) \times (q-p) = 0. Questo garantisce che c si trovi sulla linea che si ottiene estendendo il segmento di linea in entrambe le direzioni (o che si abbia un segmento di linea degenere a punto singolo). In secondo luogo, la proiezione scalare s del vettore offset sul vettore delta deve essere nell’intervallo giusto: 0 \leq s = \frac{(c-p) \cdot (q-p)}{(q-p)^2} \leq 1. Questo garantisce che c non è oltre nessuno dei punti finali del segmento.

Quando il tempo va da t=0 a t=1, il nostro segmento di linea avrà passato un punto c se e solo se esiste un tempo t in cui il segmento di linea corrente contiene c. Poiché i punti finali del nostro segmento di linea si muovono ad una velocità costante, il percorso che seguono è anch’esso un segmento di linea. Un punto finale che si muove da p_0 a p_1 si troverà nel punto interpolato linearmente lerp(p_0, p_1, t) = p_0 + (p_1 - p_0) \cdot t al tempo t. Nota che abbrevierò p_1-p_0 come p_d per risparmiare spazio. Inserendo i nostri punti mobili nelle nostre formule “il segmento di linea contiene un punto” ci dice che dobbiamo trovare t che soddisfa 0 \leq t \leq 1 e (c - (p_0 + p_d \cdot t)) \tempi ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) = 0 e 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.

Nota che “qualche prodotto incrociato deve essere uguale a 0″ non è l’unico modo di inquadrare il problema. Ha anche senso pensarlo come trovare un t e s, entrambi nell’intervallo , tali che c sia il risultato di lerping di entrambi i punti finali attraverso il loro percorso per t e poi lerping tra i punti finali per s. Matematicamente, ciò significa c = lerp(lerp(p_0, p_1, t), lerp(q_0, q_1, t), s). Le variabili t e s corrispondono approssimativamente a “quando” e “dove” avviene un’intersezione. Tuttavia, è più difficile risolvere il problema in questa forma, perché t non è inizialmente isolato, quindi userò l’inquadratura del prodotto incrociato (diversamente da come ho fatto la prima volta…).

Soluzione

Il prodotto incrociato e il prodotto del punto hanno alcune proprietà molto belle che renderanno più facile isolare t. Primo, distribuiscono l’addizione, il che significa u \times (v + w) = u \times v + u \times w e u \cdot (v + w) = u \cdot v + u \cdot w. In secondo luogo, la scalatura può essere fatta prima o dopo l’uno o l’altro prodotto, cioè (c \cdot u) \times v = c \cdot (u \times v) e (c \cdot u) \cdot v = c \cdot (u \cdot v), dove c è un numero reale. Infine, il prodotto di punti è commutativo, cioè u \cdot v = v \cdot u, mentre il prodotto incrociato è anti-commutativo, cioè u \times v = -v \times u.

Applicando questa conoscenza del prodotto, e usando un po’ di senno di poi per sapere di trattare particolari sottoespressioni come variabili individuali, possiamo trasformare la nostra equazione prodotto incrociato-è-zero in un’equazione quadratica:

{align*} 0 =(c - (p_0 + p_d \cdot t)) \tempi ((q_0 + q_d \cdot t)-(p_0 + p_d \cdot t)) \= ((c - p_0) - p_d \cdot t) \tempo ((q_0 - p_0) - (q_d - p_d) \cdot t) \tempo (a + b \cdot t) \tempo (c + d \cdot t)\a = c - p_0 a = c - p_0 b = -p_d a = -p_d a = q_0 - p_0 d = -(q_d - p_d) \= a tempo c + a tempo d \cdot t + b tempo c \cdot t + b tempo d \cdot t \cdot t \cdot t \cdot t \= t^2 \cdot (b tempo d) + t \cdot (a t \cdot (a \tempi d + b \tempi c) + (a \tempi c) \end{align*}

(Questo è esilarantemente più semplice del percorso che ho fatto la prima volta.)

Ah, ora è chiaro da dove viene la forma della soluzione del codice. Abbiamo iniziato con un prodotto incrociato uguale a zero (affermando che il vettore dalla linea al punto era parallelo alla linea) e abbiamo dovuto dividere il prodotto per isolare le somme dei termini che coinvolgono diverse potenze di t. Questo produce naturalmente un’equazione quadratica con coefficienti che coinvolgono prodotti incrociati. Bello!

Nota che questa è un’equazione molto “robusta”, perché non abbiamo mai assunto nulla dei vettori o degli scalari lungo il percorso. Per esempio, non dividiamo mai (o annulliamo implicitamente) per una variabile, quindi non abbiamo introdotto nessuna condizione di non-zero in agguato.

Con l’equazione semplificata, determinare i possibili valori di t è solo roba standard “risolvere polinomi quadratici”. Dobbiamo gestire i casi d’angolo con gli zeri, il che rende il codice un po’ più complicato, ma è solo roba noiosa caso per caso quindi mi limiterò a linkarlo.

Una volta che conosciamo un possibile valore di t, possiamo scoprire esattamente dove si è verificata la collisione usando la formula di contenimento del segmento di spina nella linea menzionata un po’ indietro: 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}. Chiamo questa formula la “proiezione lerp” di c sulla linea al tempo t, perché restituisce la proporzione s per cui lerp, dal punto di inizio della linea al suo punto finale, per ottenere c. È un piccolo metodo comodo per estrarre:

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}

Infine, una volta che abbiamo t e s, dobbiamo controllare che siano nell’intervallo . Se t è fuori dall’intervallo, allora la collisione non avverrà durante il passo temporale corrente. Se s è fuori dall’intervallo, allora la collisione avverrà sulla linea estesa, ma non sul segmento di linea. Poiché s e t descrivono quanto lerp per trovare quando/dove si è verificata la collisione, è anche un’informazione utile da restituire al chiamante.

Generalizzare

Un dettaglio importante che non ho ancora menzionato è che un puntatore del mouse in movimento ovviamente non corrisponde a un punto. Fortunatamente, possiamo semplicemente annullare il movimento del puntatore del mouse nell’ultimo passo temporale (assumendo che sia lineare) deducendolo dal movimento del segmento di linea. Non solo questo riduce il sistema ad uno risolvibile, ma i valori risultanti t e s sono validi senza alcun tipo di trasformazione inversa. L’uso assomiglia a questo:

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

Una potenziale complicazione è rappresentata dai segmenti di linea degenerati che non hanno lunghezza (dove entrambi i punti finali sono uguali). Il codice non gestisce esplicitamente questo caso, ma si comporterà come se tagliare una linea che è effettivamente un punto fosse impossibile. Il calcolo di s, se viene raggiunto, dividerà per zero. Il risultato (sia -infinito, +infinito, o NaN) fallirà il controllo dell’intervallo.

Un altro aspetto che non ho coperto è l'”angolo di taglio”. Nell’animazione che mostra i vari casi, i tagli rossi sono orientati da lerping tra le velocità dei due punti finali di s (quando la velocità risultante è 0, viene scelto un angolo casuale). Ma ho anche usato approcci alternativi come “l’angolo di taglio è la velocità del punto”. Fondamentalmente, si tratta di usare quello che sembra buono e naturale invece di cercare di capire il vero significato di “angolo di taglio”.

Sommario

Questo problema diventa banale non appena si applicano alcune conoscenze di algebra lineare. Immagino che non sia troppo sorprendente, dato che l’algebra lineare (e i polinomi) compaiono ovunque, specialmente in geometria.

Una generalizzazione naturale di questo problema è di includere gli spessori. Le linee disegnate sugli schermi non sono infinitamente sottili, dopo tutto. Avere uno spessore è anche un buon modo per ridurre l’effetto degli errori in virgola mobile che arrotondano in direzioni diverse durante diversi passi temporali. Un altro cambiamento utile sarebbe la capacità di gestire percorsi parabolici, dato che gli oggetti del gioco sono spesso in caduta libera. D’altra parte, credo che sia probabilmente più facile trattare le ‘linee spesse’ come poligoni con passi temporali a velocità costante.

–

Discuti su Reddit

–

Twisted Oak Studios offre consulenza e sviluppo su progetti interattivi ad alta tecnologia. Dai un’occhiata al nostro portfolio, o chiamaci se hai qualcosa con cui pensi che degli ingegneri davvero radicali dovrebbero aiutarti.

Archivio

  • strilanc
  • What Quantum Computers Do Faster, with Caveats
  • Naming Things: Fail-Useful
  • Detecting Simple Cycles Forming, Faster
  • Third Party Bit Commitment
  • Angular Velocity is Simple
  • Collection Equality is Hard
  • Deadlock in Practice: Non trattenere i blocchi mentre si notifica
  • Parallelizzazione della forza bruta
  • Un anno di opinioni sull’Objective-C
  • Riferire le sottostringhe più velocemente, senza perdere memoria
  • Non piangere sul vecchio codice
  • Esplorare le porte ternarie universali
  • Esperimenti pratici #2: Garantire la nebbia di guerra peer to peer contro gli hack delle mappe
  • Raccelerazione esponenziale con l’enumerazione di due volte
  • Utilizzare l’immortalità per uccidere i cicli di callback accidentali
  • Token di cancellazione (e collasso dei futuri) per l’obiettivoC
  • Visualizzare gli autovettori di una rotazione
  • Collapsing Futures in Objective-C
  • Caccia al bug #1: Audio confuso da un capo all’altro
  • Esperimenti Impratici #1: Rappresentare i Numeri come Polinomi
  • Implementare la Pseudo-Telepatia Quantistica
  • Accendi i tuoi Dannati Avvertimenti
  • Big-O reso Banale
  • Incomprensibili Bugs #7: Il forno rotto
  • Lo scienziato pazzo di Solomonoff
  • Riepilogo annuale del blog #1
  • Cosa non è una monade
  • Cercare una matrice ordinata più velocemente
  • Come leggere gli operatori ternari annidati
  • Come far saltare Sublime Text 2 alla riga giusta con Unity su OS X
  • Il mio bug, Il mio male #4: Leggere simultaneamente
  • Testare l’intera API con Reflection
  • Ottimizzare un Parser Combinator in una memcpy
  • Non trattare i percorsi come stringhe
  • Rottura di una funzione Hash giocattolo
  • Contare gli iteratori pigramente
  • Bug insondabili #6: Pretesa precisione
  • Il mio bug, il mio male #3: attaccare accidentalmente WarCraft 3
  • Tipi collassanti contro monadi (seguito)
  • Future collassanti: Facile da usare, difficile da rappresentare
  • Eccezioni Eventuali vs Programmazione in uno Stile Funzionale Minimo
  • Il Mistero di Flunf
  • Spiegare come se avessi cinque anni: Il problema del milionario socialista e il calcolo sicuro multiparty
  • L’informatica mi fa impazzire
  • Una visita agli Execution Labs di Montréal
  • Trasmettere i dadi, conservare l’entropia
  • Regola del pollice: Chiedere l’orologio
  • Regola del pollice: Usare metodi volutamente indeboliti
  • Regola del pollice: Le precondizioni dovrebbero essere verificate esplicitamente
  • Intersecare le liste collegate più velocemente
  • Lisciatura del percorso del mouse per Jack Lumber
  • My Bug, My Bad #2: Affondato da Float
  • Ripeti te stesso in modo diverso
  • Algoritmo di ricerca quantistica di Grover
  • Followup a tipi non annullabili vs C#
  • Ottimizzazione del Just in Time con gli alberi di espressioni
  • Quando la latenza in una sola direzione non conta
  • Determinare esattamente se/quando/dove una linea in movimento interseca un punto in movimento
  • Emulare gli attori in C#.Way Latency Doesn’t Matter
  • Determinare esattamente se/quando/dove una linea in movimento interseca un punto in movimento
  • Emulare gli attori in C# con Async/Await
  • Fare una coda immutabile con operazioni garantite a tempo costante
  • Migliorare le eccezioni controllate
  • Collezioni deperibili: I benefici della rimozione a tempo indeterminato
  • Distacco del controllo condiviso
  • Distacco del codice dell’interfaccia utente delineato
  • Linq alle collezioni: Oltre IEnumerable<T>
  • Pubblica la tua libreria .Net come pacchetto NuGet
  • Quando null non è abbastanza: un tipo di opzione per C#
  • Unfathomable Bugs #5: Readonly o no
  • Somme di Minkowski: esempi
  • My Bug, My Bad #1: Sfere frattali
  • Lavorare intorno alla fragile Virtualizzazione dell’UI in Windows 8
  • Incapsulando gli angoli
  • Bug insondabile #4: Chiavi che non sono
  • Come potrei usare una monade (in C#)?
  • Metodi utili/interessanti #1: Observable.WhenEach
  • Bug insondabili #3: Stringervi
  • Classi di implementazione anonime – Un modello di design per C#
  • Compiti per ActionScript 3 – Migliorare la programmazione guidata dagli eventi
  • Somme e differenze Minkowski
  • Tipi non annullabili vs C#: Correggere l’errore da un miliardo di dollari
  • Bug insondabili #2: Slashing Out
  • Modelli di script e classi base
  • Estrazione di caratteri unitari
  • Abuso di “Tipi fantasma” per codificare le lunghezze delle liste nel loro tipo
  • Critica costruttiva dell’API delle estensioni reattive
  • Quaternioni parte 3
  • Quaternioni parte 2
  • Quaternioni parte 1
  • Bugs insondabile #1: Si possono avere cose! Si possono avere cose NELLE cose! Puoi avere …
  • Coroutine – Più di quanto tu voglia sapere
  • Asset Bundle Helper
  • Il Visual Studio se ne va
  • .Net viaggia nel tempo con StopWatch
  • Introduzione a Catalyst

Articles