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

概述我需要找到数据集中每个点的所有最近邻居.数据集包含约. 1000万2D点.数据接近网格,但不形成精确的网格…… 此选项排除(在我看来)使用KD树,其中基本假设是没有点具有相同的x坐标和y坐标. 我需要一个快速算法O(n)或更好(但实现起来并不太困难:-)))来解决这个问题…由于boost不是标准化的事实,我不想用它… 感谢您的答案或代码示例…… 我会做以下事情： >在点之上创建一个更大的网格. > 我需要找到数据集中每个点的所有最近邻居.数据集包含约. 1000万2D点.数据接近网格,但不形成精确的网格……

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

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

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

解决方法 我会做以下事情：

>在点之上创建一个更大的网格.
>线性地遍历这些点,并为每一个点找出它所属的大“单元”(并将点添加到与该单元格相关联的列表中).

(这可以在每个点的恒定时间内完成,只需对点的坐标进行整数除法.)
>现在再次线性地浏览这些点.要找到10个最近的邻居,您只需要查看相邻较大的单元格中的点.

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

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

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

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

总结

以上是内存溢出为你收集整理的2D,C中的所有k个最近邻居全部内容，希望文章能够帮你解决2D,C中的所有k个最近邻居所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。