**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"

task, which means minimizing a quadratic function subject to linear

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.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Distance between two line segments in 3D =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.