An efficient algorithm for the nearest neighbourhood search for point clouds
This paper presents a high-performance method for the k-nearest neighbourhood search. Starting from a point cloud, first the method carries out the space division by the typical cubic grid partition of the bounding box; then a new data structure is constructed. Based on these two previous steps, an efficient implementation of the k-nearest neighbourhood is proposed. The performance of the method here presented is compared with that of the kd-tree and bd-tree algorithms taken from the ANN library as regards the computing time for some benchmarking point clouds and artificially generated test cases. The results are analysed and critically discussed.
Keywords: k-nearest neighbour, point cloud, space partition
Download Full-Text
ABOUT THE AUTHORS
Luca Di Angelo
Dr Luca Di Angelo obtained his degree in Mechanical Engineering in 1999 at the Faculty of Engineering of L’Aquila and his PhD in Mechanical Engineering in 2002 at the University of ‘Tor Vergata’ in Rome. Since the 2005, he has been a researcher at Faculty of Engineering of L’Aquila, Italy. His research interests include: computational geometry, geometric modelling of functional geometric shape, shape errors modelling and simulation and features based CAD technology. Dr. Luca Di Angelo is co-author over fifty papers in international journals and international conferences.
Luigi Giaccari
Luigi Giaccari received B.S degree and M.S degree in Mechanical Engineering at the Faculty of Engineering of L’Aquila, in 2007 and 2009. Since May 2011, he has been a software developer at ANSYS Germany Gmbh. His research interests include computational geometry and mesh generation. Giaccari is co-author of two papers in international journals and international conferences.
Luca Di Angelo
Dr Luca Di Angelo obtained his degree in Mechanical Engineering in 1999 at the Faculty of Engineering of L’Aquila and his PhD in Mechanical Engineering in 2002 at the University of ‘Tor Vergata’ in Rome. Since the 2005, he has been a researcher at Faculty of Engineering of L’Aquila, Italy. His research interests include: computational geometry, geometric modelling of functional geometric shape, shape errors modelling and simulation and features based CAD technology. Dr. Luca Di Angelo is co-author over fifty papers in international journals and international conferences.
Luigi Giaccari
Luigi Giaccari received B.S degree and M.S degree in Mechanical Engineering at the Faculty of Engineering of L’Aquila, in 2007 and 2009. Since May 2011, he has been a software developer at ANSYS Germany Gmbh. His research interests include computational geometry and mesh generation. Giaccari is co-author of two papers in international journals and international conferences.
