在球體上尋找最接近的一對點

Question

我知道如何在2D情況下（x和y）實現n log n最接近的一對點算法（Shamos和Hoey）。但是，對於經度和緯度的問題，這種方法不能使用。兩點之間的距離使用半正弦公式計算。

我想知道是否有辦法將這些緯度和經度轉換爲它們各自的x和y座標，並找到最接近的一對點，或者是否有另一種技術可以用來做到這一點。

Answer 1

我會將它們翻譯成三維座標，然後使用平面而不是線條使用divide and conquer approach。這一定會正常工作。我們可以確定這一點，因爲當只檢查球體上的點時，弧距離的兩個最近點（走過表面的距離）也將是兩個最接近三維笛卡爾距離的點。這將有運行時間O（nlogn）。要轉換爲三維座標，最簡單的方法是使（0,0,0）爲地球中心，然後座標爲（cos（lat）* cos（lon），cos（lat） *罪（LAN），罪（LAT））。爲了這些目的，我使用了一個地球半徑爲1的刻度，以簡化計算。如果你想要在其他單位的距離，只需在該單位測量所有數量乘以地球半徑。

我應該注意到，這一切都假定地球是一個球體。這不完全是一個點，實際上點也可能有高度，所以這些答案不會完全確切，但在幾乎所有情況下它們都將非常接近正確。