6

我们有一个 x,y 对的列表。每对代表二维空间上的一个点。我想从这个列表中找到离特定点 xq,yq 最近的点。这个问题的最佳性能关键算法是什么？Lisp of points 不会改变；这意味着我不需要执行插入和删除。我只想找到这个集合中目标 xq,yq 点的最近邻居。

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

我会根据列表构造一次数据结构，然后我会在函数中使用这个生成的数据结构（如果这个过程本身是相关的）。

谢谢雅各布；KD-Tree 数据结构似乎是一个很好的答案候选者（我觉得确实如此。当我得到一些相关结果时，我会更新）。

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

编辑 3：第一个标题是“In Search of an Algorithm (for Spatial-Querying and Spatial-Indexing) (Nearest Neighbor)”；我选择了一个新标题：“解决最近邻的最佳性能关键算法”。由于我不想对我的初始数据执行插入和删除操作，而我只想要离它们最近的一个到一个新点（不会被插入），我选择（当前）在 KD-Trees 上工作。谢谢大家！

4

5 回答 5

10

正如 Stephan202 所指出的，如果您打算找到多个点的最接近匹配，则应该使用树。

我会推荐一个 KD-tree，它的实现可以很容易地在OpenCV 2.0等几个包中找到。或者你可以自己实现一个！

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

编辑： KD-trees 已成功广泛用于 NN 搜索:) - 此外，如果您愿意接受近似匹配，您可以使用Fast Library for Approximate Nearest Neigbor (FLANN)。FLANN 实现存在于OpenCV 2.0中。

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

于 2009-10-28T20:22:55.480 回答
7

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

一旦你走到那一步，你需要一种简单的方法来确定你所在的多边形。这就是所谓的点定位问题。

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

如果您不想自己编写代码，而且您不应该这样做，那么请尝试获取一个像CGAL这样的库来为您完成大部分工作。这可能也适用于 KD-tree 答案，但我并不具体知道。

于 2009-10-28T20:29:00.117 回答
5

你需要一个空间索引。

如果你自己动手，你可以做得比选择R-Tree或Quad-tree算法差得多。

于 2009-10-28T20:42:29.653 回答
1

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

如果您的坐标是浮点类型，则有一个很好的优化技巧：在查询中，您首先必须找到包含询问最近点的点的叶节点。为此，您必须在树中从根到叶 - 在每次迭代中决定要踩到哪个子节点。将子节点的标识符/地址存储在 Node 结构中的 4 大小数组中。将查询算法中的点坐标数字化。然后，您只需通过数字化点坐标的 2 个适当位对数组进行索引，就可以找到适当的子节点。数字化速度很快：用一个简单的 static_cast 实现它。

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

于 2009-10-31T00:41:25.813 回答
0

使用距离公式遍历所有其他点以找到与 Q (xq,yq) 的最小距离。

但是，您没有为性能关键的答案提供足够的信息。

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

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

于 2009-10-28T20:10:28.480 回答