(^262) | Chapter 9: Computational Geometry
Input/Output
Input
A set of two-dimensional pointsP in a plane.
Output
An ordered list L containing thehvertices of the convex hull ofPin clockwise
order. The convex hull is a polygon defined by the points L 0 ,L 1 ,...,Lh–1, whereh
is the number of points in L. Note that the polygon is formed from thehline
segments <L 0 , L 1 >, <L 1 , L 2 >, ..., < Lh–1, L 0 >.
Assumptions
To avoid trivial solutions, we assume |P|≥3. No two points are “too close” to each
other (as determined by the implementation). If two points are too close to each
other and one of those points is on the convex hull, CONVEXHULLSCANmight
incorrectly select an invalid convex hull point (or discard a valid convex hull
point); however, the difference would be negligible.
Context
The Akl-Toussaint heuristic (1978) can noticeably improve performance of the
overall algorithm by discarding all points that exist within the extreme quadrilat-
eral (the minimum and maximum points along bothxandyaxes) computed from
the initial setP. Figure 9-10 shows the extreme quadrilateral for the sample points
from Figure 9-4, and the discarded points are shown in gray; none of these points
can belong to the convex hull.
To determine whether a pointpis within the extreme quadrilateral, imagine a line
segmentsfrompto an extreme point at (p.x,–∞), and count the number of times
thatsintersects the four line segments of the quadrilateral;*if the count is 1, then
pis inside and can be eliminated. This computation requires a fixed number of
steps, so it is O(1), which means applying the Akl-Toussaint heuristic to all points
is O(n). For large random samples, this heuristic can remove nearly half of the
Figure 9-9. Computing the determinant of an array of three points to decide right turn
- The implementation handles special cases, such as when line segmentsexactly intersects one of
the end points of the extreme quadrilateral.
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