TY - JOUR
T1 - Algorithm for finding all k-nearest neighbours in three-dimensional scattered points and its application in reverse engineering
AU - Li, X.
AU - Cripps, R. J.
PY - 2007
Y1 - 2007
N2 - A fast and exact algorithm for computing the k-nearest neighbours, or k-closest points in terms of Euclidean distance, for all data in three-dimensional point clouds is presented that avoids using complicated Voronoi diagrams or Dirichlet tessellations. Experimental evidence suggests that the algorithm has a timing of O(n) for most practical values of k under the condition: k <0.05n, where n is the number of three-dimensional points in the cloud. Case studies are presented to illustrate the robustness and efficiency of the method and a comparison is made to an existing exact method.
AB - A fast and exact algorithm for computing the k-nearest neighbours, or k-closest points in terms of Euclidean distance, for all data in three-dimensional point clouds is presented that avoids using complicated Voronoi diagrams or Dirichlet tessellations. Experimental evidence suggests that the algorithm has a timing of O(n) for most practical values of k under the condition: k <0.05n, where n is the number of three-dimensional points in the cloud. Case studies are presented to illustrate the robustness and efficiency of the method and a comparison is made to an existing exact method.
KW - Reverse engineering
KW - Three-dimensional scattered point data
KW - k-nearest neighbours
UR - http://www.scopus.com/inward/record.url?scp=38149011510&partnerID=8YFLogxK
U2 - 10.1243/09544054JEM477
DO - 10.1243/09544054JEM477
M3 - Article
AN - SCOPUS:38149011510
SN - 0954-4054
VL - 221
SP - 1467
EP - 1472
JO - Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
JF - Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
IS - 9
ER -