diva.sketch.features
Class ConvexHull

java.lang.Object
  extended by diva.sketch.features.ConvexHull

public class ConvexHull
extends Object

A ConvexHull object implements the Quickhull algorithm to find the planar convex hull of a set of points.

Given a set of points, a convex hull is the smallest convex region that contains all the points.

Version:
$Revision: 1.10 $
Author:
Heloise Hse (hwawen@eecs.berkeley.edu)

Constructor Summary
ConvexHull(double[] xvals, double[] yvals)
          Instantiate a ConvexHull object and call quickHull on the given set of points.
 
Method Summary
 double getArea()
          Return the area of the convex hull.
 double getPerimeter()
          Return the perimeter of this convex hull.
 Iterator points()
          Return an iterator over the points (Point2D) in the convex hull.
 void quickHull(double[] xpath, double[] ypath)
          Quickhull algorithm is similar to Quicksort algorithm.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ConvexHull

public ConvexHull(double[] xvals,
                  double[] yvals)
Instantiate a ConvexHull object and call quickHull on the given set of points.

Method Detail

getArea

public double getArea()
Return the area of the convex hull.


getPerimeter

public double getPerimeter()
Return the perimeter of this convex hull. Calculate the length of consecutive line segments including wrap around. ex. (p0,p1)(p1,p2)....(pLast-1, pLast)(pLast, p0)


points

public Iterator points()
Return an iterator over the points (Point2D) in the convex hull.


quickHull

public void quickHull(double[] xpath,
                      double[] ypath)
Quickhull algorithm is similar to Quicksort algorithm. It chooses a pivot, split the data based on the pivot, and recurse on each of the split sets.

In the algorithm, we first pick two points, the left most (min x) and the right most (max x). These two points (obviously lie on the hull) form a split line separating the region into two. Then we recursively split each region by finding the point that's the farthest from the split line.



Copyright © 2015 Central Laboratory of the Research Councils. All Rights Reserved.