predicato di prossimità geometrica veloce
https://stackoverflow.com/questions/254979
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho 3 punti (A, B e X) e una distanza (d). Devo eseguire una funzione che verifica se il punto X è più vicino della distanza d a qualsiasi punto sul segmento di linea AB.
La domanda è innanzitutto la mia soluzione corretta e poi di trovare una soluzione migliore (più veloce).
Il mio primo passaggio è il seguente
AX = X-A
BX = X-B
AB = A-B
// closer than d to A (done squared to avoid needing to compute the sqrt in mag)
If d^2 > AX.mag^2 return true
// closer than d to B
If d^2 > BX.mag^2 return true
// "beyond" B
If (dot(BX,AB) < 0) return false
// "beyond" A
If (dot(AX,AB) > 0) return false
// find component of BX perpendicular to AB
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2
Questo codice finirà per essere eseguito per un ampio set di P e un ampio set di terzine A / B / d con l'intento di trovare tutte le P che passano per almeno un A / B / d, quindi sospetto che lì è un modo per ridurre il costo complessivo in base a ciò, ma non l'ho ancora esaminato.
(A proposito: sono consapevole che alcuni riordini, alcuni valori temporanei e alcune identità algebriche potrebbero ridurre il costo di quanto sopra. Li ho semplicemente omessi per chiarezza.)
EDIT: questo è un problema 2D (ma la soluzione che generalizza al 3D sarebbe interessante
Modifica: a ulteriore riflessione, mi aspetto che il tasso di successo sia di circa il 50%. Il punto X può essere formato in una gerarchia nidificata, quindi mi aspetto di essere in grado di potare grandi sottotitoli come all-pass e all-fail. L'A / B / d che limita le terzine sarà più di un trucco.
Modifica: d è nello stesso ordine di grandezza di AB.
modifica: Artelius ha pubblicato una bella soluzione. Non sono sicuro di capire esattamente cosa sta succedendo mentre sono sceso su una tangente prima di averlo capito appieno. Comunque un altro pensiero mi è venuto in mente come risultato:
- Il primo bit di Artelius, pre-calcola una matrice che posizionerà AB centrato mangiando l'origine e allineato con l'asse X. (2 aggiunge, 4 muls e 2 aggiunge)
- piega tutto nel 1 ° quadrante (2 addominali)
- scala in X & amp; Y per trasformare la porzione centrale della zona in un'unità quadrata (2 mul)
- verifica se il punto è in quel quadrato (2 test) è così chiuso
- verifica il tappo di chiusura (torna ai valori non scalati
- traduci in x per posizionare la fine all'origine (1 aggiungi)
- quadrare e aggiungere (2 mul, 1 aggiungi)
- confronta con d ^ 2 (1 cmp)
Sono abbastanza sicuro che questo batte la mia soluzione.
(se non succede niente di meglio, Artelius ottiene il "premio" :)
Soluzione
Se il tuo insieme di (A, B, d) è fisso, puoi calcolare una coppia di matrici per ciascuna per tradurre il sistema di coordinate, in modo che la linea AB diventi l'asse X e il punto medio di AB sia l'origine.
Penso questo è un modo semplice per costruire le matrici:
trans = - ((A + B) / 2) // translate midpoint of AB to origin
rot.col1 = AB / AB.mag // unit vector in AB direction
0 -1
rot.col2 = rot.col1 * ( ) // unit vector perp to AB
1 0
rot = rot.inverse() // but it needs to be done in reverse
Quindi prendi semplicemente ogni X e fai rot * (X + trans) .
La regione in questione è attualmente simmetrica in entrambi gli assi xey, quindi puoi prendere il valore assoluto della coordinata xe della coordinata y.
Quindi devi solo controllare:
y < d && x < AB.mag/2 //"along" the line segment
|| (x - AB.mag/2)^2 + y^2 < d^2 // the "end cap".
Puoi fare un altro trucco; la matrice può ridimensionarsi di un fattore AB.mag / 2 (ricorda che le matrici sono calcolate solo una volta per (A, B), il che significa che è meglio trovarle più lente, piuttosto che il vero e proprio controllo ). Ciò significa che il tuo controllo diventa:
y < 2*d/AB.mag && x < 1
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2
Dopo aver sostituito due istanze di AB.mag / 2 con la costante 1, potrebbe essere un tocco più veloce. E ovviamente puoi precalcolare anche 2 * d / AB.mag e (2 * d / AB.mag) ^ 2 .
Se questo funzionerà più velocemente di altri metodi dipende dagli input che gli dai. Ma se la lunghezza di AB è lunga rispetto a d, penso che risulterà notevolmente più veloce del metodo che hai pubblicato.
Altri suggerimenti
Hmmmmmmm .... Qual è il tasso di successo? Con quale frequenza indica "X" soddisfare i requisiti di prossimità?
Penso che il tuo algoritmo esistente sia buono e qualsiasi ulteriore ottimizzazione verrà dall'ottimizzazione ai dati reali. Ad esempio, se la "X" punto incontra il test di prossimità il 99% delle volte, quindi penso che la tua strategia di ottimizzazione dovrebbe essere considerevolmente diversa rispetto a se passa solo il test l'1% delle volte.
Per inciso, quando arrivi al punto in cui stai eseguendo questo algoritmo con migliaia di punti, dovresti organizzare tutti i punti in un albero dimensionale K (o KDTree ). Rende il calcolo di "prossimo più vicino" molto più semplice.
Il tuo problema è un po 'più complesso di un vicino più vicino di base (perché stai controllando la vicinanza a un segmento di linea piuttosto che solo la vicinanza a un punto) ma penso ancora che KDTree sarà a portata di mano.
Se lo leggo correttamente, allora è quasi lo stesso del classico test di intersezione raggio / sfera usato nella tracciatura di raggi 3D.
In questo caso hai una sfera nella posizione X del raggio d e stai cercando di scoprire se la linea AB interseca la sfera. L'unica differenza con il ray-tracing è che in questo caso hai una linea specifica AB, mentre nel ray-tracing il raggio è normalmente generalizzato come origin + distance * direction , e tu non non importa quanto sia lunga la linea infinita AB + .
In pseudo-codice dal mio ray-tracer (basato sull'algoritmo fornito in "Un'introduzione al ray-tracing" (ed. Glassner):
Vector v = X - A
Vector d = normalise(B - A) // unit direction vector of AB
double b = dot(v, B - A)
double discrim = b^2 - dot(v, v) + d^2
if (discrim < 0)
return false // definitely no intersection
Se sei arrivato così lontano, allora c'è qualche possibilità che le tue condizioni siano soddisfatte. Devi solo capire se l'intersezione (i) è sulla linea AB:
discrim = sqrt(discrim)
double t2 = b + discrim
if (t2 <= 0)
return false // intersection is before A
double t1 = b - discrim
result = (t1 < length(AB) || (t2 < length(AB))
Questo codice finirà per essere eseguito per un ampio set di P e un ampio set di terzine A / B / d con l'intento di trovare tutte le P che passano per almeno un A / B / d, quindi sospetto che lì è un modo per ridurre il costo complessivo in base a ciò, ma non l'ho ancora esaminato.
Nel caso in cui d ~ AB, per un dato punto X, è possibile prima verificare se X appartiene a una delle molte sfere del raggio d e centro Ai o Bi. Guarda l'immagine:
...... .....
........... ...........
...........................
.......A-------------B.......
...........................
........... ...........
..... .....
I primi due test
If d^2 > AX.mag^2 return true
If d^2 > BX.mag^2 return true
sono i più veloci e se d ~ AB sono anche quelli con la più alta probabilità di successo (dato che il test ha esito positivo). Dato X, puoi eseguire tutti i "test delle sfere" prima, e poi tutti quelli finali:
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2
Se il numero di insiemi di A / B / d è grande e sei decisamente in 2D, considera l'utilizzo di R-alberi (o loro equivalenti ottagonali) in cui ciascuna voce nell'albero R è il riquadro di delimitazione minimo del triplo A / B / d. Ciò ti consentirebbe di eliminare la necessità di testare molte triple A / B / d & amp; focalizza la tua potenza della CPU solo su quei pochi in cui ogni punto X è all'interno dei rettangoli del triplo A / B / d. Quindi fai un test più dettagliato come quello che hai citato.
