biopython

v1.71.0

biopython v1.71.0 Bio.KDTree.KDTree.KDTree

KD tree implementation in 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.

Link to this section Summary

Functions

__init__()

Initialize KDTree class

all_get_indices()

Return All Fixed Neighbor Search results

all_get_radii()

Return All Fixed Neighbor Search results

all_search()

All fixed neighbor search

get_indices()

Return the list of indices

get_radii()

Return radii

search()

Search all points within radius of center

set_coords()

Add the coordinates of the points

Link to this section Functions

Link to this function __init__()

Initialize KDTree class.

Link to this function all_get_indices()

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.

Link to this function all_get_radii()

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

Link to this function all_search()

All fixed neighbor search.

Search all point pairs that are within radius.

Arguments:

  • radius: float (>0)
Link to this function get_indices()

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.

Link to this function get_radii()

Return radii.

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

Link to this function search()

Search all points within radius of center.

Arguments:

  • center: one dimensional NumPy array. E.g. if the points have dimensionality D, the center array should be D dimensional.
  • radius: float>0
Link to this function set_coords()

Add the coordinates of the points.

Arguments:

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