org.apache.commons.math3.geometry.euclidean.twod.hull

Class MonotoneChain

java.lang.Object

org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D

org.apache.commons.math3.geometry.euclidean.twod.hull.MonotoneChain

All Implemented Interfaces:

ConvexHullGenerator2D, ConvexHullGenerator<Euclidean2D,Vector2D>

public class MonotoneChain
extends AbstractConvexHullGenerator2D

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

Constructors

Constructor and Description
MonotoneChain() Create a new MonotoneChain instance.
MonotoneChain(boolean includeCollinearPoints) Create a new MonotoneChain instance.
MonotoneChain(boolean includeCollinearPoints, double tolerance) Create a new MonotoneChain instance.

Method Summary

Methods

Modifier and Type	Method and Description
java.util.Collection<Vector2D>	findHullVertices(java.util.Collection<Vector2D> points) Find the convex hull vertices from the set of input points.
private void	updateHull(Vector2D point, java.util.List<Vector2D> hull) Update the partial hull with the current point.

Methods inherited from class org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D

generate, getTolerance, isIncludeCollinearPoints

Methods inherited from class java.lang.Object

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

Constructor Detail

MonotoneChain

public MonotoneChain()

Create a new MonotoneChain instance.

MonotoneChain

public MonotoneChain(boolean includeCollinearPoints)

Create a new MonotoneChain instance.

Parameters:

includeCollinearPoints - whether collinear points shall be added as hull vertices

MonotoneChain

public MonotoneChain(boolean includeCollinearPoints,
             double tolerance)

Create a new MonotoneChain instance.

Parameters:

includeCollinearPoints - whether collinear points shall be added as hull vertices

tolerance - tolerance below which points are considered identical

Method Detail

findHullVertices

public java.util.Collection<Vector2D> findHullVertices(java.util.Collection<Vector2D> points)

Description copied from class: AbstractConvexHullGenerator2D

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

Specified by:

findHullVertices in class AbstractConvexHullGenerator2D

Parameters:

points - the set of input points

Returns:

the convex hull vertices in CCW winding

updateHull

private void updateHull(Vector2D point,
              java.util.List<Vector2D> hull)

Update the partial hull with the current point.

Parameters:

point - the current point

hull - the partial hull