One way to determine whether two line segments intersect is first to determine the intersection point p_i = (x_i , y _i ) of the two lines on which each segment lies, then determine whether p_i is on both segments. If p_i is on both segments, the line segments intersect. We start with the point-intercept representations of the two lines on which the segments lie, which are:

The following formulas are used to compute p_i = (x_i , y _i ). Notice that one special case we must avoid when computing x_i is two lines with slopes that are equal. In this case, the denominator in the expression for x_i becomes 0. This occurs when two lines are parallel, in which case the segments will not intersect unless they lie on top of one another to some extent.

Once we’ve computed p_i , we perform the following tests to determine whether the point is actually on both line segments. In these tests, p ₁ = (x ₁, y ₁) and p ₂ = (x ₂, y ₂) are the endpoints of one line segment, and p ₃ = (x ₃, y ₃) and p ₄ = (x ₄, y ₄ ) are the endpoints of the other. If each of the tests is true, the line segments intersect.

This approach is common for determining whether line segments intersect. However, because the division required while calculating x_i is prone to round-off error and precision problems, in computing we take a different approach.

In computing, to determine whether two lines intersect, a two-step process is used: first, we perform a quick rejection test. If this test succeeds, we then perform a straddle test. Two line segments intersect only when the quick rejection test and straddle test both succeed.

We begin the quick rejection test by constructing a bounding box around each line segment. The bounding box of a line segment is the smallest 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 ₁ = (x ₁, y ₁) and p ₂ = (x ₂, y ₂), the bounding box is the rectangle with lower left point (min(x ₁, x ₂), min(y ₁, y ₂)) and upper right point (max(x ₁, x ₂), max(y ₁, y ₂)) (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 ₁ and p ₂ straddles another with endpoints p ₃ and p ₄, we compare the orientation of p ₃ relative to p ₂ with that of p ₄ relative to p ₂ (see Figure 17.2). Each point’s orientation conveys whether the point is clockwise or counterclockwise from p ₂ with respect to p ₁. To determine the orientation of p ₃ relative to p ₂ with respect to p ₁, we look at the sign of:

z₁ = ( x₃ - x₁ ) ( y₂ - y₁ ) - ( y₃ - y₁ ) ( x₂ - x₁ )

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

z₂ = ( x₄ - x₁ ) ( y₂ - y₁ ) - ( y₄ - y₁ ) ( x₂ - x₁ )

If the signs of z ₁ and z ₂ 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 ₁ to p ₃, p ₁ to p ₂, and p ₁ to p ₄ 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.