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
Variables [hide private]
  __package__ = 'Bio.KDTree'
  sqrt = <ufunc 'sqrt'>
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.

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

Returns true if the test passes.

_test(nr_points, dim, bucket_size, radius)

source code 

Test neighbor search.

Test neighbor search using the KD tree C module.

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

Returns true if the test passes.