在球面上寻找最近的点对

Question

6

我知道如何实现n log n的最近点对算法（Shamos和Hoey）用于2D情况（x和y）。然而，对于给定纬度和经度的问题，这种方法无法使用。两点之间的距离是使用haversine公式计算的。

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

- Varun Sharma

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keith Irwin · Accepted Answer

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

转换为3D坐标的最简单方式是以地球中心(0,0,0)为原点，坐标为(cos(lat)*cos(lon),cos(lat)*sin(lon),sin(lat))。为了简化计算，我使用了一个比例尺，使地球的半径为1。如果需要其他单位的距离，请将所有量乘以地球在该单位下的半径。

值得注意的是，这一切都假设地球是一个球体。它并不完全是一个球体，点可能实际上也有高度，因此这些答案可能不是完全准确的，但在几乎每种情况下都非常接近正确。