Class ConcaveHull

Constructs a concave hull of a set of points. A concave hull is a possibly non-convex polygon containing all the input points. 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 Factor	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 criteria.

Optionally the concave hull can be allowed to contain holes by setting HolesAllowed.

Inheritance

object

ConcaveHull

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: NetTopologySuite.Algorithm.Hull

Assembly: NetTopologySuite.dll

Syntax

public class ConcaveHull

Constructors

ConcaveHull(Geometry)

Creates a new instance for a given geometry.

Declaration

public ConcaveHull(Geometry geom)

Parameters

Type	Name	Description
Geometry	geom	The input geometry

Properties

Alpha

Gets or 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.

Declaration

public double Alpha { get; set; }

Property Value

Type	Description
double

HolesAllowed

Gets or sets whether holes are allowed in the concave hull polygon.

Declaration

public bool HolesAllowed { get; set; }

Property Value

Type	Description
bool

MaximumEdgeLength

Gets or 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.

Declaration

public double MaximumEdgeLength { get; set; }

Property Value

Type	Description
double	The target maximum edge length for the concave hull

See Also

UniformGridEdgeLength(Geometry)

MaximumEdgeLengthRatio

Gets or 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.

Declaration

public double MaximumEdgeLengthRatio { get; set; }

Property Value

Type	Description
double	The target maximum edge length factor for the concave hull

Methods

AlphaShape(Geometry, double, bool)

Computes the alpha shape of a geometry as a polygon. The alpha parameter is the radius of the eroding disc.

Declaration

public static Geometry AlphaShape(Geometry geom, double alpha, bool isHolesAllowed)

Parameters

Type	Name	Description
Geometry	geom	The input geometry
double	alpha	The radius of the eroding disk
bool	isHolesAllowed	A flag indicating if holes are allowed in the result

Returns

Type	Description
Geometry	The alpha schape polygon

ConcaveHullByLength(Geometry, double)

Computes the concave hull of the vertices in a geometry using the target criterion of maximum edge length.

Declaration

public static Geometry ConcaveHullByLength(Geometry geom, double maxLength)

Parameters

Type	Name	Description
Geometry	geom	The input geometry
double	maxLength	The target maximum edge length

Returns

Type	Description
Geometry	The concave hull

ConcaveHullByLength(Geometry, double, bool)

Computes the concave hull of the vertices in a geometry using the target criterion of maximum edge length, and optionally allowing holes.

Declaration

public static Geometry ConcaveHullByLength(Geometry geom, double maxLength, bool isHolesAllowed)

Parameters

Type	Name	Description
Geometry	geom	The input geometry
double	maxLength	The target maximum edge length
bool	isHolesAllowed	A flag whether holes are allowed in the result

Returns

Type	Description
Geometry	The concave hull

ConcaveHullByLengthRatio(Geometry, double)

Computes the 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.

Declaration

public static Geometry ConcaveHullByLengthRatio(Geometry geom, double lengthRatio)

Parameters

Type	Name	Description
Geometry	geom	The input geometry
double	lengthRatio	The target edge length ratio

Returns

Type	Description
Geometry	The concave hull

ConcaveHullByLengthRatio(Geometry, double, bool)

Computes the concave hull of the vertices in a geometry using the target criterion of maximum edge length ratio, 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.

Declaration

public static Geometry ConcaveHullByLengthRatio(Geometry geom, double lengthRatio, bool isHolesAllowed)

Parameters

Type	Name	Description
Geometry	geom	The input geometry
double	lengthRatio	The target edge length ratio
bool	isHolesAllowed	A flag whether holes are allowed in the result

Returns

Type	Description
Geometry	The concave hull

GetHull()

Gets the computed concave hull.

Declaration

public Geometry GetHull()

Returns

Type	Description
Geometry	The concave hull

UniformGridEdgeLength(Geometry)

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.

Declaration

public static double UniformGridEdgeLength(Geometry geom)

Parameters

Type	Name	Description
Geometry	geom	A geometry

Returns

Type	Description
double	The approximate uniform grid length