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

[Rob Clewley]

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.

-Rob