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

Module KDTree

source code

KD tree data structure for searching N-dimensional vectors.

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. See "Computational Geometry:
Algorithms and Applications" (Mark de Berg, Marc van Kreveld, Mark Overmars,
Otfried Schwarzkopf). Author: Thomas Hamelryck.

Classes [hide private]
  KDTree
KD tree implementation (C++, SWIG python wrapper)
Functions [hide private]
 
_dist(p, q) source code
 
_neighbor_test(nr_points, dim, bucket_size, radius)
Test all fixed radius neighbor search.
source code
 
_test(nr_points, dim, bucket_size, radius)
Test neighbor search.
source code
Function Details [hide private]

_neighbor_test(nr_points, dim, bucket_size, radius)

source code 
Test all fixed radius neighbor search.

Test all fixed radius neighbor search using the
KD tree C module.

o nr_points - number of points used in test
o dim - dimension of coords
o bucket_size - nr of points per tree node
o radius - radius of search (typically 0.05 or so)

_test(nr_points, dim, bucket_size, radius)

source code 
Test neighbor search.

Test neighbor search using the KD tree C module.

o nr_points - number of points used in test
o dim - dimension of coords
o bucket_size - nr of points per tree node
o radius - radius of search (typically 0.05 or so)