O'Reilly logo

Mastering Algorithms with C by Kyle Loudon

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Description of Testing Whether Line Segments Intersect

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:

image with no caption

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).

(a) A line and (b) a line segment with endpoints p1 and p2

Figure 17.1. (a) A line and (b) a line segment with endpoints p1 and p2

Standard Test for Intersecting Line Segments

One way to determine whether two line segments intersect is first to determine the intersection point pi = (xi , y i ) of the two lines on which each segment lies, then determine whether pi is on both segments. If pi is on both segments, the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required