|
Algorithm Development Kit 1.0 |
||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||
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. |
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 | ||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||