Algorithm
Development Kit 1.0

Package algs.model.problems.convexhull

Defines core classes for the Convex Hull problem.

See:
          Description

Interface Summary
IConvexHull Defined interface for algorithms that compute the convex hull for a set of IPoint objects.
 

Class Summary
AklToussaint Heuristic that offers noticeable speed-up when when applied to Convex Hull problems.
PartialHull Represents either the top or the bottom of a Convex Hull.
 

Package algs.model.problems.convexhull Description

Defines core classes for the Convex Hull problem. Given a set of points P in a two-dimensional plane, the convex hull is the smallest convex shape that fully encloses all points in P. The hull is convex because a line between any 2 points within it lies totally within the hull. The convex hull computation is specified by the following API description:

public 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. * * @param points a set of (n ≥ 3) two dimensional points. */ public IPoint[] compute (IPoint[] points); }

The hull is formed by a clockwise ordering of h points L0 … Lh–1. The first point L0 is typically the leftmost point in the set P (although any point can be the start). Each sequence of three hull points Li, Li+1, Li+2 creates a right turn; note that this property holds for Lh–2, Lh–1, L0 as well.


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.