Back to index

python-biopython  1.60
Public Member Functions | Public Attributes
Bio.KDTree.KDTree.KDTree Class Reference

List of all members.

Public Member Functions

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

Public Attributes

 dim
 kdt
 built
 neighbors

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.

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.

Definition at line 91 of file KDTree.py.


Constructor & Destructor Documentation

def Bio.KDTree.KDTree.KDTree.__init__ (   self,
  dim,
  bucket_size = 1 
)

Definition at line 124 of file KDTree.py.

00124 
00125     def __init__(self, dim, bucket_size=1):
00126         self.dim=dim
00127         self.kdt=_CKDTree.KDTree(dim, bucket_size)
00128         self.built=0

Here is the caller graph for this function:


Member Function Documentation

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.

Definition at line 200 of file KDTree.py.

00200 
00201     def all_get_indices(self):
00202         """Return All Fixed Neighbor Search results.
00203 
00204         Return a Nx2 dim NumPy array containing
00205         the indices of the point pairs, where N
00206         is the number of neighbor pairs.
00207         """
00208         a = array([[neighbor.index1, neighbor.index2] for neighbor in self.neighbors])
00209         return a

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

Definition at line 210 of file KDTree.py.

00210 
00211     def all_get_radii(self):
00212         """Return All Fixed Neighbor Search results.
00213 
00214         Return an N-dim array containing the distances
00215         of all the point pairs, where N is the number 
00216         of neighbor pairs..
00217         """
00218         return [neighbor.radius for neighbor in self.neighbors]

def Bio.KDTree.KDTree.KDTree.all_search (   self,
  radius 
)
All fixed neighbor search.

Search all point pairs that are within radius.

o radius - float (>0)

Definition at line 189 of file KDTree.py.

00189 
00190     def all_search(self, radius):
00191         """All fixed neighbor search.
00192 
00193         Search all point pairs that are within radius.
00194 
00195         o radius - float (>0)
00196         """
00197         if not self.built:
00198                 raise Exception("No point set specified")
00199         self.neighbors = self.kdt.neighbor_search(radius)

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. 

Definition at line 172 of file KDTree.py.

00172 
00173     def get_indices(self):
00174         """Return the list of indices.
00175 
00176         Return the list of indices after a neighbor search.
00177         The indices refer to the original coords NumPy array. The
00178         coordinates with these indices were within radius of center.
00179 
00180         For an index pair, the first index<second index. 
00181         """
00182         a=self.kdt.get_indices()
00183         if a is None:
00184             return []
00185         return a

Return radii.

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

Definition at line 161 of file KDTree.py.

00161 
00162     def get_radii(self):
00163         """Return radii.
00164 
00165         Return the list of distances from center after
00166         a neighbor search.
00167         """
00168         a=self.kdt.get_radii()
00169         if a is None:
00170             return []
00171         return a
    
def Bio.KDTree.KDTree.KDTree.search (   self,
  center,
  radius 
)
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

Definition at line 147 of file KDTree.py.

00147 
00148     def search(self, center, radius):
00149         """Search all points within radius of center.
00150 
00151         o center - one dimensional NumPy array. E.g. if the points have
00152         dimensionality D, the center array should be D dimensional. 
00153         o radius - float>0
00154         """
00155         if not self.built:
00156                 raise Exception("No point set specified")
00157         if center.shape!=(self.dim,):
00158                 raise Exception("Expected a %i-dimensional NumPy array" \
00159                                 % self.dim)
00160         self.kdt.search_center_radius(center, radius)

Here is the caller graph for this function:

def Bio.KDTree.KDTree.KDTree.set_coords (   self,
  coords 
)
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. 

Definition at line 131 of file KDTree.py.

00131 
00132     def set_coords(self, coords):
00133         """Add the coordinates of the points.
00134 
00135         o coords - two dimensional NumPy array. E.g. if the points
00136         have dimensionality D and there are N points, the coords 
00137         array should be NxD dimensional. 
00138         """
00139         if coords.min()<=-1e6 or coords.max()>=1e6:
00140                 raise Exception("Points should lie between -1e6 and 1e6")
00141         if len(coords.shape)!=2 or coords.shape[1]!=self.dim:
00142                 raise Exception("Expected a Nx%i NumPy array" % self.dim)
00143         self.kdt.set_data(coords)
00144         self.built=1


Member Data Documentation

Definition at line 127 of file KDTree.py.

Definition at line 125 of file KDTree.py.

Definition at line 126 of file KDTree.py.

Definition at line 198 of file KDTree.py.


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