Algorithm
Development Kit 1.0

algs.model.problems.convexhull.balanced
Class BalancedTreeAndrew

java.lang.Object
  extended by algs.model.problems.convexhull.balanced.BalancedTreeAndrew
All Implemented Interfaces:
IConvexHull

public class BalancedTreeAndrew
extends java.lang.Object
implements IConvexHull

Computes Convex Hull following Andrew's Algorithm. This algorithm is described in the text.

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

Constructor Summary
BalancedTreeAndrew()
           
 
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

BalancedTreeAndrew

public BalancedTreeAndrew()
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.