Class ConvexHull


  • public class ConvexHull
    extends java.lang.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
    • Constructor Detail

      • ConvexHull

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

      • 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​(java.util.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)
      • grahamScan

        private java.util.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
      • 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