algorithm - 在球体上找到最近的一对点

Question

我知道如何为 2D 案例（x 和 y）实现 n log n 最接近点对算法（Shamos 和 Hoey）。但是，对于给出纬度和经度的问题，不能使用这种方法。两点之间的距离是使用半正弦公式计算的。

我想知道是否有某种方法可以将这些纬度和经度转换为它们各自的 x 和 y 坐标并找到最近的一对点，或者是否有另一种技术可以用来做到这一点。

Answer 1

我会将它们转换为三维坐标，然后使用平面而不是线来使用分而治之的方法。这肯定会正常工作。我们可以确信这一点，因为当仅检查球体上的点时，弧距离（在表面上行走的距离）最近的两个点也将是 3-d 笛卡尔距离最近的两个点。这将具有运行时间 O(nlogn)。

要转换为 3-d 坐标，最简单的方法是将 (0,0,0) 设为地球的中心，然后您的坐标为 (cos(lat)*cos(lon),cos(lat)*sin(lan) ),sin(lat))。出于这些目的，我使用地球半径为 1 的比例来简化计算。如果您想要其他单位的距离，只需将所有数量乘以以该单位测量时的地球半径。

我应该注意到，所有这些都假设地球是一个球体。它不完全是一个，并且点实际上也可能具有高度，因此这些答案不会完全准确，但它们几乎在每种情况下都非常接近正确。