algorithm - 找到一组点的最近点（以纬度/经度为单位）

Question

我得到了一组随机的点（不知道有多少），它们有纬度和经度，需要对它们进行排序。

然后我将获得另一个随机点（纬度/经度），并且需要找到最接近它的点（从上面的集合中）。

当我实现线性搜索（将集合放在列表中，然后计算所有距离）时，它需要的时间大约是允许的 7 倍。

所以，我需要一个更有效的排序算法，但我不确定如何做到这一点，特别是因为我得到了平面上不存在的点。

Answer 1

如果您的点分布适中，那么几何散列是一种在实践中加速最近邻搜索的简单方法。这个想法只是在网格单元格中注册您的对象并按单元格进行搜索，以便您可以将搜索限制在本地社区。

这个小Python 演示将这个想法应用于平面上的圆圈：

因此，在您的情况下，您可以选择一些固定的 N 并将 [0, 2pi] 中的经度坐标分成 N 等份，将 [0, pi] 中的纬度坐标分成 N 份。这会在球体上为您提供 N^2 个单元格。您在这些单元格中注册所有初始点。

当您获得查询点 p 时，您开始在被 p 命中的单元格中搜索，并且在足够大的邻域中进行搜索，这样您就不会错过最近的点。

如果您最初注册 n 个点，那么您可以选择 N 到类似 sqrt(n)/4 左右。