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. Good luck, Anne _______________________________________________ Numpy-discussion mailing list [email protected] http://projects.scipy.org/mailman/listinfo/numpy-discussion
