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

[Andrea Gavana]

Hi Rob & All,

On Sat, Sep 27, 2008 at 4:05 PM, Rob Clewley wrote:
> Hi Andrea,
>
>>    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.
>
> In 2D there would be a few tricks you could use, but in higher
> dimensions anything smart that you could attempt might cost you more
> computation time than just comparing the points (unless N is huge). At
> least make sure to put the "looping" over points into a vectorized
> form to avoid python for loops. e.g. two curves given by 3xN arrays c
> and d:
>
> from numpy import concatenate, argmin
> from numpy.linalg import norm
>
> distvec = concatenate([c[:,i]-d.T for i in range(N)])   # all N**2
> distance vectors
> ns = [norm(a) for a in distvec]   # all N**2 norms of the distance vectors
> cix, dix = divmod(argmin(ns), N)   # find the index of the minimum
> norm from [0 .. N**2] and decode which point this corresponds to
>
> The minimum is between the points c[:,cix] and d[:,dix]. A numpy wonk
> might be able to squeeze a bit more optimization out of this, but I
> think this code works OK.
>
> Unfortunately, unless you know more mathematical properties of your
> curves in advance (info about their maximum curvature, for instance)
> you'll end up needing to check every pair of points. If N is really
> big, like over 10**4 maybe, it might be worth trying to break the
> curves up into pieces contained in bounding boxes which you can
> eliminate from a full search if they don't intersect.

Thank you very much for your kind suggestions and the code snippet. I
think it will do just fine, as my well trajectories may have from 20
to 500 points maximum. I'll try it tomorrow at work and see how it
goes.

Thank you again.

Andrea.

"Imagination Is The Only Weapon In The War Against Reality."
http://xoomer.alice.it/infinity77/