Algorithm for finding all k-nearest neighbours in three-dimensional scattered points and its application in reverse engineering

X. Li, R. J. Cripps

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1467-1472
Number of pages6
JournalProceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
Volume221
Issue number9
DOIs
StatePublished - 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mechanical Engineering
  • Industrial and Manufacturing Engineering

Keywords

  • Reverse engineering
  • Three-dimensional scattered point data
  • k-nearest neighbours

Fingerprint Dive into the research topics of 'Algorithm for finding all k-nearest neighbours in three-dimensional scattered points and its application in reverse engineering'. Together they form a unique fingerprint.

Cite this