Algorithm
Development Kit 1.0

algs.model.problems.convexhull.andrew
Class ConvexHullScanLinkedList

java.lang.Object
  extended by algs.model.problems.convexhull.andrew.ConvexHullScanLinkedList

public class ConvexHullScanLinkedList
extends java.lang.Object

Computes Convex Hull following Andrew's Algorithm with linked lists. This is described in the text. This implementation of ConvexHull does not implement IConvexHull because the resulting double linked list computation would have to be converted to an array simply to be returned. In doing so, the performance costs would be higher than they should be.

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

Constructor Summary
ConvexHullScanLinkedList()
           
 
Method Summary
 DoubleLinkedList<IPoint> compute(IPoint[] points)
          Use Andrew's algorithm to return the computed convex hull for the input set of points.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ConvexHullScanLinkedList

public ConvexHullScanLinkedList()
Method Detail

compute

public DoubleLinkedList<IPoint> compute(IPoint[] points)
Use Andrew's algorithm to return the computed convex hull for the input set of points. Uses linked lists to store information.

Parameters:
points - a set 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.