Znalezienie najbliższej pary punktów na kuli

Question

Wiem, jak zaimplementować n log n najbliższą parę algorytmów punktów (Shamos i Hoey) dla przypadków 2D (x i y). Jednak w przypadku problemu dotyczącego szerokości i długości geograficznej nie można zastosować tego podejścia. Odległość między dwoma punktami oblicza się za pomocą formuły haversine.

Chciałbym wiedzieć, czy jest jakiś sposób na zamianę tych szerokości i długości na ich odpowiednie współrzędne X i Y i znalezienie najbliższej pary punktów, lub jeśli istnieje inna technika, która może być wykorzystana do tego.

Answer 1

Przetłumaczyłbym je na współrzędne trójwymiarowe, a następnie użyłbym divide and conquer approach używając raczej płaszczyzny niż linii. To z pewnością zadziała poprawnie. Możemy być tego pewni, ponieważ gdy tylko badamy punkty na kuli, dwa najbliższe punkty w zależności od odległości łuku (odległość chodzenia po powierzchni) będą również najbliższymi odległościami kartezjańskimi 3-d. Będzie to miało czas działania O (nlogn).

Aby przetłumaczyć na współrzędne 3-d, najłatwiejszym sposobem jest ustawienie (0,0,0) środka ziemi, a następnie podanie współrzędnych (cos (lat) * cos (lon), cos (lat) * sin (lan), sin (lat)). Do tych celów używam skali, dla której promień Ziemi wynosi 1, aby uprościć obliczenia. Jeśli chcesz uzyskać odległość w jakiejś innej jednostce, po prostu pomnóż wszystkie ilości przez promień Ziemi, gdy zmierzona w tej jednostce.

Muszę zauważyć, że wszystko to zakłada, że ​​Ziemia jest kulą. Nie jest to dokładnie jedna, a punkty mogą również mieć wysokość, więc te odpowiedzi nie będą tak naprawdę dokładne, ale prawie zawsze będą poprawne.