Algorithms in a Nutshell

(^270) | Chapter 9: Computational Geometry
Looking closer at the nine selected locations of the horizontal sweep line in
Figure 9-13, you will see that each occurs at (i) the start or end of a line segment,
or (ii) an intersection. LINESWEEPdoesn’t actually “sweep” a line across the
Cartesian plane; rather, it inserts the 2*nsegment end points into an event queue,
which is a modified priority queue, as shown in Figure 9-14. All intersections
involving start and end points of existing line segments can be detected when
processing these points. LINESWEEPprocesses the queue to build up the state of
the sweep line L to determine when neighboring line segments intersect; the logic
is shown in Figure 9-15.
Figure 9-14. LineSweep fact sheet (part I)
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