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

built | |

dim | |

kdt |

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

- biopython-1.30/Bio/KDTree/KDTree.py

Generated by Doxygen 1.6.0 Back to index