Class ConcaveHull

java.lang.Object
org.locationtech.jts.algorithm.hull.ConcaveHull

public class ConcaveHull extends Object
Constructs a concave hull of a set of points. A concave hull is a concave or convex polygon containing all the input points, whose vertices are a subset of the vertices in the input. A given set of points has a sequence of hulls of increasing concaveness, determined by a numeric target parameter.

The hull is constructed by removing border triangles of the Delaunay Triangulation of the points, as long as their "size" is larger than the target criterion.

The target criteria are:

  • Maximum Edge Length - the length of the longest edge of the hull is no larger than this value.
  • Maximum Edge Length Ratio - determines the Maximum Edge Length by a fraction of the difference between the longest and shortest edge lengths in the Delaunay Triangulation. This normalizes the Maximum Edge Length to be scale-free. A value of 1 produces the convex hull; a value of 0 produces maximum concaveness.
  • Alpha - produces Alpha-shapes, by removing border triangles with a circumradius greater than alpha. Large values produce the convex hull; a value of 0 produces maximum concaveness.
The preferred criterion is the Maximum Edge Length Ratio, since it is scale-free and local (so that no assumption needs to be made about the total amount of concaveness present).

Other length criteria can be used by setting the Maximum Edge Length directly. For example, use a length relative to the longest edge length in the Minimum Spanning Tree of the point set. Or, use a length derived from the uniformGridEdgeLength(Geometry) value.

The computed hull is always a single connected Polygon (unless it is degenerate, in which case it will be a Point or a LineString). This constraint may cause the concave hull to fail to meet the target criterion.

Optionally the concave hull can be allowed to contain holes by calling setHolesAllowed(boolean).

Author:
Martin Davis
  • Constructor Summary

    Constructors
    Constructor
    Description
    Creates a new instance for a given geometry.
  • Method Summary

    Modifier and Type
    Method
    Description
    static Geometry
    alphaShape(Geometry geom, double alpha, boolean isHolesAllowed)
    Computes the alpha shape of a geometry as a polygon.
    static Geometry
    concaveHullByLength(Geometry geom, double maxLength)
    Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length.
    static Geometry
    concaveHullByLength(Geometry geom, double maxLength, boolean isHolesAllowed)
    Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length, and optionally allowing holes.
    static Geometry
    concaveHullByLengthRatio(Geometry geom, double lengthRatio)
    Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length ratio.
    static Geometry
    concaveHullByLengthRatio(Geometry geom, double lengthRatio, boolean isHolesAllowed)
    Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length factor, and optionally allowing holes.
    Gets the computed concave hull.
    void
    setAlpha(double alpha)
    Sets the alpha parameter to compute an alpha shape of the input.
    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.
    static double
    Computes the approximate edge length of a uniform square grid having the same number of points as a geometry and the same area as its convex hull.

    Methods inherited from class java.lang.Object

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

    • ConcaveHull

      public ConcaveHull(Geometry geom)
      Creates a new instance for a given geometry.
      Parameters:
      geom - the input geometry
  • Method Details

    • uniformGridEdgeLength

      public static double uniformGridEdgeLength(Geometry geom)
      Computes the approximate edge length of a uniform square grid having the same number of points as a geometry and the same area as its convex hull. This value can be used to determine a suitable length threshold value for computing a concave hull. A value from 2 to 4 times the uniform grid length seems to produce reasonable results.
      Parameters:
      geom - a geometry
      Returns:
      the approximate uniform grid length
    • concaveHullByLength

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

      public static Geometry concaveHullByLength(Geometry geom, double maxLength, boolean isHolesAllowed)
      Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length, and optionally allowing holes.
      Parameters:
      geom - the input geometry
      maxLength - the target maximum edge length
      isHolesAllowed - whether holes are allowed in the result
      Returns:
      the concave hull
    • concaveHullByLengthRatio

      public static Geometry concaveHullByLengthRatio(Geometry geom, double lengthRatio)
      Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length ratio. The edge length ratio is a fraction of the length difference between the longest and shortest edges in the Delaunay Triangulation of the input points.
      Parameters:
      geom - the input geometry
      lengthRatio - the target edge length factor
      Returns:
      the concave hull
    • concaveHullByLengthRatio

      public static Geometry concaveHullByLengthRatio(Geometry geom, double lengthRatio, boolean isHolesAllowed)
      Computes a concave hull of the vertices in a geometry using the target criterion of maximum edge length factor, and optionally allowing holes. The edge length factor is a fraction of the length difference between the longest and shortest edges in the Delaunay Triangulation of the input points.
      Parameters:
      geom - the input geometry
      isHolesAllowed - whether holes are allowed in the result
      maxLength - the target maximum edge length
      Returns:
      the concave hull
    • alphaShape

      public static Geometry alphaShape(Geometry geom, double alpha, boolean isHolesAllowed)
      Computes the alpha shape of a geometry as a polygon. The alpha parameter is the radius of the eroding disc.
      Parameters:
      geom - the input geometry
      alpha - the radius of the eroding disc
      isHolesAllowed - whether holes are allowed in the result
      Returns:
      the alpha shape polygon
    • 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 concave hull of smallest area that is still connected.
      • Larger values produce less concave results. A value equal or greater than the longest Delaunay Triangulation edge length produces the convex hull.
      The uniformGridEdgeLength(Geometry) value may be used as the basis for estimating an appropriate target maximum edge length.
      Parameters:
      edgeLength - a non-negative length
      See Also:
    • 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 input points. It is a value in the range 0 to 1.
      • The value 0.0 produces a concave hull of minimum area that is still connected.
      • The value 1.0 produces the convex hull.
        Parameters:
        edgeLengthRatio - a length factor value between 0 and 1
      • setAlpha

        public void setAlpha(double alpha)
        Sets the alpha parameter to compute an alpha shape of the input. Alpha is the radius of the eroding disc. Border triangles with circumradius greater than alpha are removed.
        Parameters:
        alpha - the alpha radius
      • 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
      • getHull

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