**comp.graphics.algorithms**

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

news:1148053024.812334.200840@38g2000cwa.googlegroups.com...

> 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

function,

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.

OR

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.

OR

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

http://www.geometrictools.com

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Distance between two line segments in 3D =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.