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

Rob Clewley rob.clewley@gmail....
Sat Sep 27 10:05:07 CDT 2008

```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