org.apache.commons.math3.geometry.euclidean.twod.hull

## Class 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
  Version:
    $Id: MonotoneChain.java 1568752 2014-02-16 12:19:51Z tn $
  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

    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

      `clone, equals, finalize, 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

Copyright © 2003–2014 The Apache Software Foundation. All rights reserved.