Top Description Constructors Methods
org.apache.commons.math3.geometry.euclidean.twod.hull

public Class MonotoneChain

extends AbstractConvexHullGenerator2D
Class Inheritance
Imports
java.util.ArrayList, .Collection, .Collections, .Comparator, .List, org.apache.commons.math3.geometry.euclidean.twod.Line, .Vector2D, org.apache.commons.math3.util.FastMath, .Precision
Implements Andrew's monotone chain method to generate the convex hull of a finite set of points in the two-dimensional euclidean space.

The runtime complexity is O(n log n), with n being the number of input points. If the point set is already sorted (by x-coordinate), the runtime complexity is O(n).

The implementation is not sensitive to collinear points on the hull. The parameter includeCollinearPoints allows to control the behavior with regard to collinear points. If true, all points on the boundary of the hull will be added to the hull vertices, otherwise only the extreme points will be present. By default, collinear points are not added as hull vertices.

The tolerance parameter (default: 1e-10) is used as epsilon criteria to determine identical and collinear points.

Since
3.3
See Also
Andrew's monotone chain algorithm (Wikibooks)

Constructor Summary

AccessConstructor and Description
public
MonotoneChain()

Create a new MonotoneChain instance.

public
MonotoneChain(final boolean
whether collinear points shall be added as hull vertices
includeCollinearPoints)

Create a new MonotoneChain instance.

public
MonotoneChain(final boolean
whether collinear points shall be added as hull vertices
includeCollinearPoints, final double
tolerance below which points are considered identical
tolerance)

Create a new MonotoneChain instance.

Method Summary

Modifier and TypeMethod and Description
public Collection<Vector2D>
findHullVertices(final Collection<Vector2D>
the set of input points
points)

Implements abstract org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D.findHullVertices.

Find the convex hull vertices from the set of input points.

private void
updateHull(final Vector2D
the current point
point, final List<Vector2D>
the partial hull
hull)

Update the partial hull with the current point.

Inherited from org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D:
generategetToleranceisIncludeCollinearPoints

Constructor Detail

MonotoneChainback to summary
public MonotoneChain()

Create a new MonotoneChain instance.

MonotoneChainback to summary
public MonotoneChain(final boolean includeCollinearPoints)

Create a new MonotoneChain instance.

Parameters
includeCollinearPoints:boolean

whether collinear points shall be added as hull vertices

MonotoneChainback to summary
public MonotoneChain(final boolean includeCollinearPoints, final double tolerance)

Create a new MonotoneChain instance.

Parameters
includeCollinearPoints:boolean

whether collinear points shall be added as hull vertices

tolerance:double

tolerance below which points are considered identical

Method Detail

findHullVerticesback to summary
public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points)

Implements abstract org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D.findHullVertices.

Doc from org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D.findHullVertices.

Find the convex hull vertices from the set of input points.

Parameters
points:Collection<Vector2D>

the set of input points

Returns:Collection<Vector2D>

the convex hull vertices in CCW winding

Annotations
@Override
updateHullback to summary
private void updateHull(final Vector2D point, final List<Vector2D> hull)

Update the partial hull with the current point.

Parameters
point:Vector2D

the current point

hull:List<Vector2D>

the partial hull