Improved KNN algorithm for scattered point cloud

Aiming at the k-nearest neighbors algorithm for scatter point cloud data, an improve method has been proposed based on dimension reduction and sorting. In the improved algorithm, the main directions of point cloud data need to be solved according to PCA (Principal Components Analysis) to analyze the spatial distribution of point cloud data. After that, rotate the main directions to coincide with the X, Y, Z axis, sort the point cloud data in the three coordinate axis and find the position of query point. Then extract neighbor points in the three sorted point cloud data set in proportion respectively and calculate the distance between the query point and neighbors. Finally, sorting the distance, the first k points searched is the k-nearest neighbors. The algorithm improved in this paper reduces greatly the times of point to point distance calculation, where k-nearest neighbors are able to be obtained only after three times sorting and a small amount of calculation. Simultaneously, it improves the efficiency of KNN algorithm, which saves a lot of time to solve the normal vector of point cloud, reconstruct surface or other operations. The experimental result shows the effectiveness of the improved KNN algorithm.