On Sat, Sep 27, 2008 at 11:18 PM, Anne Archibald <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED] http://graphics.cs.uiuc.edu/~wnbell/ _______________________________________________ Numpy-discussion mailing list [email protected] http://projects.scipy.org/mailman/listinfo/numpy-discussion
