public class MonotoneChain extends Object
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 |
---|---|
Collection<Vector2D> |
findHullVertices(Collection<Vector2D> points)
Find the convex hull vertices from the set of input points.
|
ConvexHull2D |
generate(Collection<Vector2D> points)
Builds the convex hull from the set of input points.
|
double |
getTolerance()
Get the tolerance below which points are considered identical.
|
boolean |
isIncludeCollinearPoints()
Returns if collinear points on the hull will be added as hull vertices.
|
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 Collection<Vector2D> findHullVertices(Collection<Vector2D> points)
points
- the set of input pointspublic double getTolerance()
public boolean isIncludeCollinearPoints()
true
if collinear points are added as hull vertices, or false
if only extreme points are present.public ConvexHull2D generate(Collection<Vector2D> points) throws NullArgumentException, ConvergenceException
generate
in interface ConvexHullGenerator2D
generate
in interface ConvexHullGenerator<Euclidean2D,Vector2D>
points
- the set of input pointsNullArgumentException
- if the input collection is null
ConvergenceException
- if generator fails to generate a convex hull for
the given set of input pointsCopyright © 2003–2016 The Apache Software Foundation. All rights reserved.