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

[Robert Kern]

On Sat, Sep 27, 2008 at 15:23, Anne Archibald <peridot.faceted at gmail.com> wrote:
> 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.

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