2D,C++中的所有k个最近邻居

Question

我需要找到数据集中每个点的所有最近邻居.数据集包含约.1000万2D点.数据接近网格,但不形成精确的网格......

此选项排除(在我看来)使用KD树,其中基本假设是没有点具有相同的x坐标和y坐标.

我需要一个快速算法O(n)或更好(但实现起来并不太困难:-)))来解决这个问题...由于boost不是标准化的事实,我不想用它...

感谢您的答案或代码示例......

Answer 1

我会做以下事情:

1. 在点之上创建更大的网格.

2. 线性地遍历这些点,并且对于它们中的每一个,找出它所属的大"单元"(并将点添加到与该单元相关联的列表中).

   (这可以在每个点的恒定时间内完成,只需对点的坐标进行整数除法.)

3. 现在再次线性地浏览这些点.要找到10个最近的邻居,您只需要查看相邻较大的单元格中的点.

   由于您的点数相当均匀,您可以按照与每个(大)单元格中的点数成比例的时间进行此操作.

这是描述情况的(丑陋)图片:

单元格必须足够大(中心),相邻单元格必须包含最接近的10个点,但要小到足以加速计算.您可以将其视为"哈希函数",您可以在其中找到同一存储桶中的最近点.

(注意严格来说,它不是O(n),但通过调整较大单元格的大小,你应该足够接近.:-)