On Sat, Sep 27, 2008 at 15:23, Anne Archibald <[EMAIL PROTECTED]> wrote: > 2008/9/27 Andrea Gavana <[EMAIL PROTECTED]>: > >> I was wondering if someone had any suggestions/references/snippets >> of code on how to find the minimum distance between 2 paths in 3D. >> Basically, for every path, I have I series of points (x, y, z) and I >> would like to know if there is a better way, other than comparing >> point by point the 2 paths, to find the minimum distance between them. > > If you treat the points as simply two clouds of points (that is, > ignore the fact that they represent points on paths), spatial data > structures can make this kind of question faster. For example a > kd-tree can be constructed in something like O(n log n) time, and you > can answer questions like "what is the closest point in this set to > (a,b,c)?" in something like O(log n) time. So you could do this by > putting one set of points in a kd-tree and just running queries > against each point in the other. There exist other spatial data > structures - octrees, voxel grids, bounding-volume hierarchies, other > binary space partitioning trees, as well as various more specialized > ones. As the number of dimensions becomes large they become > substantially more difficult to work with, and you do need to balance > construction time against lookup time, but they are definitely worth > thinking about in your problem. Sadly, no such data structure exists > in either numpy or scipy, though biopython apparently has an > implementation of kd-trees.
Sturla Molden has just contributed a pure Python+numpy implementation on the Scipy Cookbook. http://www.scipy.org/Cookbook/KDTree -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco _______________________________________________ Numpy-discussion mailing list [email protected] http://projects.scipy.org/mailman/listinfo/numpy-discussion
