• Choose a category
• All
• Classic-Fiction

By Root 1593 0

rectangle that surrounds the segment and has sides that are parallel to the x-axis and y-axis. For a line segment with endpoints p 1 = (x 1, y 1) and p 2 = (x 2, y 2), the bounding box is the rectangle with lower left point (min(x 1, x 2), min(y 1, y 2)) and upper right point (max(x 1, x 2), max(y 1, y 2)) (see Figure 17.2). The bounding boxes of two line segments intersect if all of the following tests are true:

Figure 17.2. Testing whether line segments intersect using the quick rejection test (step 1) and straddle test (step 2)

If the bounding boxes of the line segments intersect, we proceed with the straddle test. To determine whether one segment with endpoints p 1 and p 2 straddles another with endpoints p 3 and p 4, we compare the orientation of p 3 relative to p 2 with that of p 4 relative to p 2 (see Figure 17.2). Each point's orientation conveys whether the point is clockwise or counterclockwise from p 2 with respect to p 1. To determine the orientation of p 3 relative to p 2 with respect to p 1, we look at the sign of:

z1 = ( x3 - x1 ) ( y2 - y1 ) - ( y3 - y1 ) ( x2 - x1 )

If z 1 is positive, p 3 is clockwise from p 2. If z 1 is negative, p 3 is counterclockwise from p 2. If it is 0, the points are on the same imaginary line extending from p 1. In this case, the points are said to be collinear . To determine the orientation of p 4 relative to p 2 with respect to p 1, we look at the sign of:

z2 = ( x4 - x1 ) ( y2 - y1 ) - ( y4 - y1 ) ( x2 - x1 )

If the signs of z 1 and z 2 are different, or if either is 0, the line segments straddle each other. Since if we perform this test, we have already shown that the bounding boxes intersect, the line segments intersect as well.

Figure 17.2 illustrates testing whether various pairs of line segments intersect using the quick rejection and straddle tests. The equations just given come from representing the line segments from p 1 to p 3, p 1 to p 2, and p 1 to p 4 as vectors U, V, and W (see the related topics at the end of the chapter) and using the signs of the z-components of the cross products U × V and W × V as gauges of orientation.

Interface for Testing Whether Line Segments Intersect

Name

lint

Synopsis

int lint(Point p1, Point p2, Point p3, Point p4);

Return Value

1 if the two line segments intersect, or otherwise.

Description

Tests whether two line segments intersect. Specify one line segment using its endpoints as p0 and p1. Specify the second line segment using its endpoints as p3 and p4. Each point is a structure of type Point. Although Point has three members for representing points in three dimensions, we can use it to represent points in two dimensions by setting z to 0. Since the lint operation works in two dimensions, it ignores the z-coordinate of each point.

Complexity

O (1)

Implementation and Analysis of Testing Whether Line Segments Intersect

To test whether two line segments intersect, we first must have a way to represent each segment. Let p1 and p2 define the endpoints of one of the segments and p3 and p4 define the endpoints of the other. Each endpoint is a Point structure. This structure consists of three members, x, y, and z, that are the coordinates of a point. Recall that we ignore all z-coordinates since lint works in two dimensions.

The lint operation (see Example 17.2) begins by performing the quick rejection test. This test uses two macros, MIN and MAX (see Example 17.1). These return the minimum and maximum of two values, respectively. The quick rejection test determines whether the bounding boxes of two line segments intersect. If this test succeeds, the algorithm continues with the straddle test; otherwise, it returns immediately that the line segments do not intersect. The straddle test determines the orientation of p3 relative to p2 and of p4 relative to p2 with respect to p1. If the orientations are different, or if either orientation is 0, the straddle test succeeds, and the algorithm returns that the line segments intersect; otherwise, the line segments do not intersect. The quick rejection and straddle