Algorithms in a Nutshell

(^264) | Chapter 9: Computational Geometry
Figure 9-11. PartialHull supporting class
Example 9-2. Convex Hull Scan solution to convex hull
public class ConvexHullScan implements IConvexHull {
public IPoint [] compute (IPoint[] points) {
// sort by x-coordinate (and if ==, by y-coordinate).
int n = points.length;
new HeapSort().sort(points, 0, n-1, IPoint.xy_sorter);
if (n < 3) { return points; }
// Compute upper hull by starting with leftmost two points
PartialHull upper = new PartialHull(points[0], points[1]);
for (int i = 2; i < n; i++) {
upper.add(points[i]);
while (upper.hasThree( ) && upper.areLastThreeNonRight( )) {
upper.removeMiddleOfLastThree( );
}
}
// Compute lower hull by starting with rightmost two points
PartialHull lower = new PartialHull(points[n-1], points[n-2]);
for (int i = n-3; i >= 0; i--) {
lower.add(points[i]);
while (lower.hasThree( ) && lower.areLastThreeNonRight( )) {
lower.removeMiddleOfLastThree( );
}
}
// remove duplicate end points when combining.
IPoint[] hull = new IPoint[upper.size( )+lower.size( )-2];
System.arraycopy(upper.getPoints( ), 0, hull, 0, upper.size( ));
System.arraycopy(lower.getPoints( ), 1, hull,
upper.size( ), lower.size( )-2);
return hull;
}
}
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
Licensed by
Ming Yi