Package Bio :: Package KDTree :: Module KDTree' :: Class KDTree
[hide private]
[frames] | no frames]

Class KDTree

source code

object --+
         |
        KDTree


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.

Instance Methods [hide private]
 
__init__(self, dim, bucket_size=1)
x.__init__(...) initializes x; see help(type(x)) for signature
source code
 
all_get_indices(self)
Return All Fixed Neighbor Search results.
source code
 
all_get_radii(self)
Return All Fixed Neighbor Search results.
source code
 
all_search(self, radius)
All fixed neighbor search.
source code
 
get_indices(self)
Return the list of indices.
source code
 
get_radii(self)
Return radii.
source code
 
search(self, center, radius)
Search all points within radius of center.
source code
 
set_coords(self, coords)
Add the coordinates of the points.
source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, dim, bucket_size=1)
(Constructor)

source code 
x.__init__(...) initializes x; see help(type(x)) for signature

Overrides: object.__init__
(inherited documentation)

all_get_indices(self)

source code 
Return All Fixed Neighbor Search results.

Return a Nx2 dim NumPy array containing
the indices of the point pairs, where N
is the number of neighbor pairs.

all_get_radii(self)

source code 
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..

all_search(self, radius)

source code 
All fixed neighbor search.

Search all point pairs that are within radius.

o radius - float (>0)

get_indices(self)

source code 
Return the list of indices.

Return the list of indices after a neighbor search.
The indices refer to the original coords NumPy array. The
coordinates with these indices were within radius of center.

For an index pair, the first index<second index.

get_radii(self)

source code 
Return radii.

Return the list of distances from center after
a neighbor search.

search(self, center, radius)

source code 
Search all points within radius of center.

o center - one dimensional NumPy array. E.g. if the points have
dimensionality D, the center array should be D dimensional.
o radius - float>0

set_coords(self, coords)

source code 
Add the coordinates of the points.

o coords - two dimensional NumPy array. E.g. if the points
have dimensionality D and there are N points, the coords
array should be NxD dimensional.