Bio ::
KDTree ::
KDTree ::
KDTree ::
Class KDTree
|
|
Class KDTree
source code
KD tree implementation (C++, SWIG python wrapper)
The KD tree data structure can be used for all kinds of searches that
involve N-dimensional vectors, e.g. neighbor searches (find all points
within a radius of a given point) or finding all point pairs in a set
that are within a certain radius of each other.
Reference:
Computational Geometry: Algorithms and Applications Second Edition
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf
published by Springer-Verlag 2nd rev. ed. 2000. ISBN: 3-540-65620-0
The KD tree data structure is described in chapter 5, pg. 99.
The following article made clear to me that the nodes should contain
more than one point (this leads to dramatic speed improvements for the
"all fixed radius neighbor search", see below):
JL Bentley, "Kd trees for semidynamic point sets," in Sixth
Annual ACM Symposium on Computational Geometry, vol. 91. San Francisco,
1990
This KD implementation also performs a "all fixed radius neighbor
search", i.e. it can find all point pairs in a set that are within a
certain radius of each other. As far as I know the algorithm has not been
published.
Add the coordinates of the points.
o coords - two dimensional Numeric array of type "f". E.g.
if the points have dimensionality D and there are N points, the coords
array should be NxD dimensional.
|
Search all points within radius of center.
o center - one dimensional Numeric array of type "f". E.g.
if the points have dimensionality D, the center array should be D
dimensional. o radius - float>0
|
Return radii.
Return the list of distances from center after a neighbor search.
|
Return the list of indices.
Return the list of indices after a neighbor search. The indices refer
to the original coords Numeric array. The coordinates with these indices
were within radius of center.
For an index pair, the first index<second index.
|
All fixed neighbor search.
Search all point pairs that are within radius.
o radius - float (>0)
|
Return All Fixed Neighbor Search results.
Return a Nx2 dim Numeric array containing the indices of the point
pairs, where N is the number of neighbor pairs.
|
Return All Fixed Neighbor Search results.
Return an N-dim array containing the distances of all the point pairs,
where N is the number of neighbor pairs..
|