Fast algorithm for finding the k-nearest neighbors of a large-scale scattered point cloud
大规模散乱点的k邻域快速搜索算法

To solve the problem of low efficiency and weak stability in searching the k-nearest neighbors of a large-scale scattered point cloud, a fast algorithm for finding k-nearest neighbors is presented. First, the point cloud data is divided into different sub-spaces by using a space block strategy. Second, the variation of the search step length is controlled dynamically. The accuracy of the algorithm is ensured by the minimum distance from the point to the small cube boundary. Finally, the infinite loop problem due to improper initial values in existing algorithms is avoided by altering the right-side threshold, which controls the number of pre-screening points. The experiment results show that the proposed method obtains not only a good stability for the initial searching step, the step increment, and the sampling density at different topology structures, but also a better performance than the existing algorithms.