我需要找到数据集中每个点的所有最近邻居.数据集包含约. 1000万2D点.数据接近网格,但不形成精确的网格……
此选项排除(在我看来)使用KD树,其中基本假设是没有点具有相同的x坐标和y坐标.
我需要一个快速算法O(n)或更好(但实现起来并不太困难:-)))来解决这个问题…由于boost不是标准化的事实,我不想用它…
感谢您的答案或代码示例……
解决方法
我会做以下事情：
>在点之上创建一个更大的网格.
>线性地遍历这些点,并为每一个点找出它所属的大“单元”(并将点添加到与该单元格相关联的列表中).
(这可以在每个点的恒定时间内完成,只需对点的坐标进行整数除法.)
>现在再次线性地浏览这些点.要找到10个最近的邻居,您只需要查看相邻较大的单元格中的点.
由于您的点数相当均匀,您可以按照与每个(大)单元格中的点数成比例的时间进行此操作.
这是描述情况的(丑陋)图片：
单元格必须足够大(中心),相邻单元格必须包含最接近的10个点,但要小到足以加速计算.您可以将其视为“哈希函数”,您可以在其中找到同一存储桶中的最近点.
(注意严格来说,它不是O(n),但通过调整较大单元格的大小,你应该足够接近.:-)
