Class ConcaveHullOfPolygons


  • public class ConcaveHullOfPolygons
    extends java.lang.Object
    Constructs a concave hull of a set of polygons, respecting the polygons as constraints. A concave hull is a concave or convex polygon containing all the input polygons, whose vertices are a subset of the vertices in the input. A given set of polygons has a sequence of hulls of increasing concaveness, determined by a numeric target parameter. The computed hull "fills the gap" between the polygons, and does not intersect their interior.

    The concave hull is constructed by removing the longest outer edges of the constrained Delaunay Triangulation of the space between the polygons, until the target criterion parameter is reached.

    The target criteria are:

    • Maximum Edge Length - the length of the longest edge between the polygons is no larger than this value.
    • Maximum Edge Length Ratio - determine the Maximum Edge Length as a fraction of the difference between the longest and shortest edge lengths between the polygons. This provides a scale-free parameter. A value of 1 produces the convex hull; a value of 0 produces the original polygons.
    Optionally the concave hull can be allowed to contain holes, via setHolesAllowed(boolean).

    The hull can be specified as being "tight", via setTight(boolean). This causes the result to follow the outer boundaries of the input polygons.

    Instead of the complete hull, the "fill area" between the input polygons can be computed using getFill().

    The input polygons must form a valid MultiPolygon (i.e. they must be non-overlapping and non-edge-adjacent). If needed, a set of possibly-overlapping Polygons can be converted to a valid MultiPolygon by using Geometry.union();

    Author:
    Martin Davis
    • Constructor Summary

      Constructors 
      Constructor Description
      ConcaveHullOfPolygons​(Geometry polygons)
      Creates a new instance for a given geometry.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static Geometry concaveFillByLength​(Geometry polygons, double maxLength)
      Computes a concave fill area between a set of polygons, using the target criterion of maximum edge length.
      static Geometry concaveFillByLengthRatio​(Geometry polygons, double lengthRatio)
      Computes a concave fill area between a set of polygons, using the target criterion of maximum edge length ratio.
      static Geometry concaveHullByLength​(Geometry polygons, double maxLength)
      Computes a concave hull of set of polygons using the target criterion of maximum edge length.
      static Geometry concaveHullByLength​(Geometry polygons, double maxLength, boolean isTight, boolean isHolesAllowed)
      Computes a concave hull of set of polygons using the target criterion of maximum edge length, and allowing control over whether the hull boundary is tight and can contain holes.
      static Geometry concaveHullByLengthRatio​(Geometry polygons, double lengthRatio)
      Computes a concave hull of set of polygons using the target criterion of maximum edge length ratio.
      static Geometry concaveHullByLengthRatio​(Geometry polygons, double lengthRatio, boolean isTight, boolean isHolesAllowed)
      Computes a concave hull of set of polygons using the target criterion of maximum edge length ratio, and allowing control over whether the hull boundary is tight and can contain holes.
      Geometry getFill()
      Gets the concave fill, which is the area between the input polygons, subject to the concaveness control parameter.
      Geometry getHull()
      Gets the computed concave hull.
      void setHolesAllowed​(boolean isHolesAllowed)
      Sets whether holes are allowed in the concave hull polygon.
      void setMaximumEdgeLength​(double edgeLength)
      Sets the target maximum edge length for the concave hull.
      void setMaximumEdgeLengthRatio​(double edgeLengthRatio)
      Sets the target maximum edge length ratio for the concave hull.
      void setTight​(boolean isTight)
      Sets whether the boundary of the hull polygon is kept tight to the outer edges of the input polygons.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • ConcaveHullOfPolygons

        public ConcaveHullOfPolygons​(Geometry polygons)
        Creates a new instance for a given geometry.
        Parameters:
        geom - the input geometry
    • Method Detail

      • concaveHullByLength

        public static Geometry concaveHullByLength​(Geometry polygons,
                                                   double maxLength)
        Computes a concave hull of set of polygons using the target criterion of maximum edge length.
        Parameters:
        polygons - the input polygons
        maxLength - the target maximum edge length
        Returns:
        the concave hull
      • concaveHullByLength

        public static Geometry concaveHullByLength​(Geometry polygons,
                                                   double maxLength,
                                                   boolean isTight,
                                                   boolean isHolesAllowed)
        Computes a concave hull of set of polygons using the target criterion of maximum edge length, and allowing control over whether the hull boundary is tight and can contain holes.
        Parameters:
        polygons - the input polygons
        maxLength - the target maximum edge length
        isTight - true if the hull should be tight to the outside of the polygons
        isHolesAllowed - true if holes are allowed in the hull polygon
        Returns:
        the concave hull
      • concaveHullByLengthRatio

        public static Geometry concaveHullByLengthRatio​(Geometry polygons,
                                                        double lengthRatio)
        Computes a concave hull of set of polygons using the target criterion of maximum edge length ratio.
        Parameters:
        polygons - the input polygons
        lengthRatio - the target maximum edge length ratio
        Returns:
        the concave hull
      • concaveHullByLengthRatio

        public static Geometry concaveHullByLengthRatio​(Geometry polygons,
                                                        double lengthRatio,
                                                        boolean isTight,
                                                        boolean isHolesAllowed)
        Computes a concave hull of set of polygons using the target criterion of maximum edge length ratio, and allowing control over whether the hull boundary is tight and can contain holes.
        Parameters:
        polygons - the input polygons
        lengthRatio - the target maximum edge length ratio
        isTight - true if the hull should be tight to the outside of the polygons
        isHolesAllowed - true if holes are allowed in the hull polygon
        Returns:
        the concave hull
      • concaveFillByLength

        public static Geometry concaveFillByLength​(Geometry polygons,
                                                   double maxLength)
        Computes a concave fill area between a set of polygons, using the target criterion of maximum edge length.
        Parameters:
        polygons - the input polygons
        maxLength - the target maximum edge length
        Returns:
        the concave fill
      • concaveFillByLengthRatio

        public static Geometry concaveFillByLengthRatio​(Geometry polygons,
                                                        double lengthRatio)
        Computes a concave fill area between a set of polygons, using the target criterion of maximum edge length ratio.
        Parameters:
        polygons - the input polygons
        lengthRatio - the target maximum edge length ratio
        Returns:
        the concave fill
      • setMaximumEdgeLength

        public void setMaximumEdgeLength​(double edgeLength)
        Sets the target maximum edge length for the concave hull. The length value must be zero or greater.
        • The value 0.0 produces the input polygons.
        • Larger values produce less concave results. Above a certain large value the result is the convex hull of the input.

          The edge length ratio provides a scale-free parameter which is intended to produce similar concave results for a variety of inputs.

        Parameters:
        edgeLength - a non-negative length
      • setMaximumEdgeLengthRatio

        public void setMaximumEdgeLengthRatio​(double edgeLengthRatio)
        Sets the target maximum edge length ratio for the concave hull. The edge length ratio is a fraction of the difference between the longest and shortest edge lengths in the Delaunay Triangulation of the area between the input polygons. (Roughly speaking, it is a fraction of the difference between the shortest and longest distances between the input polygons.) It is a value in the range 0 to 1.
        • The value 0.0 produces the original input polygons.
        • The value 1.0 produces the convex hull.
          Parameters:
          edgeLengthRatio - a length factor value between 0 and 1
        • setHolesAllowed

          public void setHolesAllowed​(boolean isHolesAllowed)
          Sets whether holes are allowed in the concave hull polygon.
          Parameters:
          isHolesAllowed - true if holes are allowed in the result
        • setTight

          public void setTight​(boolean isTight)
          Sets whether the boundary of the hull polygon is kept tight to the outer edges of the input polygons.
          Parameters:
          isTight - true if the boundary is kept tight
        • getHull

          public Geometry getHull()
          Gets the computed concave hull.
          Returns:
          the concave hull
        • getFill

          public Geometry getFill()
          Gets the concave fill, which is the area between the input polygons, subject to the concaveness control parameter.
          Returns:
          the concave fill