[Numpy-discussion] Minimum distance between 2 paths in 3D

[Nathan Bell]

On Sat, Sep 27, 2008 at 11:18 PM, Anne Archibald
<peridot.faceted at gmail.com> wrote:
>
> I think a kd-tree implementation would be a valuable addition to
> scipy, perhaps in a submodule scipy.spatial that might eventually
> contain other spatial data structures and algorithms. What do you
> think? Should we have one? Should it be based on Sturla Molden's code,
> if the license permits? I am willing to contribute one, if not.

+1

If you're implementing one, I would highly recommend the
"left-balanced" kd-tree.
http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/2535/pdf/imm2535.pdf

Here's one implementation (undetermined license):
http://www2.imm.dtu.dk/~jab/software.html#kdtrees

I have a C++ implementation based on the one above that does a few
more operations (like nearest-n neighbors) that you're welcome to use.
 The use of n_th() in the STL makes left-balancing fairly
straightforward.

FWIW I also have a pure python implementation here:
http://code.google.com/p/pydec/source/browse/trunk/pydec/math/kd_tree.py

-- 
Nathan Bell wnbell at gmail.com
http://graphics.cs.uiuc.edu/~wnbell/