Mastering Algorithms with C

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 tests are performed using the methods described earlier.

The runtime complexity of lint is O (1) because all of the steps in testing whether two line segments intersect run in a constant amount of time.

Example 17.2. Implementation ...