Cover by Gary Pollice, Stanley Selkow, George T. Heineman

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

O'Reilly logo

LineSweep

There are numerous situations where one must detect intersections between geometric shapes. In VLSI chip design, precise circuits are laid out on a circuit board, and there must be no unplanned intersections. For travel planning, a set of roads could be stored in a database as line segments whose street intersections are determined by line segment intersections.

Figure 9-13 shows an example with seven intersections found between six line segments. Perhaps we don't have to compare all possible C(n,2) or n*(n−1)/2 line segments. After all, line segments that are clearly apart from one another (in this example, S1 and S4) cannot intersect. LineSweep is a proven approach that improves efficiency by focusing on a subset of the input elements as it progresses. Imagine sweeping a horizontal line L across the input set of line segments from the top to the bottom and reporting the intersections when they are found by L. Figure 9-13 shows the state of line L as the sweep occurs from top to bottom (at nine distinct and specific locations).

Detecting seven intersections for six line segments

Figure 9-13. Detecting seven intersections for six line segments

The innovation of LineSweep is recognizing that line segments can be ordered from left to right at a specific y coordinate.[33] Line segment intersections can then occur only between neighboring segments in the state of the sweep line. Specifically, for two line segments Si and Sj to intersect, ...

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