Class MonotoneChain
java.lang.Object
org.hipparchus.geometry.euclidean.twod.hull.MonotoneChain
 All Implemented Interfaces:
ConvexHullGenerator2D
,ConvexHullGenerator<Euclidean2D,
Vector2D>
Implements Andrew's monotone chain method to generate the convex hull of a finite set of
points in the twodimensional 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 xcoordinate), 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: 1e10) is used as epsilon criteria to determine
identical and collinear points.

Constructor Summary
ConstructorDescriptionCreate a new MonotoneChain instance.MonotoneChain
(boolean includeCollinearPoints) Create a new MonotoneChain instance.MonotoneChain
(boolean includeCollinearPoints, double tolerance) Create a new MonotoneChain instance. 
Method Summary
Modifier and TypeMethodDescriptionfindHullVertices
(Collection<Vector2D> points) Find the convex hull vertices from the set of input points.generate
(Collection<Vector2D> points) Builds the convex hull from the set of input points.double
Get the tolerance below which points are considered identical.boolean
Returns if collinear points on the hull will be added as hull vertices.

Constructor Details

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 verticestolerance
 tolerance below which points are considered identical


Method Details

findHullVertices
Find the convex hull vertices from the set of input points. Parameters:
points
 the set of input points Returns:
 the convex hull vertices in CCW winding

getTolerance
public double getTolerance()Get the tolerance below which points are considered identical. Returns:
 the tolerance below which points are considered identical

isIncludeCollinearPoints
public boolean isIncludeCollinearPoints()Returns if collinear points on the hull will be added as hull vertices. Returns:
true
if collinear points are added as hull vertices, orfalse
if only extreme points are present.

generate
Builds the convex hull from the set of input points. Specified by:
generate
in interfaceConvexHullGenerator<Euclidean2D,
Vector2D>  Specified by:
generate
in interfaceConvexHullGenerator2D
 Parameters:
points
 the set of input points Returns:
 the convex hull
 Throws:
MathIllegalStateException
 if generator fails to generate a convex hull for the given set of input points
