Algorithms in a Nutshell

LineSweep | 277

Computational

Geometry

In Figure 9-14, when the event point representing the lower point*for segment S6

was inserted into the priority queue, LINESWEEPonly stored S6 as a lower

segment; once it is processed, it will additionally store S4 as an intersecting

segment. For a more complex example, when the event point representing the

intersection of segments S2 and S5 is inserted into the priority queue, it stores no

additional information. Once this event point is processed, it will store segments

S6, S2, and S5 as intersecting segments.

The computational engine behind LINESWEEPis contained within theLineState

class depicted in Figure 9-17.LineStatemaintains the current sweep point as it

sweeps from the top of the Cartesian plane downward. When the minimum entry

is extracted from theEventQueue, the providedpointSortercomparator properly

returns theEventPointobjects from top to bottom. The true work of LINESWEEP

occurs in thedetermineIntersectingmethod ofLineState: the intersections are

determined by iterating over those segments betweenleftandright. Full details on

these supporting classes are found in the code repository accompanying this book.

Consequences

LINESWEEPachieves O((n+k) logn) performance because it can reorder the active

line segments when the sweep point is advanced. If this step requires more than

O(logs) for its operations, wheresis the number of segments in the state, then the

entire performance of the overall algorithm will degenerate to O(n^2 ). For example,

if the line state were stored simply as a doubly linked list (a useful structure to

rapidly find predecessor and successor segments), the insert operation would

increase to require O(s) time to properly locate the segment in the list, and as the

setSof line segments increases, the performance degradation will soon become

noticeable.

Similarly, the event queue must support an efficient operation to determine

whether an event point is already present in the queue. Using a heap-based

priority queue implementation—as provided byjava.util.PriorityQueue, for

example—also forces the algorithm to degenerate to O(n^2 ). Beware of code imple-

mentations that claim to implement an O(nlogn) algorithm but instead produce

an O(n^2 ) implementation!

Analysis

LINESWEEPinserts the 2*nsegment end points into an event queue, a modified

priority queue that supports the following operations in time O(logq), whereqis

the number of elements in the queue:

min

Remove the minimum element from the queue.

insert (e)

Insert the element into its proper location within the ordered queue.

* Actually therightmostend point, since S6 is horizontal.

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