逆向工程中散乱点云的K邻域搜索算法研究

Research of K-nearest neighbors search algorithm in reverse engineering

针对逆向工程中散乱点云的K邻域搜索,提出了一种快速、精确的散乱点云K邻域搜索算法。该算法根据点云包围盒的大小,点的总数以及邻域点的个数,采用二次空间划分的策略,以确定合适的立方体小栅格的梭长,从而保证立方体小栅格里点的个数相对均匀。然后,建立以采样点为中心的球体、该点到所对应的立方体小栅格环六壁的距离为半径的取值范围,依次增加该球体的半径,以球体内有K个点为中止条件,可以快速完成采样点的K邻域搜索。与已有算法相比,该算法具有较高的搜索效率。

For computing the K-nearest neighbors in reverse engineering, a fast and exact K-nearest neighbors search algorithm was proposed.Through twice spatial partitioning,the size of cell grids was appro- priately estimated to ensure the number of points in cell grids well-distributed by overall considering the size of bounding box,the total numbers of points and the numbers of nearest neighbors.Then the algorithm assumes that there is a sphere centered at any point of the scattered points with the range of radius, namely the distances between the point and each face of the cube containing it.With the growth of radius the sphere contains all the K-nearest-neighbor,and the algorithm considers this as the only terminal condition.K- nearest neighbors of the point can be found quickly.In comparison with the existing methods,the proposed algorithm has more efficient performance.