Algorithms in a Nutshell

(^272) | Chapter 9: Computational Geometry
Input/Output
Input
A set ofn line segmentsS in the Cartesian plane.
Output
The full set ofkpoints representing the intersections (if any exist) between these
line segments and, for each of thesekpoints,pi, the actual line segments fromS
that intersect atpi.
Assumptions
There can be no duplicate segments inS. No two line segments inSare collinear
(that is, overlap each other and have the same slope). The algorithm supports
both horizontal and vertical line segments by carefully performing computations
and ordering segments appropriately. No line segment should be a single point (i.e.,
a line segment whose start and end point are the same).
Context
When the expected number of intersections is much smaller than the number of
line segments, this algorithm will handily outperform a brute-force approach.
When there are a significant number of intersections, the bookkeeping of the algo-
rithm may outweigh the benefits.
Forces
A sweep-based approach is useful when you can (a) efficiently construct the line
state, and (b) manage the event queue that defines when the sweep line is inter-
preted. There are numerous special cases to consider within the LINESWEEP
implementation, and the resulting code is much more complex than the brute
force approach, whose worst-case performance is O(n^2 ). You would only choose
this algorithm for the expected performance savings.
LINESWEEPproduces partial results intermittently until the entire input set has
been processed and all output results are produced. In the example here, the line
state is a balanced binary tree of line segments, which is possible because we can
impose an ordering on the segments at the sweep line point. The event queue can
also simply be a balanced binary tree of event points, sorted lexicographically.
To simplify the coding of the algorithm, the binary tree used to store the line state
is an augmented balanced binary tree in which only the leaf nodes contain real
information. Interior nodes store min and max information about the leftmost
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