Class ConcaveHull
- java.lang.Object
-
- org.locationtech.jts.algorithm.hull.ConcaveHull
-
public class ConcaveHull extends java.lang.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 concave hull is constructed by removing the longest outer edges of the Delaunay Triangulation of the points, until the target criterion parameter is reached.
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 - determine the Maximum Edge Length as 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.
uniformGridEdgeLength(Geometry)
value.The computed hull is always a single connected
Polygon
(unless it is degenerate, in which case it will be aPoint
or aLineString
). This constraint may cause the concave hull to fail to meet the target criterion.Optionally the concave hull can be allowed to contain holes. Note that when using the area-based criterion this may result in substantially slower computation.
- Author:
- Martin Davis
-
-
Constructor Summary
Constructors Constructor Description ConcaveHull(Geometry geom)
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
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.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.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.
-
-
-
Constructor Detail
-
ConcaveHull
public ConcaveHull(Geometry geom)
Creates a new instance for a given geometry.- Parameters:
geom
- the input geometry
-
-
Method Detail
-
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 geometrymaxLength
- 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 geometrymaxLength
- the target maximum edge lengthisHolesAllowed
- 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 geometrylengthRatio
- 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 geometrymaxLength
- the target maximum edge lengthisHolesAllowed
- whether holes are allowed in the result- Returns:
- the concave hull
-
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.
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:
uniformGridEdgeLength(Geometry)
-
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
-
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
-
-