¿Hay alguna desventaja de usar las comprobaciones de Distancia al cuadrado en lugar de la Distancia?

29

Utilizo verificaciones de distancia al cuadrado para básicamente todas mis verificaciones de distancia (longitud de vector3), debido al aumento del rendimiento de no incurrir en una raíz cuadrada (como en las verificaciones de longitud simple).

Por lo que parece, los controles de distancia al cuadrado funcionan bien en cada situación:

if x^2 < y^2, then x < y, even when 0 < (x or y) < 1

No estoy considerando situaciones en las que x o y sea menor que 0, ya que la distancia y la distancia al cuadrado siempre serán positivas.

Como esto funciona, parece que nunca se necesitan verificaciones de distancia, pero tengo la sensación de que me falta algo. ¿Se mantendrá esto en situaciones críticas de precisión?

mathematics spaces Aralox
fuente

Respuestas:

41

No hay ninguna desventaja que conozca al usar la longitud al cuadrado para comparar distancias. Piénsalo así: solo estás salteando lo sqrtque no te da ninguna precisión adicional. Si no necesita la distancia euclidiana real, entonces puede dejarla sqrtfuera con seguridad .

Por supuesto, la longitud al cuadrado se escala de manera muy diferente a la distancia euclidiana y, por lo tanto, es un mal candidato para cosas como la heurística de búsqueda de caminos .

bummzack
fuente
16
La raíz cuadrada en realidad elimina la precisión de la verificación de distancia. Puede pensarlo como un intento de sacar la raíz cuadrada de un número de punto fijo entre 1 y 2 y almacenar el resultado (entre 1 y sqrt (2)) exactamente en el mismo rango. Algunas distancias que se comparan como x ^ 2 <y ^ 2 se compararán como x = y después de sacar la raíz cuadrada. La verificación de la longitud al cuadrado es más rápida y más precisa.
John Calsbeek
Gracias por sus excelentes respuestas bummzack y John Calsbeek! Sus respuestas combinadas responden perfectamente a mi pregunta. No consideré el espacio de memoria adicional de no usar una raíz cuadrada, una recolección realmente agradable allí. Y ese enlace heurístico es una gran lectura
Aralox
1
Excepto en el caso de A *. Recuerdo haber leído un artículo que describía las pruebas de diferentes heurísticas y d^2funcionaba horrible. En A * |dx| + |dy|funciona muy bien. No tengo el enlace ya que leí hace un mes más o menos.
Jonathan Dickinson
3
En el caso de A *, no solo está comparando distancias, sino que las suma, por lo que omitir el sqrt hace la diferencia.
amitp
1
@bobobobo estoy de acuerdo; Sobre todo lo hice para derribar un argumento potencial en la otra dirección, es decir, la distancia normal de alguna manera es más precisa.
John Calsbeek
14

Como bummzack insinuó con la analogía de encontrar el Camino, NECESITA usar la longitud "normal" cada vez que agrega distancias y desea comparar su suma. (Solo porque las sumas de cuadrados de longitudes son diferentes de las sumas cuadradas de longitudes).

x ^ 2 + y ^ 2! = (x + y) ^ 2

Imi
fuente
4

La única desventaja que se me ocurre es cuando se trata de grandes números que se desbordarán cuando estén al cuadrado.

Por ejemplo, en Java:

int x = Integer.MAX_VALUE / 1000000; //2147
int y = Integer.MAX_VALUE / 5000; //429496
System.out.println("x < y: " + (x < y)); //true
System.out.println("x*x: " + (x * x)); //4609609
System.out.println("y*y: " + (y * y)); //-216779712 - overflows!
System.out.println("x*x < y*y: " + (x * x < y * y)); //false - incorrect result due to overflow!

También vale la pena señalar que eso es lo que sucede cuando usa Math.pow () con exactamente los mismos números y devuelve a int desde el doble devuelto por Math.pow():

System.out.println("x^2: " + (int) (Math.pow(x, 2))); //4609609
System.out.println("y^2: " + (int) (Math.pow(y, 2))); //2147483647 - double to int conversion clamps to Integer.MAX_VALUE
System.out.println("x^2 < y^2: " + ((int) (Math.pow(x, 2)) < (int) (Math.pow(y, 2)))); //true - but for the wrong reason!

¿Está funcionando? No , solo dio la respuesta correcta porque y*yestá sujeta a Integer.MAX_VALUE, y x*xes menor que Integer.MAX_VALUE. Si x*xtambién se sujetó Integer.MAX_VALUE, obtendría una respuesta incorrecta.

Principios similares también se aplican con flotadores y dobles (excepto que obviamente tienen un rango mayor antes de que se desborden) y cualquier otro lenguaje que silenciosamente permita desbordamientos.

Caspar
fuente
La mayoría de las personas usan floats para las coordenadas, que solo se desbordan después de 10^38no hacerlo int.
bobobobo
Pero con 10 ^ 38 has perdido tanta precisión que realmente no puedes estar seguro de que tus comparaciones de distancia sean válidas más: el desbordamiento no es el único problema aquí. Consulte altdevblogaday.com/2012/02/05/dont-store-that-in-a-float (la sección "Tablas" resume la pérdida de precisión de hasta mil millones).
Maximus Minimus
Tendrá el mismo problema de desbordamiento con sqrt (x * x). No entiendo tu punto. No se trata de la distancia de Manhattan, etc.
bogglez
@bogglez: depende de si su biblioteca (o CPU) se duplica o no.
Maximus Minimus
3

Una vez estaba trabajando en distancias cuadradas, y cometí el error de acumular distancias cuadradas, para contar el odómetro.

Por supuesto, no puedes hacer esto, porque matemáticamente,

(a^2+b^2+c^2+d^2)!=(a+b+c+d)^2

Entonces, terminé con un resultado incorrecto allí. ¡Uy!

bobobobo
fuente
1
También podría agregar que hubo más de un par de veces que intenté usar distancias cuadradas, solo para descubrir que necesitaba distancias reales más adelante en esa misma rama de código. Por lo tanto, no exagere. A veces no vale la pena el inconveniente de mantener coeficientes cuadrados en todas partes, cuando de sqrttodos modos necesita terminar la operación.
bobobobo
3

Puede tener problemas si está escribiendo un algoritmo que requiere que calcule una posición optimizada. Por ejemplo, supongamos que tenía un conjunto de objetos y estaba tratando de calcular la posición con la distancia total más pequeña de todos los objetos. Solo por un ejemplo concreto, digamos que estamos tratando de alimentar tres edificios, y queremos averiguar a dónde debe ir la planta de energía para que podamos conectarla a todos los edificios utilizando la menor longitud total de cable. Usando la métrica de la distancia al cuadrado, terminarías con la coordenada x de la central eléctrica como el promedio de las coordenadas x de todos los edificios (y de forma análoga a la coordenada y). Usando la métrica de distancia ordinaria, la solución sería diferente y, a menudo, muy alejada de la solución de distancia al cuadrado.

Alexander Gruber
fuente
Parece discutible cuál sería mejor o peor para una situación dada. Recuerdo que los matemáticos a menudo eligen usar la distancia al cuadrado cuando ajustan una línea a un conjunto de puntos. Quizás lo hacen porque reduce la influencia de los valores atípicos solitarios. En su caso de tres edificios, los valores atípicos podrían no ser un riesgo. O tal vez lo hacen porque x^2es más fácil trabajar con ellos que |x|.
joeytwiddle 01 de
Los valores atípicos de @joeytwiddle en realidad afectan más la regresión lineal con ajustes de mínimos cuadrados que la distancia absoluta. Tienes razón en que se usa porque es más fácil trabajar con él. En el ejemplo que di (incluso si se modifica para contener una gran cantidad de edificios), la métrica de la distancia al cuadrado se resuelve con una fórmula simple (el promedio aritmético de cada coordenada), pero la métrica de la distancia absoluta es matemáticamente intratable y debe ser resuelto aproximadamente utilizando uno de varios métodos numéricos.
Alexander Gruber
Gracias por la corrección. Por supuesto que tiene razón, el cuadrado de la distancia genera un error mayor para los valores atípicos, aumentando su influencia en lugar de reducirlo, como dije anteriormente incorrectamente. Es fascinante cuánto más difícil es calcular la solución de distancia mínima absoluta.
joeytwiddle
0

Usar la distancia al cuadrado casi siempre está bien y es bueno para el rendimiento. Las siguientes consideraciones son importantes:

Si desea pensar en la suma de varias distancias, la distancia al cuadrado será inexacta. Por ejemplo, tengo dos distancias y quiero asegurarme de que su suma sea inferior a 10. El siguiente código es incorrecto:

a = get_distance_squared(c,d);
b = get_distance_squared(e,f);
assert(a+b < 10^2);

No se puede afirmar en el siguiente caso no válido: a=36y b=49. En este caso, la primera longitud es 6 y la segunda 7; su suma es mayor que 10, pero la suma de los cuadrados no es 100 o mayor.

Otra consideración: para distancias de valor real, la distancia al cuadrado siempre será positiva. Si está midiendo el desplazamiento, por ejemplo, es posible que tenga que lidiar con valores negativos y no cuadrarlos.

Expiación limitada
fuente