Study on a Nearest Neighbor Algorithm for Point Clouds Based on the Space Partition Principle
Xue Chang Zhang, Tao Liang, Yan Mei Tang, Xu Zhang · Applied Mechanics and Materials · 2012
In the product modeling based on the reverse engineering, the point cloud data smoothing and multi-view point cloud data registration will be related to search some nearest neighbor points. The search speed will determine the efficiency of product modeling in some cases. The paper analysis the nearest neighbor point query algorithms, KD tree and Range tree, based on the space partition principle. The tree structure creation and query method are described by pseudo-code in the paper. Finally, the experimental results involving different sizes point clouds demonstrate that KD tree and Range tree have their own advantages in space storage and time complexity. Two data strictures all meet the efficiency of the search algorithm.