c++ - tridimensional - hallar la distancia entre tres puntos

Manera eficiente de encontrar la distancia entre dos puntos 3D

Question

Estoy escribiendo un código en C ++ y quiero calcular la distancia entre dos puntos. Pregunta 1:

Tengo dos puntos P (x1, y1, z1) y Q (x2, y2, z2), donde x, y y z son flotantes / dobles.

Quiero encontrar la distancia entre estos dos puntos. Una forma de hacerlo es:

square_root (x_diff x_diff + y_diff y_diff + z_diff * z_diff)

Pero probablemente esta no sea la forma más eficiente. (por ejemplo, una fórmula mejor o una utilidad ya hecha en math.h etc.)

Pregunta 2:

¿Hay una mejor manera si solo quiero determinar si P y Q son de hecho los mismos puntos?

Mis entradas son coordenadas x, y y z de ambos puntos.

Gracias

Answer 1

¿Hay una mejor manera si solo quiero determinar si P y Q son de hecho los mismos puntos?

¡Entonces solo compara las coordenadas directamente!

bool areEqual(const Point& p1, const Point& p2) {
     return fabs(p1.x - p2.x) < EPSILON &&
            fabs(p1.y - p2.y) < EPSILON &&
            fabs(p1.z - p2.z) < EPSILON;
}

Answer 2

¿Necesita la distancia real? Podría usar la distancia al cuadrado para determinar si son iguales y para muchos otros propósitos. (Guarda en la operación sqrt)

Answer 3

En lo que respecta a la Pregunta 1, la penalización de rendimiento es el cálculo de la raíz cuadrada. La fórmula para calcular la distancia utilizando la raíz cuadrada de las diferencias de coordenadas emparejadas es lo que es.

Recomendaría encarecidamente leer esta http://www.codemaestro.com/reviews/9 implementación de raíz cuadrada por John Carmack del software de identificación que utilizó en su motor en Quake III. Es simplemente mágico.

Answer 4

Hay formas más rápidas de obtener una distancia aproximada, pero no hay nada integrado en las bibliotecas estándar. Eche un vistazo a este artículo en FlipCode que cubre el método para distancias 2D rápidas. Básicamente, colapsó la función sqrt en una función lineal compuesta que puede calcularse rápidamente pero no es 100% precisa. Sin embargo, en las máquinas modernas en estos días, fpmath es bastante rápido, así que no lo optimice demasiado pronto, puede que encuentre que está tomando su enfoque simple.

Answer 5

La biblioteca científica de GNU define gsl_hypot3 que calcula exactamente la distancia que desea en la primera parte de su pregunta. Una especie de exageración compilando todo solo por eso, dada la sugerencia de Darius, pero quizás haya otras cosas que quieras.

Answer 6

No hay mejor manera.

La implementación de square_root podría estar optimizada.

Si está comparando dos distancias y desea saber más, pero no le importa cuál es la distancia real, simplemente puede ingresar el paso de enraizamiento cuadrado por completo y manipular sus distancias aún al cuadrado. Esto sería aplicable a la comparación de dos pares de puntos para determinar si están a la misma distancia, por ejemplo.

Answer 7

No, no hay una manera más eficiente de calcular la dist. Cualquier tratamiento con casos especiales px == qx etc. será más lento en promedio.

Sí, la forma más rápida de ver si p y q son los mismos puntos es simplemente comparando x, y, z. Como son flotantes, no debe marcar == sino permitir alguna pequeña diferencia finita que defina.

Answer 8

Podrías encontrar este artículo interesante:

http://www.codemaestro.com/reviews/9

Describe cómo se calculó la raíz cuadrada en el motor de Quake 3, afirmando que en algunas CPU se ejecutó 4 veces más rápido que la función sqrt (). No estoy seguro de si te dará un aumento de rendimiento en C ++ hoy en día, pero sigue siendo una lectura interesante

Answer 9

Puedes intentar usar extensiones SSE. Por ejemplo, puedes iniciar dos vectores A (x1, y1, z1) y B (x2, y2, z2):

_m128 A = _mm_set_ps(x1, y1, z1, 0.0f)
_m128 B = _mm_set_ps(x2, y2, z2, 0.0f)

Luego calcule diff usando _mm_sub_ps:

__m128 Diff = _mm_sub_ps(A, B)

Siguiente cálculo sqr de diff:

__m128 Sqr = __mm_mul_ps(Diff, Diff)

Y finalmente:

__m128 Sum = add_horizontal(Sqr)
__m128 Res = _mm_sqrt_ss(Sum)

Res [0] se llenará con su respuesta.

PS add_horizontal es un lugar para la optimización

Answer 10

Respuesta Q2: x1 = x2 e y1 = y2 y z1 = z2 si los puntos son iguales.

Teniendo en cuenta que almacena puntos como flotante / doble, es posible que tenga que hacer la comparación con algunos épsilon.

Answer 11

Tenga en cuenta que al usar sqrt(dx*dx+dy*dy+dz*dz) la suma de cuadrados puede desbordarse. hypot(dx, dy) calcula una distancia directamente sin ninguna posibilidad de desbordamiento. No estoy seguro de cuál es el equivalente 3d más veloz, pero hypot(dx, hypot(dy, dz)) hace el trabajo y tampoco se desbordará.