最近点算法

Question

我有一个包含约5000个经纬度对的列表，我想找到其中离用户指定的另一点最近的5个点。

你能否建议一个有效的算法来解决这个问题？我在Ruby中实现这个算法，所以如果有合适的库那就更好了，但是我仍然对算法很感兴趣！

更新：有几个人要求更具体地解释这个问题。因此，在此提供更多细节：

- 这5000个点大部分都在同一个城市内。可能会有一些在城市外，但可以安全地假设99%的点在75公里半径内，所有点都在200公里半径内。 - 点的列表变化很少。为了论证，我们假设它每天更新一次，在那段时间内我们必须处理几千个请求。

- thomson_matt

---

如果只有那么几个点，一个一个地去做也没关系。 - Andrey

无论您选择哪种算法，通过比较平方距离而不是实际距离，可以节省一些时间。如果您不需要知道实际距离，则无需执行平方根运算。 - Lars Haugseth

Answer 1

你可以通过使用四叉树或kd-tree对二维空间进行分区来加速搜索，然后一旦到达叶节点，就逐个比较剩余的距离，直到找到最接近的匹配项。

另请参见这篇博客文章，其中提到了在Ruby中使用kd-trees进行最近邻搜索的另一篇博客文章。

- Gregory Pakosz

---

总的来说，这是一个好主意，但如果有5000个点，创建数据结构所需的时间将比手动计算所有可能的距离更长。 - Gleno

Answer 2

您可以使用曼哈顿距离（针对纬度进行缩放）获得非常快速的距离上限估计器，这应该足以拒绝99.9％的候选者，如果它们不接近（编辑：因为后来您告诉我们他们很接近。在这种情况下，根据Lars H的评论，您的度量应该是距离平方）。 将其视为拒绝任何在球形矩形边界框之外的内容（作为圆形边界框的近似）。 我不会Ruby，因此这里是带有伪代码的算法： 让您的参考点P（pa，po）和另一个点X（xa，xo）的纬度和经度。 预先计算ka，经度距离的纬度缩放因子：ka（= cos（pa in°））。 （严格地说，ka =常数是P附近的线性化近似。） 然后，距离估计器是：D（X，P）= ka * | xa-pa | + | xo-po | = ka * da + do 其中| z |表示abs（z）。最坏的情况下，这会将真实距离高估√2倍（当da == do时），因此我们按如下方式允许： 运行搜索并保持Dmin，第五个最小的比例曼哈顿距离估计。 因此，您可以拒绝所有D（X，P）>√2 * Dmin的点（因为它们必须至少比√（（ka * da）² + do²）远 - 这应该消除99.9％的点）。 保留所有剩余候选点的列表，其中D（X，P）<=√2 * Dmin。如果找到新的第五个最小值D，则更新Dmin。优先队列或者坐标，D的列表是很好的数据结构。 请注意，我们从未计算欧几里得距离，只使用浮点乘法和加法。 （将其视为四叉树类似，但过滤掉除了我们感兴趣的区域之外的所有内容，因此无需预先计算准确的距离或构建数据结构。） 如果您告诉我们纬度，经度的期望差异（度，分或其他什么？如果所有点都很接近，则此估计器中的√2因子将过于保守并将每个点标记为候选；基于查找表的距离估计器将更可取。）。 伪代码：

initialize Dmin with the fifth-smallest D from the first five points in list
for point X in list:
    if D(X,P) <= √2 * Dmin:
        insert the tuple (X,D) in the priority-queue of candidates
        if (Dmin>D): Dmin = D
# after first pass, reject candidates with D > √2 * Dmin (use the final value of Dmin)
# ...
# then a second pass on candidates to find lowest 5 exact distances

- smci

Answer 3

由于你的列表相当短，我强烈建议使用暴力方法。只需将所有5000个点与用户指定点进行比较即可。这将是O(n)，而且你会得到酬劳。

除此之外，四叉树或Kd树是空间细分的常用方法。但在你的情况下，你将最终需要对树进行线性插入操作，然后进行恒定数量的对数查找……当你可以更好地进行线性距离比较并完成时，这有些浪费。

现在，如果你想找到N个最近的点，则需要计算距离排序并取前N个，但这仍然是O(n log n)的。

编辑：值得注意的是，如果你要重复查询点列表，则构建空间树将变得有价值。

- Michael

Answer 4

对于5000个节点，我会计算每个节点的单独x+y距离，而不是直线距离，这样比纯暴力更好。

一旦你排好了那个列表，如果第5个节点的x+y为38，你可以排除任何x或y距离大于38的节点。这样，你就可以在不必计算直线距离的情况下排除很多节点。然后对剩余的节点进行暴力计算直线距离。

- asc99c

Answer 5

这些算法不容易解释，因此我只能给你一些指向正确方向的提示。你应该寻找Voronoi图。通过Voronoi图，你可以在O(n^2 log n)的时间内轻松预先计算一个图，并在O(log n)的时间内搜索最近的点。

预处理是在晚上进行的定时作业，搜索是实时进行的。这符合你的规格。

现在，你可以保存每个5000个点中最接近的k对，然后从Voronoi图中最近的点开始搜索剩下的四个点。

但请注意，这些算法并不是很容易实现。

一个好的参考资料是：

• de Berg:计算几何算法应用(2008)第7.1章和第7.2章

- ayckoster

Answer 6

由于您只有这么少的点，我建议进行暴力搜索，即尝试将所有点相互比较，其操作为O(n^2)，其中n = 5000，或大约250万次适当算法的迭代，并仅存储相关结果。在C中，这将具有小于100毫秒的执行时间，因此在Ruby中最多需要一两秒钟。

当用户选择一个点时，您可以使用存储的数据以恒定的时间给出结果。

编辑 我重新阅读了您的问题，似乎用户提供自己的最后一个点。在这种情况下，每次用户提供一个点时，直接通过您的集合进行O(n)线性搜索会更快。

- Gleno

Answer 7

如果您需要多次重复此操作，且输入位置不同，但又不想实现四叉树（或找不到库的实现），那么可以使用一种基本直观的局部敏感哈希（kind-of）方法：

• 将您的 (x,y) 对取出并创建两个列表，一个是 (x, i) ，另一个是 (y, i)，其中 i 是点的索引。
• 对这两个列表进行排序。

当给定一个点 (X,Y) 时，

• 对 X 和 Y 进行二分排序。
• 同时沿着两个列表向外扩展，查找共同的索引。
• 对于相同的索引，计算精确距离。
• 当 X 和 Y 的差异超过当前最远的 5 个点的精确距离时，停止扩展。

所有你要做的就是说附近的点必须具有相似的 x 值和相似的 y 值...

- andrew cooke