Class: KDTree

Bio/Tools/KDTree/__init__.py

KD tree implementation (C++, SWIG python wrapper)

The KD tree data structure can be used for all kinds of algorithms that involve N-dimensional points, 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 contains 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. I suspect that the algorithm is described in:

Bentley, Stanat & Williams, "The complexity of finding fixed radius near neighbors", Inf. Proc. Lett., 6, 209-213, 1977

Methods

__init__
get_indices
get_radii
neighbor_get_indices
neighbor_get_radii
neighbor_search
search
set_coords

__init__

__init__ (
        self,
        dim,
        bucket_size=1,
        )

get_indices

get_indices ( self )

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.

get_radii

get_radii ( self )

Return radii.

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

neighbor_get_indices

neighbor_get_indices ( self )

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.

neighbor_get_radii

neighbor_get_radii ( self )

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

neighbor_search

neighbor_search ( self,  radius )

All fixed neighbor search.

Search all point pairs that are within radius.

radius - float (>0)

Exceptions
Exceptions	Exception, "No point set specified"

search (
        self,
        center,
        radius,
        )

Search all points within radius of center.

center - one dimensional Numpy array of type "f". E.g. if the points have dimensionality D, the center array should be D dimensional. o radius - float>0

Exceptions
Exceptions	Exception, "Expected a %i-dimensional Numpy array" % self.dim Exception, "Expected a Numpy array of type float" Exception, "No point set specified"

set_coords

set_coords ( self,  coords )

Add the coordinates of the points.

coords - two dimensional Numpy array of type "f". E.g. if the points have dimensionality D and there are N points, the coords array should be NxD dimensional.

Exceptions
Exceptions	Exception, "Expected a Numpy array of type float" Exception, "Expected a Nx%i Numpy array" % self.dim

Table of Contents

This document was automatically generated on Mon Jul 1 12:03:06 2002 by HappyDoc version 2.0.1