小编典典

查找球体上最接近的点对

algorithm

我知道如何为2D情况(x和y)实现n log
n个最接近的对点算法(Shamos和Hoey)。但是,对于给出纬度和经度的问题,无法使用此方法。两点之间的距离是使用Haversine公式计算的。

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


阅读 288

收藏
2020-07-28

共1个答案

小编典典

我将它们转换为三维坐标,然后使用分而治之的方法,即使用平面而不是直线。这绝对可以正常工作。我们可以放心,因为当仅检查球体上的点时,两个最接近的圆弧距离点(在曲面上行走的距离)也将是最接近的三个3d笛卡尔距离。这将具有运行时间O(nlogn)。

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

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

2020-07-28