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. Iftrue
, 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 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
All Methods Instance Methods Concrete Methods Modifier and Type Method 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
-
-
-
-
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 verticestolerance
- tolerance below which points are considered identical
-
-
Method Detail
-
findHullVertices
public java.util.Collection<Vector2D> findHullVertices(java.util.Collection<Vector2D> points)
Find the convex hull vertices from the set of input points.- Specified by:
findHullVertices
in classAbstractConvexHullGenerator2D
- Parameters:
points
- the set of input points- Returns:
- the convex hull vertices in CCW winding
-
-