[Numpy-discussion] Minimum distance between 2 paths in 3D
Nathan Bell
wnbell at gmail.com
Sat Sep 27 23:58:32 EDT 2008
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/
More information about the NumPy-Discussion
mailing list