[SciPy-dev] [Numpy-discussion] Proposal: scipy.spatial

[Anne Archibald]

2008/10/6 Nathan Bell <wnbell at gmail.com>:

> IMO speed for the common query types is more important than support
> for sophisticated traversals.

There is now a compiled kd-tree implementation in scipy.spatial. It is
written in cython and based on the python implementation. It supports
only optionally-bounded, optionally-approximate, k-nearest neighbor
queries but runs without any per-point python code. It includes all
the algorithmic optimizations described by the ANN authors (sliding
midpoint subdivision, multiple-entry leaves, updating minimum-distance
calculation, priority search, and short-circuit distance
calculations). I think it's pretty good. The major feature it is
missing, from what people have asked for, is an all-neighbors query.

It's more or less impossible to traverse these trees from within
python. I am considering a tree-walking API to make it easy to write
algorithms that work on kd-trees efficiently, but it may make more
sense to just let people use the python implementation for this.

Anne