Algorithm
Development Kit 1.0

algs.model.problems.convexhull
Class AklToussaint

java.lang.Object
  extended by algs.model.problems.convexhull.AklToussaint

public class AklToussaint
extends java.lang.Object

Heuristic that offers noticeable speed-up when when applied to Convex Hull problems. Questions that may not have an impact but are worth asking: What if LEFT/BOTTOM are same point and TOP/RIGHT are same point? What if LEFT/BOTTOM/TOP/RIGHT are all same point?

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

Method Summary
static IPoint[] reduce(IPoint[] points)
          Remove points that are within the quadrilateral formed by the extreme points at (x,y) axes.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

reduce

public static IPoint[] reduce(IPoint[] points)
Remove points that are within the quadrilateral formed by the extreme points at (x,y) axes.

These points clearly cannot be on the convex hull. The array returned contains those points that are outside the quadrilateral.

Parameters:
points - initial convex hull set.

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.