Algorithm
Development Kit 1.0

algs.model.problems.convexhull.bucket
Class BucketAndrew

java.lang.Object
  extended by algs.model.problems.convexhull.bucket.BucketAndrew
All Implemented Interfaces:
IConvexHull

public class BucketAndrew
extends java.lang.Object
implements IConvexHull

Computes Convex Hull following Andrew's Algorithm. This algorithm is described in the text. We use BucketSort to sort the points.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
BucketAndrew()
           
 
Method Summary
 IPoint[] compute(IPoint[] points)
          Return the computed convex hull for the input set of IPoint objects.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BucketAndrew

public BucketAndrew()
Method Detail

compute

public IPoint[] compute(IPoint[] points)
Description copied from interface: IConvexHull
Return the computed convex hull for the input set of IPoint objects.

Points must have at least three points to do anything meaningful. If it does not, then the sorted array is returned as the "hull".

Some implementations may be able to work if duplicate points are found, but the set should contain distinct IPoint objects.

Specified by:
compute in interface IConvexHull
Parameters:
points - an array of (n ≥ 3) two dimensional points.

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.