algorithm - una - Cálculo de la distancia más corta entre dos líneas(segmentos de línea) en 3D
la distancia mas corta entre dos puntos es una curva (6)
¿Qué tal extender los segmentos de línea en líneas infinitas y encontrar la distancia más corta entre las dos líneas? Luego encuentre los puntos en cada línea que son los puntos finales del segmento de línea de distancia más corta.
Si el punto para cada línea está en el segmento de línea original, entonces tiene la respuesta. Si un punto para cada línea no está en el segmento original, entonces el punto es uno de los puntos finales de los segmentos de línea originales.
Tengo dos segmentos de línea: X1, Y1, Z1 - X2, Y2, Z2 y X3, Y3, Z3 - X4, Y4, Z4
Estoy tratando de encontrar la distancia más corta entre los dos segmentos.
He estado buscando una solución durante horas, pero todas parecen funcionar con líneas en lugar de segmentos de línea.
¿Alguna idea de cómo hacer esto, o alguna fuente de furmulae?
Encontrar la distancia entre dos líneas finitas basada en encontrar entre dos líneas infinitas y luego unir las líneas infinitas a las líneas finitas no siempre funciona. por ejemplo prueba estos puntos
Q=[5 2 0]
P=[2 2 0]
S=[3 3.25 0]
R=[0 3 0]
Basado en el enfoque infinito, el algoritmo selecciona R y P para el cálculo de la distancia (distancia = 2.2361), pero en algún lugar en el medio de R y S tiene una distancia más cercana al punto P. Aparentemente, la selección de P y [2 3.166] de R a S tiene una distancia menor de 1.1666. Incluso esta respuesta podría mejorar con un cálculo preciso y encontrando una línea ortogonal de la línea P a la RS.
Primero, encuentre el segmento de línea de aproximación más cercana que une entre sus líneas extendidas. Llamemos a este LineSeg BR.
Si BR.endPt1 cae en LS1 y BR.endPt2 cae en LS2, ya ha terminado ... simplemente calcule la longitud de BR.
Si el puente BR se interseca con LS1 pero no con LS2, use la menor de estas dos distancias: smallOf (dist (BR.endPt1, LS2.endPt1), dist (BR.endPt1, LS2.endPt2))
Si el puente BR se interseca con LS2 pero no con LS1, use la menor de estas dos distancias: smallOf (dist (BR.endPt2, LS1.endPt1), dist (BR.endPt2, LS1.endPt2))
Si no se cumple ninguna de estas condiciones, la distancia más cercana es el par más cercano de puntos finales en Segmentos de línea opuestos.
Responderé esto en términos de matlab, pero se pueden usar otros entornos de programación. Agregaré que esta solución es válida para resolver el problema en cualquier número de dimensiones (> = 3).
Supongamos que tenemos dos segmentos de línea en el espacio, PQ y RS. Aquí hay algunos conjuntos aleatorios de puntos.
> 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 línea infinita PQ (t) se define fácilmente como
PQ(u) = P + u*(Q-P)
Del mismo modo, tenemos
RS(v) = R + v*(S-R)
Vea que para cada línea, cuando el parámetro está en 0 o 1, obtenemos uno de los puntos finales originales en la línea devuelta. Por lo tanto, sabemos que PQ (0) == P, PQ (1) == Q, RS (0) == R, y RS (1) == S.
Esta forma de definir una línea de forma paramétrica es muy útil en muchos contextos.
A continuación, imagine que estábamos mirando hacia abajo a lo largo de la línea PQ. ¿Podemos encontrar el punto de menor distancia desde el segmento de línea RS hasta la línea infinita PQ? Esto se hace más fácilmente mediante una proyección en el espacio nulo de la línea PQ.
> N = null(P-Q)
N =
-0.37428 -0.76828
0.9078 -0.18927
-0.18927 0.61149
Por lo tanto, nulo (PQ) es un par de vectores base que abarcan el subespacio bidimensional ortogonal a la línea PQ.
> r = (R-P)*N
r =
0.83265 -1.4306
> s = (S-P)*N
s =
1.0016 -0.37923
Esencialmente, lo que hemos hecho es proyectar el vector RS en el subespacio bidimensional (plano) ortogonal a la línea PQ. Al restar P (un punto en la línea PQ) para obtener r y s, nos aseguramos de que la línea infinita pase por el origen en este plano de proyección.
Entonces, realmente, hemos reducido esto para encontrar la distancia mínima desde la línea rs (v) hasta el origen (0,0) en el plano de proyección. Recuerde que la línea rs (v) está definida por el parámetro v como:
rs(v) = r + v*(s-r)
El vector normal a la línea rs (v) nos dará lo que necesitamos. Ya que hemos reducido esto a 2 dimensiones porque el espacio original era 3-d, podemos hacerlo simplemente. De lo contrario, habría usado null otra vez. Este pequeño truco funciona en 2-d:
> n = (s - r)*[0 -1;1 0];
> n = n/norm(n);
n es ahora un vector con longitud de unidad. La distancia desde la línea infinita rs (v) al origen es simple.
> d = dot(n,r)
d =
1.0491
Mira que también podría haber usado s, para obtener la misma distancia. La distancia real es abs (d), pero resulta que d fue positivo aquí de todos modos.
> d = dot(n,s)
d =
1.0491
¿Podemos determinar v de esto? Sí. Recuerde que el origen es una distancia de d unidades desde la línea que conecta los puntos r y s. Por lo tanto, podemos escribir d n = r + v (sr), para algún valor del escalar v. Forme el producto puntual de cada lado de esta ecuación con el vector (sr), y resuelva para v.
> v = dot(s-r,d*n-r)/dot(s-r,s-r)
v =
1.2024
Esto nos dice que el enfoque más cercano del segmento de línea rs al origen ocurrió fuera de los puntos finales del segmento de línea. Entonces realmente el punto más cercano en rs al origen fue el punto rs (1) = s.
Al retirarse de la proyección, esto nos dice que el punto más cercano en el segmento de línea RS a la línea infinita PQ fue el punto S.
Hay un paso más en el análisis a tomar. ¿Cuál es el punto más cercano en el segmento de línea PQ? ¿Cae este punto dentro del segmento de línea o también cae fuera de los puntos finales?
Proyectamos el punto S en la línea PQ. (Esta expresión para u es fácilmente derivada de una lógica similar como lo hice antes. Note aquí que he usado / para hacer el trabajo.)
> u = (Q-P)''/((S - (S*N)*N'') - P)''
u =
0.95903
Vea que u se encuentra en el intervalo [0,1]. Hemos resuelto el problema. El punto en la línea PQ es
> P + u*(Q-P)
ans =
0.25817 -1.1677 1.1473
Y, la distancia entre los puntos más cercanos en los dos segmentos de línea era
> norm(P + u*(Q-P) - S)
ans =
1.071
Por supuesto, todo esto se puede comprimir en unas pocas líneas cortas de código. Pero ayuda a expandirlo todo para comprender mejor cómo funciona.
Un enfoque básico es el mismo que calcular la distancia más corta entre 2 líneas, con una excepción.
Si observa la mayoría de los algoritmos para encontrar la distancia más corta entre 2 líneas, encontrará que encuentra los puntos en cada línea que están más cerca y luego calcula la distancia desde ellos.
El truco para extender esto a los segmentos (o rayos), es ver si ese punto está más allá de uno de los puntos finales de la línea, y si es así, use el punto final en lugar del punto más cercano en la línea infinita.
Para una muestra concreta, ver:
http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm
Más específicamente:
http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()
Yo parametrizaría ambos segmentos de línea para usar un parámetro cada uno, enlazado entre 0 y 1, ambos inclusive. Luego encuentre la diferencia entre ambas funciones de línea y utilícela como función objetivo en un problema de optimización lineal con los parámetros como variables.
Así que diga que tiene una línea de (0,0,0) a (1,0,0) y otra de (0,1,0) a (0,0,0) (Sí, estoy usando las más fáciles) . Las líneas se pueden parametrizar como (1 * t, 0 * t, 0 * t) donde t se encuentra en [0,1] y (0 * s, 1 * s, 0 * s) donde s se encuentra en [0,1 ], independiente de t.
Entonces necesitas minimizar || (1 * t, 1 * s, 0) || donde t, s se encuentran en [0,1]. Ese es un problema bastante simple de resolver.