Graphics Reference
In-Depth Information
5.1.9
Closest Points of Two Line Segments
The problem of determining the closest points of two line segments
S
1
and
S
2
,
S
1
(
s
)
=
P
1
+
s
d
1
,
d
1
=
Q
1
−
P
1
,0
≤
s
≤
1
S
2
(
t
)
=
P
2
+
t
d
2
,
d
2
=
Q
2
−
P
2
,0
≤
t
≤
1,
is more complicated than computing the closest points of the lines
L
1
and
L
2
of
which the segments are a part. Only when the closest points of
L
1
and
L
2
happen to
lie on the segments does the method for closest points between lines apply. For the
case in which the closest points between
L
1
and
L
2
lie outside one or both segments,
a common misconception is that it is sufficient to clamp the outside points to the
nearest segment endpoint. However, as cases (b) and (c) of Figure 5.9 illustrate, this
is not a valid assumption.
It can be shown that if just one of the closest points between the lines is outside
its corresponding segment that point can be clamped to the appropriate endpoint of
the segment and the point on the other segment closest to the endpoint is computed
[Lumelsky85]. This corresponds to case (b) in Figure 5.9, in which the closest point on
L
1
is clamped to endpoint
Q
1
on segment
S
1
. The closest point
R
on
L
2
to
Q
1
is then
computed and found to be on segment
S
2
, leaving the closest points as
Q
1
and
R
.
If both points are outside their respective segments, the same clamping procedure
must be repeated twice, as illustrated by case (c) in Figure 5.9. Again the closest point
on
L
1
gets clamped to endpoint
Q
1
on
S
1
. The closest point
R
on
L
2
to
Q
1
is computed.
Because
R
is found to be outside segment
S
2
, it is clamped to the nearest segment
endpoint,
Q
2
. The closest point
S
on
L
1
to
Q
2
is then computed and now found to be
on segment
S
1
, leaving the closest points as
Q
2
and
S
.
Given a point
S
2
(
t
)
=
P
2
+
t
d
2
on the second segment, the closest point
L
1
(
s
)on
L
1
is given by
=
−
·
·
=
+
−
·
·
s
(
S
2
(
t
)
P
1
)
d
1
/
d
1
d
1
(
P
2
t
d
2
P
1
)
d
1
/
d
1
d
1
.
Q
2
P
1
P
1
P
1
P
1
Q
2
Q
1
S
Q
1
Q
1
P
2
P
2
Q
1
P
2
Q
2
P
2
R
Q
2
R
(a)
(b)
(c)
(d)
Figure 5.9
Closest points (a) inside both segments, (b) and (c) inside one segment endpoint
of other, (d) endpoints of both segments (after [Lumelsky85]).
