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

Nathan Bell wnbell@gmail....
Sat Sep 27 22:58:32 CDT 2008

On Sat, Sep 27, 2008 at 11:18 PM, Anne Archibald
<peridot.faceted@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.


If you're implementing one, I would highly recommend the
"left-balanced" kd-tree.

Here's one implementation (undetermined license):

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

FWIW I also have a pure python implementation here:

Nathan Bell wnbell@gmail.com

More information about the Numpy-discussion mailing list