math.geom2d.polygon.convhull
Class JarvisMarch2D

java.lang.Object
  math.geom2d.polygon.convhull.JarvisMarch2D

All Implemented Interfaces:

ConvexHull2D

public class JarvisMarch2D
extends java.lang.Object
implements ConvexHull2D

Computes the convex hull of a set of points as a single Polygon2D by gift wrapping algorithm, also know as Jarvis March.

The complexity of the algorithm is of O(n * h), where n is the number of input points and h the number of vertices of the convex hull. This low complexity makes it the best choice algorithm for computing convex hull.

Author:

dlegland

Constructor Summary

JarvisMarch2D()
Creates a new Convex hull calculator.

Method Summary

Polygon2D

convexHull(java.util.Collection<? extends Point2D> points) Computes the convex hull of a set of points as a single Polygon2D.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

JarvisMarch2D

public JarvisMarch2D()

Creates a new Convex hull calculator.

Method Detail

convexHull

public Polygon2D convexHull(java.util.Collection<? extends Point2D> points)

Computes the convex hull of a set of points as a single Polygon2D. Current implementation start at the point with lowest y-coord. The points are considered in counter-clockwise order. Result is an instance of SimplePolygon2D. Complexity is O(n*h), with n number of points, h number of points of the hull. Worst case complexity is O(n^2).

Specified by:

convexHull in interface ConvexHull2D

Parameters:

points - a set of points

Returns:

the convex polygon corresponding to the convex hull