Calcolo della distanza più breve tra due linee (segmenti di linea) in 3D

Question

Ho due segmenti di linea: X1, Y1, Z1 - X2, Y2, Z2 e X3, Y3, Z3 - X4, Y4, Z4

I Sto cercando di trovare la distanza più breve tra i due segmenti.

Sono stato alla ricerca di una soluzione per ore, ma tutti sembrano funzionare con linee piuttosto che segmenti di linea.

Qualche idea su come procedere o su eventuali fonti di furmula?

Answer 1

Un approccio di base è lo stesso del calcolo della distanza più breve tra 2 linee, con un'eccezione.

Se osservi la maggior parte degli algoritmi per trovare la distanza più breve tra 2 linee, scoprirai che trova i punti su ciascuna linea più vicina, quindi calcola la distanza da essi.

Il trucco per estendere questo a segmenti (o raggi), è vedere se quel punto è oltre uno dei punti finali della linea, e in tal caso, utilizzare il punto finale anziché il punto più vicino effettivo sull'infinito linea.

Per un esempio concreto, si veda:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

In particolare:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()

Answer 2

Vorrei parametrizzare entrambi i segmenti di linea per utilizzare un parametro ciascuno, compresi tra 0 e 1, inclusi. Quindi trova la differenza tra le due funzioni di linea e la usa come funzione obiettivo in un problema di ottimizzazione lineare con i parametri come variabili.

Quindi dire che avete una linea da (0,0,0) a (1,0,0) e un'altra da (0,1,0) a (0,0,0) (Sì, sono usando quelli facili). Le linee possono essere parametrizzate come (1 * t, 0 * t, 0 * t) dove t giace in [0,1] e (0 * s, 1 * s, 0 * s) dove s giace in [0,1 ], indipendente da t.

Quindi è necessario ridurre al minimo || (1 * t, 1 * s, 0) || dove t, s giace in [0,1]. Questo è un problema piuttosto semplice da risolvere.

Answer 3

Che ne dite di estendere i segmenti di linea in linee infinite e trovare la distanza più breve tra le due linee . Quindi trova i punti su ciascuna linea che sono i punti finali del segmento di linea della distanza più breve.

Se il punto per ogni linea si trova sul segmento di linea originale, allora si ottiene la risposta. Se un punto per ogni linea non è sul segmento originale, il punto è uno dei punti finali dei segmenti di linea originali.

Answer 4

Risponderò a questo in termini di MATLAB, ma è possibile utilizzare altri ambienti di programmazione. Aggiungo che questa soluzione è valida per risolvere il problema in qualsiasi numero di dimensioni (> = 3).

Supponiamo di avere due segmenti di linea nello spazio, PQ e RS. Ecco alcuni set casuali di punti.

> P = randn(1,3) 
P = 
    -0.43256  -1.6656  0.12533 

> Q = randn(1,3) 
Q = 
     0.28768  -1.1465  1.1909 

> R = randn(1,3) 
R = 
     1.1892 -0.037633  0.32729 

> S = randn(1,3) 
S = 
     0.17464  -0.18671  0.72579 

La linea infinita PQ (t) è facilmente definito come

PQ(u) = P + u*(Q-P) 

Analogamente, abbiamo

RS(v) = R + v*(S-R) 

vedere che per ogni linea, quando il parametro è a 0 o 1 , otteniamo uno degli endpoint originali sulla riga restituita. Quindi, sappiamo che PQ (0) == P, PQ (1) == Q, RS (0) == R e RS (1) == S.

Questo modo di definire una linea in modo parametrico è molto utile in molti contesti.

Quindi, immaginavamo di guardare lungo la linea PQ. Possiamo trovare il punto di minima distanza dal segmento di linea RS alla linea infinita PQ? Questo è fatto più facilmente da una proiezione nello spazio nullo della riga PQ.

> N = null(P-Q) 
N = 
    -0.37428  -0.76828 
     0.9078  -0.18927 
    -0.18927  0.61149 

Così, null (PQ) è una coppia di vettori di base che coprono l'ortogonale bidimensionale sottospazio alla linea PQ.

> r = (R-P)*N 
r = 
     0.83265  -1.4306 

> s = (S-P)*N 
s = 
     1.0016  -0.37923 

sostanza ciò abbiamo fatto è di proiettare RS vettoriale nel 2 sottospazio bidimensionale (aereo) ortogonali alla linea PQ. Sottraendo P (un punto sulla linea PQ) per ottenere r e s, ci assicuriamo che la linea infinita passi attraverso l'origine in questo piano di proiezione.

Quindi, in realtà, abbiamo ridotto questo valore alla ricerca della distanza minima dalla linea rs (v) all'origine (0,0) nel piano di proiezione. Ricordiamo che le RS di linea (V) è definito dal parametro v come:

rs(v) = r + v*(s-r) 

Il vettore normale alla RS di linea (v) ci darà quello che ci serve. Dal momento che abbiamo ridotto questo a 2 dimensioni perché lo spazio originale era 3-d, possiamo farlo semplicemente. Altrimenti, avrei usato di nuovo null. Questo piccolo trucco funziona in 2-d:

> n = (s - r)*[0 -1;1 0]; 
> n = n/norm(n); 

n è ora un vettore con unità di lunghezza. La distanza dalla linea infinita rs (v) all'origine è semplice.

> d = dot(n,r) 
d = 
     1.0491 

Vedere che avrei potuto anche usare s, per ottenere la stessa distanza. La distanza effettiva è abs (d), ma come risulta, d era comunque positivo qui.

> d = dot(n,s) 
d = 
     1.0491 

Possiamo determinare v da questo? Sì. Ricorda che l'origine è una distanza di unità d dalla linea che collega i punti r e s. Quindi possiamo scrivere d n = r + v (sr), per qualche valore dello scalare v. Formare il prodotto scalare di ogni lato di questa equazione con il vettore (sr), e calcolare v.

> v = dot(s-r,d*n-r)/dot(s-r,s-r) 
v = 
     1.2024 

Questo ci dice che l'approccio più vicino del segmento di linea rs all'origine è accaduto al di fuori dei punti finali del segmento di linea. Quindi il punto più vicino su rs all'origine era il punto rs (1) = s.

Backing out dalla proiezione, questo ci dice che il punto più vicino sul segmento di linea RS alla linea infinita PQ era il punto S.

C'è ancora un passo da compiere nell'analisi. Qual è il punto più vicino sul segmento di linea PQ? Questo punto cade all'interno del segmento di linea o troppo fuori dagli endpoint?

Proiettiamo il punto S sulla linea PQ. (Questa espressione per u è abbastanza facilmente derivata dalla logica simile come ho fatto prima. Notare qui che ho usato \ per fare il lavoro.)

> u = (Q-P)'\((S - (S*N)*N') - P)' 
u = 
     0.95903 

Vedi che u si trova nell'intervallo [0,1] . Abbiamo risolto il problema. Il punto sulla linea PQ è

> P + u*(Q-P) 
ans = 
     0.25817  -1.1677  1.1473 

E, la distanza tra i punti più vicini ai due segmenti di linea era

> norm(P + u*(Q-P) - S) 
ans = 
     1.071 

Naturalmente, tutto questo può essere compresso in poche righe brevi di codice . Ma aiuta a espandere tutto per capire come funziona.

Answer 5

Trovare la distanza tra due linee finite basata sul trovare tra due linee infinite e quindi legare le linee infinite alle linee finite non funziona sempre. per esempio provare questo sottolinea

Q=[5 2 0] 
P=[2 2 0] 
S=[3 3.25 0] 
R=[0 3 0] 

Sulla base di approccio infinita l'algoritmo di selezione R e P per il calcolo della distanza (distanza = 2,2361), ma da qualche parte nel mezzo di R e S ha una distanza più vicina al punto di P. Apparentemente, selezionando P e [2 3.166] dalla linea R alla S si ha una distanza inferiore di 1.1666. Anche questa risposta potrebbe migliorare con il calcolo preciso e la ricerca della linea ortogonale dalla linea P a R S.

Answer 6

In primo luogo, individuare il metodo di avvicinamento più vicino tra le linee estese. Chiamiamo questo LineSeg BR.

Se BR.endPt1 cade su LS1 e BR.endPt2 cade su LS2, hai finito ... basta calcolare la lunghezza di BR.

Se il BR ponte interseca LS1 ma non LS2, utilizzare il più breve di queste due distanze: smallerOf (dist (BR.endPt1, LS2.endPt1), dist (BR.endPt1, LS2.endPt2))

Se il ponte BR interseca LS2 ma non LS1, utilizzare il minore di queste due distanze: minoreOf (dist (BR.endPt2, LS1.endPt1), dist (BR.endPt2, LS1.endPt2))

Se nessuno di questi condizioni tenere, la distanza più vicina è l'accoppiamento più vicino di endpoint su segmenti di linea opposti.