One fundamental problem in computational geometry is
determining whether two *line segments* intersect.
Line segments are lines that have a beginning and an end. The points
that define either end are a line segment's
*endpoints* . To determine whether two line segments intersect, we
first need to understand a little about lines and line segments in
general.

One representation of a line is
*point-intercept form* , or *y* = *mx* +
*b*, where *m* is the line's
slope and *b* is where the line crosses the
*y*-axis. Using this, for any value of
*x*, we can compute a corresponding value for
*y* (see Figure
17.1a). For a line segment with endpoints
*p* _{1} =
(*x* _{1},
*y* _{1}) and
*p* _{2} =
(*x* _{2},
*y* _{2}), the slope
*m* and *y*-intercept
*b * are calculated by applying the following
formulas:

Using *m* and *b*, the
line segment is represented as a line in point-intercept form with
endpoints *p* _{1} and
*p* _{2} understood (see Figure 17.1b).

Figure 17.1. (a) A line and (b) a line segment with endpoints
p_{1} and p_{2}

One way to determine whether two line segments
intersect is first to determine the intersection point
*p _{i} * =
(

Start Free Trial

No credit card required