A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud

To solve the problem of low efficiency and non-uniform blocking when searching nearest neighbors in large-scale scattered point clouds, a fast algorithm for finding k-nearest neighbors is presented. Firstly, a point cloud is blocked adaptively in the coordinate directions according to the point number threshold of a sub-block. Secondly, the initial small cube is created using the minimum distance from the point to the sub-block boundary, and the size of the small cube is changed dynamically based on a threshold; that is, the amount of points in a small cube to narrow down the search extent of k-neighbors. Thirdly, the expansion direction is determined by the outer normal vector of the corresponding side, which is the side nearest to a unsuccessful searching point. The maximal distance from the unsuccessful searching point to the side is taken as a step to expand the sub-block quantitatively. Experimental results show that the proposed method is not only stable, but also is more automatic with better performance.