# comp.graphics.algorithms

## Subject: Re: Distance between two line segments in 3D

On 19 May 2006 08:37:04 -0700, Cleverbum@hotmail.com wrote:
>How to find the distance between two line segments in 3D
>
>Define the distance between two segments in 3D as the minimum
>Euclidean distance between a point on one and a point on the other.
>Let S1 = (a,b) and S2 = (c,d) be two such segments, and let L1 and L2
>be the (infinite) lines containing S1 and S2. Here a = (ax,ay,az)
>and similarly for the other endpoints. Then the distance between
>S1 and S2 is the minimum of
>
> the distance between a and c
> the distance between a and d
> the distance between b and c
> the distance between b and d
>
> the distance between a and L1
> the distance between b and L1
> the distance between c and L2
> the distance between d and L2
>
> the distance between L1 and L2

What's embarrassing is that this is from an old version of the FAQ! In
the current FAQ there is no entry for this, which I suppose is an
improvement over misinformation.

The archives contain this more helpful response from Oct 31 2002:
----
>Lumelsky's paper from 1985 is the classical reference, using
>elementary linear algebra to solve the problem. Dave Eberly presents
>a slightly more involved vector calculus solution in his 3DGED book.
>Dan Sunday gives a somewhat simplified version of Dave's vector
>calculus approach here:
>
>http://www.geometryalgorithms.com/Archive/algorithm_0106/algorithm_01...
>
>There's code too in Sunday's article, but beware, last time I checked
>it, it didn't properly handle degenerate configurations and could get
>a division-by-zero error.
>
>Christer Ericson
>Sony Computer Entertainment, Santa Monica
----

Presumably the intended "classic reference" is this:

Vladimir J. Lumelsky. On fast computation of distance between line
segments. Information Processing Letters, 21:55--61, 1985.

Lumelsky appears to be affiliated with NASA's GSFC these days.

Technically, the problem can be described as a "quadratic programming"
constraints (here, simple bounds). The general rule is that either the
bounds matter, so a minimum is forced at a boundary, or else they do
not, so a minimum is free within the bounded region. This does bear a
vague resemblance to the mess you quote, but leads to different (and
correct!) algorithms.

Others have noted that an algorithm may be mathematically correct but
not numerically robust. Additionally, many applications of distance
computations are really trying to make decisions, and we can often use
pre-screening tests like comparing bounding boxes to quickly decide if
we need to look more closely. The segment-distance computation may not
be expensive enough to benefit from pre-screening; only experiments
can say if this is true in specific applications.

View All Messages in comp.graphics.algorithms

path:
Distance between two line segments in 3D =>

Replies: