I used kd-tree structure to find a "consistent-closest point" in 3D space. Given a point p in source set S, I want to find a closest point q1 in target set T for p. Then, I check geometric consistency between p and q1. If they are not satisfied, I find second closest point q2 and check geometric consistency again between p and q2. I repeat this process until I find a point qn which is a consistent-closest point for p. Is there any strategy to reduce searching time for this whole process?Thank you!
Thanks Christoph.
In my case, consistent criteria is a small angle between two normals (e.g. normal at p and normal at qi ).
Coherent point drift (cpd) ... This can be used to align ppoints in 2d and 3d ... Implementation is also available online ...
I use Approximate Nearest Neighbor.
It is a C++ package written by David Mount (University of Maryland) and Sunil Arya (Hong Kong University of Science and Technology).
http://www.cs.umd.edu/~mount/ANN/
In the nearest neighbor problem a set of data points in d-dimensional space is given. These points are preprocessed into a data structure, so that given any query point q, the nearest or generally k nearest points of P to q can be reported efficiently. The distance between two points can be defined in many ways. ANN assumes that distances are measured using any class of distance functions called Minkowski metrics. These include the well known Euclidean distance, Manhattan distance, and max distance.
ANN performs quite efficiently for point sets ranging in size from thousands to hundreds of thousands, and in dimensions as high as 20.
The library implements a number of different data structures, based on kd-trees and box-decomposition trees, and employs a couple of different search strategies.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms