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

Start Free Trial

No credit card required