Logo Search packages:      
Sourcecode: python-biopython version File versions

Bio::KDTree::KDTree::KDTree Class Reference

List of all members.

Detailed Description

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.


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

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.

Definition at line 88 of file KDTree.py.

Public Member Functions

def __init__
def all_get_indices
def all_get_radii
def all_search
def get_indices
def get_radii
def search
def set_coords

Public Attributes


The documentation for this class was generated from the following file:

Generated by  Doxygen 1.6.0   Back to index