摘要
以三维扫描得到的散乱点云为基础,提出了一种基于空间八叉树的快速k近邻搜索算法,通过对点集建立包围盒,利用八叉树记录分割过程,从而使近邻点的搜索只局限于采样点所在的包围盒及其周围的包围盒,并通过剪枝策略使搜索范围进一步缩小。大量真实数据的实验结果表明:该算法可以很好地提高近邻点的搜索速度。
An octree based on the rapid k nearest search was presented for scattered points from 3D scanner. Through the establishment of bounding box on point sets, octree was used to record segmentation process, so that the search of point neighbors was limited to the bounding box of sample points and its neighbor, and through pruning strategies to further narrow the scope of the search. The experiments on a great deal of real data show that the search speed can be well improved.
出处
《计算机应用》
CSCD
北大核心
2008年第8期2046-2048,2051,共4页
journal of Computer Applications
基金
国家自然科学基金资助项目(60475021)
河南省杰出青年基金资助项目(0412000400)
洛阳市科技攻关计划项目(0701041A)
关键词
K近邻
八叉树
包围盒
曲面重建
k-neighbor
octree
bounding box
surface reconstruction