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

Anne Archibald peridot.faceted@gmail....
Sat Sep 27 22:18:46 CDT 2008


2008/9/27 Robert Kern <robert.kern@gmail.com>:
> On Sat, Sep 27, 2008 at 15:23, Anne Archibald <peridot.faceted@gmail.com> wrote:
>> 2008/9/27 Andrea Gavana <andrea.gavana@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.
>
> Sturla Molden has just contributed a pure Python+numpy implementation
> on the Scipy Cookbook.
>
>  http://www.scipy.org/Cookbook/KDTree

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.

Anne


More information about the Numpy-discussion mailing list