Algorithms in a Nutshell

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

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 S_i and S_j to intersect, ...