Algorithms in a Nutshell

LineSweep | 269

Computational

Geometry

The innovation of LINESWEEPis recognizing that line segments can be ordered

from left to right at a specificycoordinate.*Line segment intersections can then

occur only between neighboring segments in the state of the sweep line. Specifi-

cally, for two line segmentsSiandSjto intersect, there must be some time during

the line sweep when they are neighbors. Indeed, LINESWEEPcan efficiently locate

intersections because it maintains this line state efficiently.

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

* Horizontal segments are addressed by considering the left end point to be “higher” than the right

end point.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use