# comp.graphics.algorithms

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

Dave Eberly wrote:

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

Thanks for this detailed and useful answer.

I just had a quick look at your implementation, and it looks like you're
doing it nearly as i was up to. (Hard to say if these are good or bad
news :))

But i think the order you're doing it will be more effective, as there
are only 3 calculations of the distance line-segment instead of 3 times
segment-segment like i would've done it.

seems it wasn't close enough :)

Maik