Graphics Reference
In-Depth Information
C
C
C
A
B
A
B
A
B
(a)
(b)
(c)
Figure 5.2
The three cases of
C
projecting onto
AB
: (a) outside
AB
on side of
A
, (b) inside
AB
, and (c) outside
AB
on side of
B
.
outside the segment, it is instead the segment endpoint closest to
C
that is the closest
point.
Any point on the line through
AB
can be expressed parametrically as
P
(
t
)
=
A
+
t
(
B
A
). Using the projective properties of the dot product, the
t
corresponding
to the projection of
C
onto the line is given by
t
−
=
(
C
−
A
)
·
n
/
B
−
A
, where
n
is a unit vector in the direction of
AB
.
Because the closest point on the line segment is required,
t
must be clamped to the
interval 0
=
(
B
−
A
)/
B
−
A
≤
≤
1, after which
D
can be obtained by substituting
t
into the parametric
equation. Implemented, this becomes:
t
// Given segment ab and point c, computes closest point d on ab.
// Also returns t for the position of d, d(t)=a+t*(b - a)
void ClosestPtPointSegment(Point c, Point a, Point b, float &t, Point &d)
{
Vector ab=b-a;
// Project c onto ab, computing parameterized position d(t)=a+t*(b - a)
t = Dot(c - a, ab) / Dot(ab, ab);
// If outside segment, clamp t (and therefore d) to the closest endpoint
if (t < 0.0f) t = 0.0f;
if (t > 1.0f) t = 1.0f;
// Compute projected position from the clamped t
d=a+t*ab;
}
If divisions are expensive, the division operation can be postponed by multiply-
ing both sides of the comparisons by the denominator, which as a square term is
guaranteed to be nonnegative. Optimized in this fashion, the code becomes:
// Given segment ab and point c, computes closest point d on ab.
// Also returns t for the parametric position of d, d(t)=a+t*(b - a)
