# comp.graphics.algorithms

## Subject: Re: Distance between a Line Segment and a triangle in 3D

"Maik Wagner" wrote in message
news:e5f28e\$8ke\$1@anderson.hrz.tu-chemnitz.de...

> I need to calculate the distance between a line segment and a triangle.

My approach is to minimize the quadratic function
F(u,v,w) = |T(u,v) - L(w)|^2, where T(u,v) is a
point on the triangle and L(w) is a point on the
line segment. The triangle point is
T(u,v) = P0 + u*(P1 - P0) + v*(P2 - P0)
where P0, P1, and P2 are the triangle vertices and
where u >= 0, v >= 0, u+v <= 1. The line segment
point is
L(w) = Q0 + w*(Q1 - Q0)
where Q0 and Q1 are the line segment endpoints and
where 0 <= w <= 1.

The domain is a prism in (u,v,w) space. When the line
segment is not parallel to the triangle, the minimum
of F(u,v,w) occurs at
(1) an interior point of the prism, or
(2) an interior point of the face of the prism, or
(3) an interior point of an edge of the prism, or
(4) a vertex of the prism.
It is easy enough to associate the geometric configuration
for each of these cases.

If the line segment and triangle are parallel, F(u,v,w) has
a minimum value occurring on a line segment in the (u,v,w)
domain.

A source code implementation is at my website, select the
Source tab and then the Distance tab. Files are
Wm3DistSegment3Triangle3.* (although I actually use a
center-radius formulation for the line segment to help with
numerical robustness).

--
Dave Eberly
http://www.geometrictools.com