Class ConvexHull

java.lang.Object
org.locationtech.jts.algorithm.ConvexHull

public class ConvexHull extends Object
Computes the convex hull of a Geometry. The convex hull is the smallest convex Geometry that contains all the points in the input Geometry.

Uses the Graham Scan algorithm.

Version:
1.7
  • Field Details

  • Constructor Details

    • ConvexHull

      public ConvexHull(Geometry geometry)
      Create a new convex hull construction for the input Geometry.
    • ConvexHull

      public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory)
      Create a new convex hull construction for the input Coordinate array.
  • Method Details

    • extractCoordinates

      private static Coordinate[] extractCoordinates(Geometry geom)
    • getConvexHull

      public Geometry getConvexHull()
      Returns a Geometry that represents the convex hull of the input geometry. The returned geometry contains the minimal number of points needed to represent the convex hull. In particular, no more than two consecutive points will be collinear.
      Returns:
      if the convex hull contains 3 or more points, a Polygon; 2 points, a LineString; 1 point, a Point; 0 points, an empty GeometryCollection.
    • toCoordinateArray

      protected Coordinate[] toCoordinateArray(Stack stack)
      An alternative to Stack.toArray, which is not present in earlier versions of Java.
    • reduce

      private Coordinate[] reduce(Coordinate[] inputPts)
      Uses a heuristic to reduce the number of points scanned to compute the hull. The heuristic is to find a polygon guaranteed to be in (or on) the hull, and eliminate all points inside it. A quadrilateral defined by the extremal points in the four orthogonal directions can be used, but even more inclusive is to use an octilateral defined by the points in the 8 cardinal directions.

      Note that even if the method used to determine the polygon vertices is not 100% robust, this does not affect the robustness of the convex hull.

      To satisfy the requirements of the Graham Scan algorithm, the returned array has at least 3 entries.

      Parameters:
      pts - the points to reduce
      Returns:
      the reduced list of points (at least 3)
    • padArray3

      private Coordinate[] padArray3(Coordinate[] pts)
    • preSort

      private Coordinate[] preSort(Coordinate[] pts)
    • grahamScan

      private Stack grahamScan(Coordinate[] c)
      Uses the Graham Scan algorithm to compute the convex hull vertices.
      Parameters:
      c - a list of points, with at least 3 entries
      Returns:
      a Stack containing the ordered points of the convex hull ring
    • isBetween

      private boolean isBetween(Coordinate c1, Coordinate c2, Coordinate c3)
      Returns:
      whether the three coordinates are collinear and c2 lies between c1 and c3 inclusive
    • computeOctRing

      private Coordinate[] computeOctRing(Coordinate[] inputPts)
    • computeOctPts

      private Coordinate[] computeOctPts(Coordinate[] inputPts)
    • lineOrPolygon

      private Geometry lineOrPolygon(Coordinate[] coordinates)
      Parameters:
      vertices - the vertices of a linear ring, which may or may not be flattened (i.e. vertices collinear)
      Returns:
      a 2-vertex LineString if the vertices are collinear; otherwise, a Polygon with unnecessary (collinear) vertices removed
    • cleanRing

      private Coordinate[] cleanRing(Coordinate[] original)
      Parameters:
      vertices - the vertices of a linear ring, which may or may not be flattened (i.e. vertices collinear)
      Returns:
      the coordinates with unnecessary (collinear) vertices removed