在球体上寻找最接近的一对点

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的刻度，以简化计算。如果你想要在其他单位的距离，只需在该单位测量所有数量乘以地球半径。

我应该注意到，这一切都假定地球是一个球体。这不完全是一个点，实际上点也可能有高度，所以这些答案不会完全确切，但在几乎所有情况下它们都将非常接近正确。