Graphics Reference
In-Depth Information
D
D
D
B
B
B
P
A
C
P
C
A
A
C
(a)
(b)
(c)
Figure 5.10
(a) Segments
AB
and
CD
do not intersect because the intersection point
P
of
their extended lines lies outside the bounding box of
CD
. (b) Segments
AB
and
CD
intersect
because
P
lies inside the bounding boxes of both
AB
and
CD
. (c) Segment
CD
intersects the
line through
AB
because the triangles
ABD
and
ABC
have opposite winding.
of the extended line through the other segment. That is, for
AB
and
CD
to overlap,
A
and
B
must be on different sides of
CD
and
C
and
D
must be on different sides of
AB
.
Testing whether the endpoints
C
and
D
are on different sides of
AB
can be done by
verifying that the triangles
ABD
and
ABC
wind in different directions (illustrated in
Figure 5.10c). To determine the winding, the signed triangle area can be computed.
Recall that the signed area is positive if the triangle winds counterclockwise, negative
if it winds clockwise, and zero if the triangle is degenerate (collinear or coincident
points).
// Returns 2 times the signed triangle area. The result is positive if
// abc is ccw, negative if abc is cw, zero if abc is degenerate.
float Signed2DTriArea(Point a, Point b, Point c)
{
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
}
In the case in which the segments are intersecting, it turns out that the signed
areas computed to detect this can also be used to compute the intersection point. The
computation and its derivation are given in the following implementation.
// Test if segments ab and cd overlap. If they do, compute and return
// intersection t value along ab and intersection position p
int Test2DSegmentSegment(Point a, Point b, Point c, Point d, float &t, Point &p)
{
// Sign of areas correspond to which side of ab points c and d are
float a1 = Signed2DTriArea(a, b, d);
// Compute winding of abd (+ or -)
float a2 = Signed2DTriArea(a, b, c);
// To intersect, must have sign opposite of a1
