Home Products Download Order Contacts


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

wrote in message

> is this true? I don't see the logic, surely if L1 and L2 intersect
> while the segments do not this will produce a totally false result!
> Does anyone have a simple methodology for this, as a lot of the info I
> can find online starts at too high a level for me to fully understand
> it.

Your counterexample is a good one. A correct algorithm is
the following. The first segment has parameterization
X(s) = a + s*(b-a) for 0 <= s <= 1. The second segment
has parameterization Y(t) = c + t*(d-c) for 0 <= t <= 1.
The squared distance between two points is a quadratic
Q(s,t) = |X(s) - Y(t)|^2
and is defined on the square (s,t) in [0,1]x[0,1]. The
minimum of this function occurs
1. At (s,t) in the interior of the square, in which case
the distance between the line segments is equal to
the distance between the lines.
2. At (s,t) on an edge of the square, but not at a
corner of the square. For example, suppose s = 1
and 0 < t < 1. The point 'b' is closest to an interior
point of the other segment.
3. At (s,t) which is a corner of the square. For example,
if (s,t) = (0,1), then 'a' and 'd' are the closest points
on the line segment.

Dave Eberly


View All Messages in comp.graphics.algorithms

Distance between two line segments in 3D =>


Copyright 2006 WatermarkFactory.com. All Rights Reserved.