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

[Anne Archibald]

2008/9/27 Andrea Gavana <andrea.gavana at gmail.com>:

>    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