php - por - Fórmulas para calcular la proximidad geográfica

distancia entre dos puntos latitud longitud excel

Question

Necesito implementar una búsqueda de proximidad geográfica en mi aplicación, pero estoy muy confundido con respecto a la fórmula correcta para usar. Después de algunas búsquedas en la Web y en StackOverflow encontré que las soluciones son:

1. Usa la fórmula Haversine
2. Usa la fórmula de distancia Great-Circle
3. Use un motor de búsqueda espacial en la base de datos

La opción n. ° 3 realmente no es una opción para mí ATM. Ahora estoy un poco confundido ya que siempre pensé que la fórmula de distancia Great-Circle y la fórmula Haversine eran sinónimos, pero aparentemente estaba equivocado.

Haversine Formula http://i46.tinypic.com/30shbn6.png

La captura de pantalla anterior fue tomada de la impresionante búsqueda Geo (proximidad) con papel MySQL , y utiliza las siguientes funciones:

ASIN, SQRT, POWER, SIN, PI, COS

También he visto variaciones de la misma fórmula ( Ley Esférica de Coseno ) , como esta:

(3956 * ACOS(COS(RADIANS(o_lat)) * COS(RADIANS(d_lat)) * COS(RADIANS(d_lon) - RADIANS(o_lon)) + SIN(RADIANS(o_lat)) * SIN(RADIANS(d_lat))))

Eso usa las siguientes funciones:

ACOS, COS, RADIANS, SIN

No soy un experto en matemáticas, pero ¿son estas fórmulas las mismas? He encontrado más variaciones y fórmulas (como la Ley esférica de los cosenos y las Vincenty''s que parece ser la más precisa) y eso me confunde aún más ...

Necesito elegir una buena fórmula de propósito general para implementar en PHP / MySQL. ¿Alguien puede explicarme las diferencias entre las fórmulas que mencioné anteriormente?

• ¿Cuál es el más rápido de calcular?
• ¿Cuál proporciona los resultados más precisos?
• ¿Cuál es el mejor en términos de velocidad / precisión de los resultados?

Aprecio tu visión sobre estas preguntas.

Basándome en la respuesta theonlytheory , probé las siguientes fórmulas de distancia Great-Circle:

• Fórmula Vincenty
• Fórmula Haversine
• Ley Esférica de Coseno

La fórmula de Vincenty es muy lenta, pero es bastante precisa (hasta 0,5 mm) .

La Fórmula Haversine es mucho más rápida que la fórmula Vincenty, pude ejecutar 1 millón de cálculos en aproximadamente 6 segundos, lo cual es bastante aceptable para mis necesidades.

La Fórmula de la Ley Esférica de Coseno reveló ser casi dos veces más rápida que la Fórmula Haversine, y la diferencia de precisión es negligencia para la mayoría de los casos de uso.

Aquí hay algunos lugares de prueba:

• Google HQ ( 37.422045 , -122.084347 )
• San Francisco, CA ( 37.77493 , -122.419416 )
• Torre Eiffel, Francia ( 48.8582 , 2.294407 )
• Opera House, Sydney ( -33.856553 , 151.214696 )

Sede de Google - San Francisco, CA:

• Fórmula Vincenty: 49 087.066 meters
• Fórmula Haversine: 49 103.006 meters
• Ley Esférica de Coseno: 49 103.006 meters

Sede de Google - Torre Eiffel, Francia:

• Fórmula Vincenty: 8 989 724.399 meters
• Fórmula Haversine: 8 967 042.917 meters
• Ley Esférica de Coseno: 8 967 042.917 meters

Sede de Google - Opera House, Sydney:

• Fórmula Vincenty: 11 939 773.640 meters
• Fórmula Haversine: 11 952 717.240 meters
• Ley Esférica de Coseno: 11 952 717.240 meters

Como puede ver, no existe una diferencia notable entre la fórmula de Haversine y la ley esférica de los cosenos, sin embargo, ambos tienen desplazamientos de distancia de hasta 22 kilómetros en comparación con la fórmula de Vincenty porque utiliza una aproximación elipsoidal de la tierra en lugar de esférica.

Answer 1

Entonces tu quieres:

• ordenar registros por distancia de p0
• seleccionar solo registros cuya distancia de p0 es menor que r

¡El truco es que no necesitas calcular exactamente la gran distancia circular para eso! Puede hacer con cualquier función desde un par de puntos hasta un valor real que crece estrictamente con la gran distancia circular entre los puntos . Hay muchas funciones similares y algunas son mucho más rápidas de calcular que las diversas fórmulas para la distancia exacta de círculo grande. Una de esas funciones es la distancia euclidiana en 3D. La conversión de latitud y longitud a un punto 3D en la esfera no implica funciones trigonométricas inversas.

Una vez que tenga x, Y, Z, puede darse cuenta de que en realidad no necesita la distancia desde p0 hasta su punto, porque también puede usar la distancia desde el plano de la tangente en p0. Esa distancia también crece estrictamente con la gran distancia circular, y se calcula a partir de X, Y, Z como una combinación lineal, no se necesita ni siquiera una raíz cuadrada. Solo necesita calcular previamente los coeficientes y la distancia de corte que corresponde a la distancia de gran círculo deseada.

Answer 2

La Ley de Coseno y la Fórmula Haversine darán resultados idénticos asumiendo una máquina con precisión infinita. La fórmula de Haversine es más robusta a los errores de coma flotante. Sin embargo, las máquinas actuales tienen una precisión doble del orden de 15 figuras significativas, y la ley de los cosenos puede funcionar bien para usted. Ambas fórmulas asumen tierra esférica, mientras que la solución iterativa de Vicenty (la más precisa) supone tierra elipsoidal (en realidad, la tierra ni siquiera es un elipsoide, es un geoide). Algunas referencias: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

Se pone mejor: tenga en cuenta la latitud que se utilizará en la ley de los cosenos, así como la Haversine es la latitud geocéntrica, que es diferente de la latitud geodésica. Para una esfera, estos dos son lo mismo.

¿Cuál es el más rápido de calcular?

En orden de más rápido a más lento están: ley de los cosenos (5 llamadas trigonométricas) -> haversine (implica sqrt) -> Vicenty (tiene que resolver esto iterativamente en un ciclo for)

¿Cuál es más exacto?

Vicenty.

¿Cuál es el mejor cuando se consideran la velocidad y la precisión?

Si su dominio de problema es tal que para las distancias que está tratando de calcular, la tierra puede considerarse plana, entonces puede calcular (no voy a dar detalles) una fórmula de la forma x = kx * diferencia en longitud , y = ky * diferencia en latitud. Luego distance = sqrt (dx dx + dy dy). Si su dominio problemático es tal que se puede resolver con distancia cuadrada, entonces no tendrá que tomar sqrt, y esta fórmula será tan rápida como sea posible. Tiene la ventaja añadida de que puede calcular la distancia vectorial : x es la distancia en dirección este ey es la distancia en la dirección norte. De lo contrario, experimente con el 3 y elija lo que funciona mejor en su situación.