diva.sketch.features

Class ConvexHull

java.lang.Object

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

Constructors

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

Method Summary

Modifier and Type	Method and Description
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.