Encontrar el par de puntos más cercano en una esfera

Question

Sé cómo implementar n log n el algoritmo de par de puntos más cercano (Shamos y Hoey) para casos 2D (x e y). Sin embargo, para un problema donde se dan latitud y longitud, este enfoque no se puede usar. La distancia entre dos puntos se calcula usando la fórmula de haversine.

Me gustaría saber si hay alguna forma de convertir estas latitudes y longitudes en sus respectivas coordenadas xey y encontrar el par de puntos más cercano, o si hay otra técnica que pueda usarse para hacerlo.

Answer 1

Los traduciría a coordenadas tridimensionales y luego usaría el divide and conquer approach utilizando un avión en lugar de una línea. Esto definitivamente funcionará correctamente. Podemos estar seguros de esto porque cuando solo se examinan puntos en la esfera, los dos puntos más cercanos por distancia de arco (distancia recorriendo la superficie) también serán los dos más cercanos en una distancia cartesiana 3-d. Esto tendrá un tiempo de ejecución O (nlogn).

Para traducir a coordenadas 3-d, la forma más fácil es hacer (0,0,0) el centro de la tierra y luego sus coordenadas son (cos (lat) * cos (lon), cos (lat) * sin (lan), sin (lat)). Para esos fines, estoy usando una escala para la cual el radio de la Tierra es 1 para simplificar los cálculos. Si quieres distancia en alguna otra unidad, simplemente multiplica todas las cantidades por el radio de la Tierra cuando se mida en esa unidad.

Debo notar que todo esto asume que la tierra es una esfera. No es exactamente uno y los puntos también pueden tener altitud, por lo que estas respuestas no serán del todo exactas, pero estarán casi correctas en casi todos los casos.