Tengo dos segmentos de línea: X1, Y1, Z1 - X2, Y2, Z2 y X3, Y3, Z3 - X4, Y4, Z4Cálculo de la distancia más corta entre dos líneas (segmentos de línea) en 3D
I 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 sobre cómo hacerlo o sobre cualquier fuente de furmulae?
Un enfoque básico es lo 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, luego calcula la distancia desde ellos.
El truco para extender esto a 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í, usar el punto final en lugar del punto más cercano real en el infinito línea.
Para una muestra de hormigón, véase:
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()
Me gustaría parametrizar ambos segmentos de línea para usar un parámetro cada uno, limitado entre 0 y 1, inclusive. Luego, encuentre la diferencia entre ambas funciones de línea y úsela como la función objetivo en un problema de optimización lineal con los parámetros como variables.
Digamos 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 los 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.
Luego debe minimizar || (1 * t, 1 * s, 0) || donde t, s se encuentran en [0,1]. Ese es un problema bastante simple de resolver.
Dado segmentos de línea de p1 a p2 y de q1 a q2, necesita calcular todas las siguientes distancias y tomar el mínimo: (línea1, línea2), (p1, línea2), (p1, q1), (p1, q2), (p2, línea2), (p2, q1), (p2, q2), (línea1, q1), (línea1, q2). (O tal vez puede mostrar matemáticamente que algunos se pueden eliminar.) –
¿Qué hay de la extensión de 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 la línea de distancia más corta.
Si el punto de cada línea está en el segmento de línea original, entonces usted 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.
Responderé esto en términos de matlab, pero se pueden usar otros entornos de programación. Añadiré que esta solución es válida para resolver el problema en cualquier cantidad 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)
mismo modo, tenemos
RS(v) = R + v*(S-R)
ver 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 paramétricamente es muy útil en muchos contextos.
Después, 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 a 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, null (PQ) es un par de vectores de la base que abarcan la ortogonal dos subespacio dimensional 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 2 dimensiones (plano) ortogonales a la línea PQ. Al restar P (un punto en la línea PQ) para obtener rys, nos aseguramos de que la línea infinita pase por el origen en este plano de proyección.
De hecho, hemos reducido esto a la búsqueda de la distancia mínima desde la línea rs (v) al origen (0,0) en el plano de proyección. Recordemos que los rs línea (V) es definido 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. Como hemos reducido esto a 2 dimensiones porque el espacio original era 3-d, podemos hacerlo de manera simple. De lo contrario, me gustaría haber utilizado null de nuevo. Este pequeño truco funciona en 2-d:
> n = (s - r)*[0 -1;1 0];
> n = n/norm(n);
n ahora es un vector con la longitud de la unidad. La distancia desde la línea infinita rs (v) al origen es simple.
> d = dot(n,r)
d =
1.0491
Ver que también podría haber usado s, para obtener la misma distancia. La distancia real es abs (d), pero resulta que d fue positiva aquí de todos modos.
> d = dot(n,s)
d =
1.0491
¿Podemos determinar v a partir 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. Formar el producto de puntos de cada lado de esta ecuación con el vector (sr), y resolver 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 retroceder desde la proyección, esto nos dice que el punto más cercano en línea segmento RS a la línea infinita PQ fue el punto S.
Hay un paso más en el análisis a seguir. ¿Cuál es el punto más cercano en el segmento de línea PQ? ¿Este punto cae 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 bastante facilidad derivado de una lógica similar como lo hacía antes. Nótese aquí que he utilizado \ para hacer el trabajo.)
> u = (Q-P)'\((S - (S*N)*N') - P)'
u =
0.95903
Ver que u se encuentra en el intervalo [0,1] . Hemos resuelto el problema El punto de PQ es
> P + u*(Q-P)
ans =
0.25817 -1.1677 1.1473
Y, la distancia entre los puntos más cercanos de los dos segmentos de línea era
> norm(P + u*(Q-P) - S)
ans =
1.071
Por supuesto, todo esto se puede comprimir en tan sólo unas pocas líneas de código . Pero ayuda a expandirlo todo para obtener una mejor comprensión de cómo funciona.
Encontrar la distancia entre dos líneas finitas basado en encontrar entre dos líneas infinitas y luego unir las líneas infinitas a las líneas finitas no siempre funciona. por ejemplo tratar esto apunta
Q=[5 2 0]
P=[2 2 0]
S=[3 3.25 0]
R=[0 3 0]
Basado en enfoque infinito el algoritmo de selección de R y P para 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 cerca del punto P. Aparentemente, seleccionar P y [2 3.166] de la línea R a S tiene una distancia inferior de 1.1666. Incluso esta respuesta podría mejorarse mediante cálculos precisos y la búsqueda de una línea ortogonal desde la línea P a R S.
He intentado diferentes puntos y métodos y este es mi hallazgo hasta ahora. Cuando usa el método de proyecto para encontrar la distancia entre dos líneas finitas, debe realizar una proyección en cada lado. Significa que primero debe proyectar RS a PQ primero y luego viceversa para obtener la respuesta correcta. En este método, se calculan dos distancias diferentes y la más baja es lo que está buscando. – morteza
En primer lugar, encuentre la aproximación más cercana del puente del segmento de línea entre sus líneas extendidas. Llamemos a este LineSeg BR.
Si BR.endPt1 cae en LS1 y BR.endPt2 cae en LS2, ya está ... solo calcule la longitud de BR.
Si el BR puente cruza LS1 LS2 pero no, utilizar la menor de estas dos distancias: smallerOf (dist (BR.endPt1, LS2.endPt1), dist (BR.endPt1, LS2.endPt2))
Si el puente BR interseca LS2 pero no LS1, utilice la menor de estas dos distancias: smallerOf (dist (BR.endPt2, LS1.endPt1), dist (BR.endPt2, LS1.endPt2))
Si ninguno de estos las condiciones se mantienen, la distancia más cercana es el emparejamiento más cercano de los puntos finales en los Segs de línea opuestos.
El código de SoftSurfer es bastante bueno. Tiene problemas con líneas casi paralelas. Terminé escribiendo un cheque para líneas "casi paralelas". Una vez que hice esto, funcionó bien. No estoy seguro de por qué la comprobación de líneas "casi paralelas" integradas en SoftSurfer no funcionó. Solo pensé que el siguiente usuario quisiera saber ... –
Encontré lo mismo que @TimPerry. Utilicé esta verificación paralela: bool parallel = dot (u, v)/(u.length() * v.length())> 1 - SMALL_NUM; Modificar para su biblioteca de vectores. –
@ReedCopsey Intenté dist3D_Segment_to_Segment() con los siguientes segmentos de línea: LineSegment lineSegmentA; lineSegmentA.startPoint = PointType (0., 0., 0); lineSegmentA.endPoint = PointType (1., 0., 0); LineSegment lineSegmentB; lineSegmentB.startPoint = PointType (.5,0.2,0.); lineSegmentB.endPoint = PointType (.5,1.2,0.); La distancia más cercana debe ser desde el punto final de lineSegmentB hasta el punto central de lineSegmentA, que debe tener el valor "0.2". Sin embargo, la función devuelve la distancia como "0.538". ¿Alguna idea? –