¿Por qué es más preferible la ley de los cosenos que la haversina al calcular la distancia entre dos puntos de latitud y longitud?

41

De hecho, cuando Sinnott publicó la fórmula de Haversine, la precisión computacional fue limitada. Hoy en día, JavaScript (y la mayoría de las computadoras e idiomas modernos) usan números de coma flotante IEEE 754 de 64 bits, que proporcionan 15 cifras significativas de precisión. Con esta precisión, la fórmula simple de la ley esférica del coseno ( cos c = cos a cos b + sin a sin b cos C) brinda resultados bien condicionados a distancias tan pequeñas como alrededor de 1 metro. En vista de esto, probablemente valga la pena, en la mayoría de las situaciones, usar la ley más simple de cosenos o la fórmula de Vincenty elipsoidal más precisa en lugar de la haversina. (teniendo en cuenta las notas a continuación sobre las limitaciones en la precisión del modelo esférico).
Fuente: http://www.movable-type.co.uk/scripts/latlong.html

¿Cuál es la razón por la cual la ley del coseno es más preferible?

Nota: El texto citado ha sido actualizado por su autor como se menciona a continuación .

Afriza N. Arief
fuente
10
¿Cómo es "preferible" la ley de cosenos? Podemos responder esto de dos maneras: para la computadora y el programador. Para la computadora, la fórmula de Haversine usa menos funciones trigonométricas pero requiere dos raíces cuadradas. Para la eficiencia computacional, entonces, es una sacudida. Para el programador, la fórmula de Haversine es un poco más larga. Sin embargo, la fórmula de la ley de cosenos requiere tener una implementación ACos, que se ve con un poco menos de frecuencia que una implementación ATan. Además, para escribir código a prueba de balas , debe verificar que el ACos no fallará. Solo por esta razón , deberíamos preferir la haversina.
whuber
2
Acabo de implementar haversine y cosine en Python. En esta computadora, el haversine toma 3.3μs y el coseno toma 2.2μs, lo cual es bastante significativo si necesita hacer muchos de ellos
gnibbler
1
Gracias a todos por algunas buenas observaciones e información. He actualizado el texto citado en la pregunta para que sea, espero, bastante más objetivo y útil.
ChrisV
@ChrisV, gracias por la actualización! He movido esto a un comentario, ya que no es directamente una respuesta a la pregunta, gracias por su gran sitio.
scw

Respuestas:

49

El problema está indicado por la palabra "bien condicionado". Es una cuestión de aritmética informática, no de matemáticas.

Aquí están los hechos básicos a considerar:

  1. Un radián en la tierra abarca casi 10 ^ 7 metros.

  2. La función coseno para argumentos x cerca de 0 es aproximadamente igual a 1 - x ^ 2/2.

  3. El punto flotante de precisión doble tiene aproximadamente 15 dígitos decimales de precisión.

Los puntos (2) y (3) implican que cuando x es alrededor de un metro, o 10 ^ -7 radianes (punto 1), casi toda la precisión se pierde: 1 - (10 ^ -7) ^ 2 = 1 - 10 ^ - 14 es un cálculo en el que los primeros 14 de los 15 dígitos significativos se cancelan, dejando solo un dígito para representar el resultado. Darle la vuelta a esto (que es lo que hace el coseno inverso, "acos") significa que calcular acos para ángulos que corresponden a distancias de un metro no se puede hacer con una precisión significativa. (En ciertos casos graves, la pérdida de precisión da un valor donde ni siquiera se define acos, por lo que el código se descompondrá y no dará respuesta, una respuesta sin sentido o bloqueará la máquina). Consideraciones similares sugieren que debe evitar usar el coseno inverso si hay distancias de menos de unos cientos de metros, dependiendo de la precisión que esté dispuesto a perder.

El papel que juega acos en la ingenua fórmula de la ley del coseno es convertir un ángulo en una distancia. Atan2 desempeña ese papel en la fórmula de Haversine. La tangente de un ángulo pequeño x es aproximadamente igual a x misma. En consecuencia, la tangente inversa de un número, que es aproximadamente ese número, se calcula esencialmente sin pérdida de precisión. Es por eso que la fórmula de Haversine, aunque matemáticamente equivalente a la fórmula de la ley del coseno, es muy superior para distancias pequeñas (del orden de 1 metro o menos).

Aquí hay una comparación de las dos fórmulas usando 100 pares de puntos aleatorios en el globo (usando los cálculos de doble precisión de Mathematica).

texto alternativo

Puede ver que para distancias de menos de aproximadamente 0.5 metros, las dos fórmulas divergen. Por encima de 0,5 metros tienden a estar de acuerdo. Para mostrar qué tan de acuerdo están, la siguiente gráfica muestra las relaciones de la ley de los cosenos: resultados de haversina para otros 100 pares de puntos aleatorios, con sus latitudes y longitudes que difieren aleatoriamente en hasta 5 metros.

texto alternativo

Esto muestra que la fórmula de la ley del coseno es buena para 3-4 decimales una vez que la distancia excede los 5-10 metros. El número de lugares decimales de precisión aumenta cuadráticamente; así, a 50-100 metros (un orden de magnitud) obtienes una precisión de 5-6 dp (dos órdenes de magnitud); a 500-1000 metros obtienes 7-8 dp, etc.

whuber
fuente
¿Hay alguna prueba barata, por ejemplo, delta latitude > .1 || delta longitude > .1para elegir dinámicamente coseno (para grandes) o haversina (para pequeñas distancias)? Con el fin de obtener el mejor rendimiento y una buena precisión.
Anony-Mousse
@ Anony-Mousse Ambas fórmulas pueden estar apagadas en algunas décimas de uno por ciento para distancias de un cuarto alrededor del mundo, por lo que para entonces no nos preocuparemos por la precisión. Por lo tanto, cualquier prueba que pueda distinguir puntos cercanos (unos pocos cientos de metros) de puntos casi diametralmente opuestos (alrededor de 20 millones de metros) de todo lo demás debería ser suficiente.
whuber
¿Ofrece atan2más beneficios numéricos asin? Vi puntos de referencia, donde atan2era 2-3 veces más lento que asin, y también necesitamos un segundo sqrt.
Erich Schubert
@Erich No he estudiado la diferencia, pero tenga en cuenta que asines esencialmente lo mismo acosy, por lo tanto, sufre la misma pérdida de precisión para ciertos valores, en este caso, para argumentos cercanos a 1 y -1. En principio, atan2no tiene ese problema.
whuber
Eso sería a distancias muy grandes? Combinar eso con la sugerencia de @ Anony-Mousse anterior parece ser interesante entonces.
Erich Schubert
7

Una nota al pie histórica:

El haversine era una forma de evitar grandes errores de redondeo en cálculos como

1 - cos(x)

cuando x es pequeño. En cuanto a la haversina tenemos

1 - cos(x) = 2*sin(x/2)^2
           = 2*haversin(x)

y 2 * sin (x / 2) ^ 2 se puede calcular con precisión incluso cuando x es pequeño.

En los viejos tiempos, la fórmula de haversina tenía una ventaja adicional de evitar una adición (lo que implicaba una búsqueda antilógina, la adición y una búsqueda de registro). Se decía que una fórmula trigonométrica que implicaba solo multiplicaciones estaba en "forma logarítmica".

Hoy en día, el uso de las fórmulas de haversina es ligeramente anacrónico. Puede ser que el ángulo x se exprese en términos sin(x)y cos(x)(y x no se conozca explícitamente). En ese caso, la computación 1 - cos(x)mediante la fórmula de Haversine implica un arcotangente (para obtener el ángulo x), reducir a la mitad (obtener x/2), un seno (obtener sin(x/2)), un cuadrado (obtener sin(x/2)^2) y una duplicación final. Estás mucho mejor usando la evaluación

1 - cos(x) = sin(x)^2/(1 + cos(x))

lo que no implica evaluaciones de funciones trigonométricas. (Obviamente, use el lado derecho solo si cos(x) > 0; de lo contrario, está bien usarlo 1 - cos(x)directamente).

cffk
fuente
1

La fórmula del coseno se puede implementar en una línea:

  Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371

La fórmula de Haversine toma múltiples líneas:

  dLat = (lat2-lat1)
  dLon = (lon2-lon1)
  a = sin(dLat/2) * sin(dLat/2) + cos(lat1) * cos(lat2) * sin(dLon/2) * sin(dLon/2)
  distance = 6371 * 2 * atan2(sqrt(a), sqrt(1-a))

Matemáticamente, hay idénticos, por lo que la única diferencia es de practicidad.

Tom W
fuente
Si bien el Haversine original no usa la atan2fórmula relacionada con la computadora , no hay nada que impida reescribir las 4 líneas anteriores en una sola fórmula.
Arjan
@Arjan, cierto, pero sería ineficiente debido a que se necesita para calcular un doble. Es esencial que la fórmula involucre tanto a Sqrt (a) como a Sqrt (1-a), porque aunque uno de ellos será numéricamente inestable para distancias muy pequeñas o muy grandes, el otro no lo será: eso es lo que hace que este enfoque funcione.
whuber
Es cierto, @whuber, pero aún dudo que el número de líneas me haga elegir una sobre la otra. (Y como ya se explicó en su respuesta, hay razones mucho más importantes para favorecer una.)
Arjan
3
@Arjan, estoy de acuerdo. La primera prioridad debe ser la adecuación del código para la tarea de programación. Después de eso, pondría claridad: es decir, legibilidad, mantenibilidad y documentación alfabetizada. En ausencia de dicho contexto, contar el número de líneas de código no tiene sentido.
whuber
1
atan2(sqrt(a), sqrt(1-a))es lo mismo queasin(sqrt(a))
user102008