public class MonotoneChain extends AbstractConvexHullGenerator2D
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.
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.
|
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.
|
generate, getTolerance, isIncludeCollinearPoints
public MonotoneChain()
public MonotoneChain(boolean includeCollinearPoints)
includeCollinearPoints
- whether collinear points shall be added as hull verticespublic MonotoneChain(boolean includeCollinearPoints, double tolerance)
includeCollinearPoints
- whether collinear points shall be added as hull verticestolerance
- tolerance below which points are considered identicalpublic java.util.Collection<Vector2D> findHullVertices(java.util.Collection<Vector2D> points)
AbstractConvexHullGenerator2D
findHullVertices
in class AbstractConvexHullGenerator2D
points
- the set of input pointsCopyright (c) 2003-2014 Apache Software Foundation