我需要为数据集的每个点找到它所有最近的邻居。数据集包含大约。1000 万个二维点。数据接近网格，但没有形成精确的网格……
此选项排除（在我看来）使用 KD 树，其中基本假设是没有点具有相同的 x 坐标和 y 坐标。
我需要一个快速算法 O(n) 或更好的算法（但实现起来不太难:-)））来解决这个问题......由于 boost 没有标准化，我不想使用它......
感谢您的回答或代码示例...
问问题
10334 次
2 回答
10
我会做以下事情：
在点的顶部创建一个更大的网格。
线性地遍历这些点，对于它们中的每一个，找出它属于哪个大“单元格”（并将这些点添加到与该单元格关联的列表中）。
（这可以在每个点的恒定时间内完成，只需对点的坐标进行整数除法。）
现在再次线性地通过这些点。要查找最近的 10 个邻居，您只需查看相邻的较大单元格中的点。
由于您的点分布相当均匀，因此您可以按每个（大）单元格中的点数成比例地执行此操作。
这是描述情况的（丑陋的）图片：
单元格必须足够大，以便（中心）和相邻单元格包含最近的 10 个点，但又足够小以加快计算速度。您可以将其视为“哈希函数”，您可以在其中找到同一个存储桶中最近的点。
（请注意，严格来说它不是O(n)，而是通过调整较大单元格的大小，您应该足够接近。:-)
于 2010-11-13T11:57:03.867 回答
1
我使用了一个名为ANN（近似最近邻）的库并取得了巨大的成功。它确实使用了 Kd-tree 方法，尽管有不止一种算法可供尝试。我将它用于三角曲面上的点定位。你可能有一些运气。它是最小的，只需放入它的源代码就可以很容易地包含在我的库中。
祝这个有趣的任务好运！
于 2010-11-16T11:13:20.027 回答