MonotoneChain

java.lang.Object
- org.apache.commons.math3.geometry.euclidean.twod.hull.MonotoneChain

All Implemented Interfaces:

ConvexHullGenerator2D, ConvexHullGenerator<Euclidean2D,Vector2D>
```
public class MonotoneChain
extends Object
```
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

All Methods Instance Methods Concrete Methods
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.

Methods inherited from class java.lang.Object
equals, 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 Collection<Vector2D> findHullVertices(Collection<Vector2D> points)
```
    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, or false if only extreme points are present.
  - generate
```
public ConvexHull2D generate(Collection<Vector2D> points)
                      throws NullArgumentException,
                             ConvergenceException
```
    Builds the convex hull from the set of input points.
    
    Specified by:
    
    generate in interface ConvexHullGenerator2D
    
    Specified by:
    
    generate in interface ConvexHullGenerator<Euclidean2D,Vector2D>
    
    Parameters:
    
    points - the set of input points
    
    Returns:
    
    the convex hull
    
    Throws:
    
    NullArgumentException - if the input collection is null
    
    ConvergenceException - if generator fails to generate a convex hull for the given set of input points

Class MonotoneChain

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

MonotoneChain

MonotoneChain

MonotoneChain

Method Detail

findHullVertices

getTolerance

isIncludeCollinearPoints

generate