You are previewing Algorithms in a Nutshell.

Algorithms in a Nutshell

Cover of Algorithms in a Nutshell by George T. Heineman... Published by O'Reilly Media, Inc.


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

The best content for your career. Discover unlimited learning on demand for around $1/day.