Algorithms in a Nutshell

(^278) | Chapter 9: Computational Geometry
member (e)
Determine whether the given element is a member of the queue. Note that
this operation is not strictly required of a generic priority queue type.
Only unique points appear in the event queue; that is, if the same event point is
inserted, its information is combined with the event point already in the queue.
Thus when the points from Figure 9-13 are initially inserted, the event queue
contains only eight event points.
LINESWEEPsweeps from top to bottom and updates the line state by adding and
deleting segments in their proper order. In Figure 9-13, the ordered line state
reflects the line segments that intersect the sweep line, from left to right after
processing the event point. To properly compute intersections, LINESWEEPmust
determine the segment in the state to the left of (or right of) a given segmentSi.
LINESWEEPuses an augmented balanced binary tree to process all of the
following operations in time O(logt), wheretis the number of elements in the
tree:
insert (s)
Insert the line segments into the tree.
delete (s)
Delete segments from the tree.
previous (s)
Return the segment immediately befores in the ordering (if one exists).
successor (s)
Return the segment immediately afters in the ordering (if one exists).
To properly maintain the ordering of segments, LINESWEEPswaps the order of
segments when a sweep detects an intersection between segmentsSiandSj; fortu-
nately, this too can be performed in O(logt) time simply by updating the sweep
line point and then deleting and reinserting the line segmentsSiandSj.In
Figure 9-13, for example, this swap occurs when the third intersection (6.66, 6.33)
is found.
The initialization phase of the algorithm constructs a priority queue from the 2*n
points (start and end) in the input set ofnlines. The event queue must additionally
be able to determine whether a new pointpalready exists within the queue; for this
reason, we cannot simply use a heap to store the event queue, as is commonly done
with priority queues. Since the queue is ordered, we must define an ordering of two-
dimensional points. Point p1p2.y; however, if p1.y=p2.y, then p1<p2 if
p1.x<p2.x. The size of the queue will never be larger than 2n+k, wherekis the
number of intersections andn is the number of input line segments.
All intersection points detected by LINESWEEPbelow the sweep line are added to
the event queue, where they will be processed to swap the order of intersecting
segments when the sweep line finally reaches the intersection point. Note that all
intersections between neighboring segments will be found below the sweep line,
and no intersection point will be missed.
As LINESWEEPprocesses each event point, line segments are added to the state
when an upper end point is visited, and removed when a lower end point isvisited.
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