Calcula la distancia promedio de un segmento de punto a otro y de un segmento de línea a un segmento de línea

Question

Estoy buscando un algoritmo para calcular la distancia promedio entre un punto y un segmento de línea en 3D. Entonces, dados dos puntos A (x1, y1, z1) y B (x2, y2, z2) que representan el segmento de línea AB, y un tercer punto C (x3, y3, z3), ¿cuál es la distancia promedio entre cada punto de AB? al punto C?

También estoy interesado en la distancia promedio entre dos segmentos de línea. Entonces, dado el segmento AB y CD, ¿cuál es la distancia promedio entre cada punto en AB y el punto más cercano en CD?

No he tenido suerte con las búsquedas web que he probado, por lo que cualquier sugerencia sería apreciada.

Gracias.

Answer 1

Si quiere decir lo que creo que quiere decir con "promedio" (y "distancia", es decir, la norma L2 mencionada por dreeves), este es un procedimiento que piensa debería funcionar para encontrar la distancia promedio entre un punto y un segmento de línea. Necesitará una función dot(A,B) que toma el producto punto de dos vectores.

// given vectors (points) A, B, C 
K1 = dot(A-C,A-C) 
K2 = 2*dot(B-A,A-C) 
K3 = dot(B-A,B-A) 
L1 = sqrt(K3*(K1+K2+K3)) 
L2 = sqrt(K3*K1) 
N = 4*K3*L1 + 2*K2*(L1-L2) + (K2*K2-4*K1*K3)*log((K2+2*L2)/(2*K3+K2+2*L1)) 
D = N/(8*K3^1.5) 

Suponiendo que he transcrito todo correctamente, D A continuación tendrá lugar la distancia media.

Esto es básicamente solo un pseudocódigo para evaluar el resultado de una integral que hice en Mathematica. Puede haber algún buen atajo computacional para esto, pero si lo hay, no lo sé. (Y a menos que haya uno, me pregunto cuánto realmente necesita hacer este cálculo)

Si desea encontrar la distancia promedio desde el punto más cercano en un segmento de línea CD a todos los puntos en AB, en la mayoría En los casos, el punto más cercano será C o D, por lo que puede verificar ambos para ver cuál está más cerca (probablemente usando algún cálculo de distancia mínima como se hace en otras respuestas). La única excepción es cuando CD y AB son paralelos y se puede ejecutar una perpendicular de uno a otro, en cuyo caso tendría que definir sus requisitos de manera más precisa.

Si quería encontrar la distancia promedio entre todos los puntos en CD y todos los puntos en AB ... podría hacerse con una doble integral, aunque me da escalofríos pensar lo complicada que sería la fórmula resultante.

Answer 2

Primero, la distancia entre dos puntos es la raíz cuadrada de la suma de los cuadrados de las diferencias por pares de las coordenadas. (Por ejemplo, la distancia desde (0,0,0) a (1,1,1) es sqrt (3) pero esto funciona para puntos arbitrarios en cualquier cantidad de dimensiones.) Esta distancia se conoce como l2-norm (minúscula L) o norma euclidiana. norma de escritura (A, B) para la distancia entre los puntos A y B.

En el interesante problema de las distancias medias ... (Tenga en cuenta que la búsqueda de la mínima distancia de un punto a una línea o entre segmentos de línea es un problema mucho más común. Hubo una respuesta aquí con buenos punteros para ese problema, pero parece que se eliminó mientras tanto.)

Para encontrar la distancia promedio de un punto C a un segmento de línea AB, considere la distancia a un punto arbitrario entre A y B, es decir (1-k) A + kB donde k varía de 0 a 1. Esa es la norma (C, (1-k) A + kB). Entonces la distancia promedio es la integral de k = 0 a 1 de la norma (C, (1-k) A + kB).

Mathematica puede hacer eso integral para cualquier específico A, B, y C.

Aquí hay una aplicación de Mathematica:

avgd[A_,B_,C_] := Integrate[Sqrt@Dot[(1-k)*A+k*B-C, (1-k)*A+k*B-C], {k, 0, 1}] 

El integrando también se puede escribir Norm[(1-k)*A+k*B-C]. De cualquier manera, Mathematica puede hacerlo por puntos específicos pero no puede integrarlo simbólicamente, aunque aparentemente David lo hizo de alguna manera. Aquí está el ejemplo de David de los comentarios:

> avgd[{0, 0, 0}, {4, 0, 0}, {4, 3, 0}] // N 

3.73594 

Para el problema de la distancia media entre dos segmentos de línea, en teoría, creo que esto debería funcionar:

avgd[A_,B_,C_,D_] := Integrate[Norm[(1-k)A+k*B - (1-j)C - j*D], {k,0,1}, {j,0,1}] 

Pero Mathematica parece ahogarse con que incluso para puntos específicos, y mucho menos simbólicamente.

Answer 3

Bueno, si el análisis falla, llegar a una computadora y hacer una cantidad ridícula de cálculo hasta que se obtiene una idea de los números ...

también tengo una copia de Mathematica. Para mantener las cosas simples, dado que un triángulo debe estar en un plano, he trabajado lo siguiente en el espacio 2D. Para mantener las cosas más simples, especifico un punto en {0,0} y un segmento de línea de {1,0} a {0,1}. La distancia promedio de un punto a la línea debe ser, si es significativa, la longitud promedio de todas las líneas que podrían dibujarse desde {0.0} a cualquier parte del segmento de línea. Por supuesto, hay una gran cantidad de este tipo de líneas, así que vamos a empezar con, digamos, 10. En Mathematica esto podría ser computado como

Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 10.0^-1}]]] 

que da 0.830255. El próximo paso es obvio, hacer que la cantidad de líneas que mida sea más grande. De hecho, hagamos una tabla de promedios a medida que el exponente de 10.0 se hace más pequeño (¡son negativos!). En Mathematica:

Table[Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}] 

que produce:

{1, 0.830255, 0.813494, 0.811801, 0.811631, 0.811615, 0.811613} 

Siguiendo este enfoque me re-trabajado @ ejemplo de Dave (olvidar la tercera dimensión):

Table[Mean[Table[EuclideanDistance[{0, 0}, {4, 0 + 3 k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}] 

que da:

{9/2, 4.36354, 4.34991, 4.34854, 4.34841, 4.34839, 4.34839} 

Esto no ag ree con lo que @dreeves dice @ el algoritmo de Dave calcula.

EDITAR: OK, así que he perdido un poco más de tiempo en esto. Por el simple ejemplo I usado en el primer lugar, es decir, con un punto en el {0,0} y un segmento de línea que se extiende desde {0,1} a {1,0} I definir una función en Mathematica (como siempre), así:

fun2[k_] := EuclideanDistance[{0, 0}, {0 + k, 1 - k}] 

Ahora, esto es integrable.Mathematica da:

In[13]:= Integrate[fun2[k], {k, 0, 1}] 

    Out[13]= 1/4 (2 + Sqrt[2] ArcSinh[1]) 

O, si usted prefiere tener números, esto:

In[14]:= NIntegrate[fun2[k], {k, 0, 1}] 
Out[14]= 0.811613 

que es lo que el enfoque puramente numérica Tomé anterior da.

Ahora voy a volver al trabajo y dejo que ustedes generalicen esto en un triángulo arbitrario definido por un punto y los puntos finales de un segmento de línea.