解决最近邻的最佳性能关键算法

Question

我们有一个x，y对的列表。每对代表2D空间上的一个点。我想找到这个列表中最接近的点，到特定点xq，yq。针对此问题的最佳性能关键算法是什么？点的Lisp不会改变;这意味着我不需要执行插入和删除。我想在这个集合中找到目标xq，yq点的最近邻居。

编辑1：谢谢大家！正如Stephan202猜对了，我想反复这样做;像一个功能。列表不一定是排序的（实际上我不明白它是如何排序的？就像一个主键为2列a和y的表？如果有帮助那么我会对它进行排序）。

我将基于列表一次构建数据结构，然后我将在函数中使用此生成的数据结构（如果此过程本身是相关的）。

谢谢雅各布;似乎KD-Tree数据结构是一个很好的候选者（我觉得它是。我会在得到一些相关结果时更新）。

编辑2：我发现，这个问题被命名为“最近邻居”！

编辑3：第一个标题是“寻找算法（用于空间查询和空间索引）（最近邻）”;我选择了一个新标题：“解决最近邻居的最佳性能关键算法”。由于我不想对我的初始数据执行插入和删除操作，并且我只想从它们中最近的一个到新点（不会插入），我选择（当前）处理KD-Trees。谢谢大家！

Answer 1

正如Stephan202所指出的，如果你打算找到一个以上点的最接近匹配，你应该使用一棵树。

我会推荐一个KD树，它的实现很容易在几个软件包中找到，比如 OpenCV 2.0 。或者你可以自己实现一个！

编辑：我问了一个关于kd-tree实现的问题这里 - 可能有用。

编辑： KD-tree已被广泛用于NN搜索:) - 此外，如果您愿意接受大概匹配，您可以使用近似最近邻居（FLANN）的快速库。 FLANN实现存在于 OpenCV 2.0 中。

如果您不想要近似答案，可以调整FLANN参数以搜索整个树。

Answer 2

如果查询点（xq，yq）发生变化而列表没有变化，则需要计算点列表的 Voronoi图 。这将为您提供一组多边形或“单元格”。 （其中一些是无限的）;每个多边形对应于原始列表中的一个点，称为“站点”。那个细胞。完全位于一个多边形内的任何点都比该原始列表上的其他站点更接近该多边形的位置。两个多边形之间的边界上的任何点距离每个站点都相同。

一旦你走得那么远，你需要一个简单的方法来确定你所在的多边形。这被称为 点位置问题 。

对于这类事情，一本非常非常好的书是计算几何：算法和应用。他们详细讨论了Voronoi图计算和点位置的梯形板法。

如果您不想自己编写代码而不想编写代码，那么请尝试 CGAL 将为您完成大部分工作。这可能也适用于KD树的答案，但我不知道。

Answer 3

您需要空间索引。

如果你自己动手，你可以比选择 R-Tree 或四叉树算法。

Answer 4

我会选择四叉树。它是最简单的空间结构。在2维中，我通常会推荐使用quadtree而不是kd-tree，因为它更简单，更快。如果尺寸数量很大，它的缺点是更多的内存消耗，但是在2维的情况下，差异并不显着。

如果您的坐标是浮点类型，那么有一个很好的优化技巧： 在查询中，您首先必须找到包含要求最近点的点的叶节点。要做到这一点，你必须从树根到叶子进入树 - 在每次迭代中决定要踩到哪个子节点。 将子节点的标识符/地址存储在Node结构中的4大小数组中。数字化查询算法中的点坐标。然后，只需将数组索引数字化点坐标的2个正确位，就能找到合适的子节点。数字化很快：使用简单的static_cast实现它。

但是首先在没有优化的情况下实现四叉树，因为很容易出现位操作的错误。即使没有这种优化，它仍然是最快的解决方案。

Answer 5

使用距离公式迭代每个其他点以找到距Q（xq，yq）的最小距离。

但是，您没有提供足够的信息来表达对性能至关重要的答案。

例如，如果Q是一个非常常见的点，您可能想要计算到Q的距离并将其存储在每个点上。

第二个例子，如果您有大量的点，您可以将这些点组织成各个部分，并从仅包含Q的部分的相同部分和相邻部分开始。