Study on a Nearest Neighbor Algorithm for Point Clouds Based on the Space Partition Principle

Abstract:

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.

• Periodical: Applied Mechanics and Materials (Volumes 201-202)
• Pages: 834-837
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.201-202.834
• Online since: October 2012
• Authors: Xue Chang Zhang, Tao Liang, Yan Mei Tang, Xu Zhang
• Keywords: KD Tree, Nearest Neighbor Query, Range Tree, Space Partition Principle

References

[1] Y.H. Liu: Image vision computing, Vol. 24 (2006), pp.762-781.

[2] X.C. Zhang, X.J. Gao: Applied mechanics and materials, Vol. 101-102 (2012), pp.232-235.

[3] Z.X. Xie, S. Xu, X.Y. Li: Image and vision computing, Vol. 28 (2010), pp.563-570.

[4] X.C. Zhang, J.T. Xi, J.Q. Yan: International Journal of Advanced Manufacturing Technology, Vol. 30 (2006), pp.70-75.

[5] S. Kim, N.W. Cho, B. Kang, S. Kang, Expert systems with applications, Vol. 38 (2011), pp.9587-9596.

[6] J. Sankaranarayanan, H. Samet, A. Varshney: Computers and graphics, Vol. 31(2007), pp.157-174.

[7] M.D. Berg, M.V. Kreveld, M. Overmars, O. Schwarzkopf: Computational geometry algorithms and applications. (Springer. Germany 1998).

DOI: 10.1007/978-3-662-03427-9