散乱数据点的k近邻搜索算法

K-neighbor Searching of Surface Reconstruction From Scattered Points

文章提出了一种基于八叉树的快速k近邻搜索算法,即通过对点集建立包围盒,利用八叉树记录分割过程,从而使近邻点的搜索只局限于采样点所在包围盒及周围的包围盒,并通过剪枝策略,使搜索范围近一步缩小,提高了搜索的速度,并能对噪声点自动删除。

In this paper, a method to find the k-neighbor of points very quickly which is based on octree,is provided. K-neighbor searching method builds up the envelopment-box of points first, then divides the box and records the dividing process by octree. This method limits the searching range to the point＇s envelopment-box and its neighbor boxes, and reduces the searching range uheriorly by pruning means. This method has some excellent characters such as quick speed, automatic deleting of yawp points.