基于球分割的空间二叉树检索算法(sphere-kdtree)

sphere-kdtree算法思路说明

具体思路如下:

第一、球半径分割,即利用不同的球半径,将三维空间点(向量)分割成多块。所以首先要求确定的就是分割多少块,怎么设置半径最合理。

第二、三维空间点平衡二叉树的实现,也就是kdtree的思想,平衡二叉树的建立,但要尽可能避免树的两个分支数量差异较大,采用了均值分割。

第三、挂载,即利用第二步的建树方法,分别在第一步中的分块中进行二叉树的建立。

第四、空间knn检索的实现,首先判断属于求分割的哪个块,并定位到查询点的叶子节点,利用回溯法,遍历相应的兄弟叶子节点;同样方法检索相邻块,更新检索结果。

图1、块的分割

图2、 树建立

代码测试:对70万点,进行遍历检索其周围5个点,用时28s,与PCL的kdtree检索速度相当。目前用时主要在建树过程,以及相邻块检索上,后面准备利用多线程加速。

 

 

 

 

 

 

原文地址:https://www.cnblogs.com/lovebay/p/11477004.html