Namespace NetTopologySuite.Algorithm.Hull

Contains classes implementing algorithms to compute hulls of geometry objects.

See also ConvexHull

Classes

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.

ConcaveHullOfPolygons

Constructs a concave hull of a set of polygons, respecting the polygons as constraints. A concave hull is a possibly non-convex polygon containing all the input polygons. 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 Delaunay Triangulation of the space between the polygons, until the target criterion parameter is reached.

The target criteria are:

• Maximum Edge Lengththe length of the longest edge between the polygons is no larger than this value.
• Maximum Edge Length Ratiodetermine the Maximum Edge Length as a fraction of the difference between the longest and shortest edge lengths between the polygons. This normalizes the Maximum Edge Length to be scale-free. A value of 1 produces the convex hull; a value of 0 produces the original polygons.

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).

Optionally the concave hull can be allowed to contain holes, via HolesAllowed.

The hull can be specified as being "tight", which means it follows the outer boundaries of the input polygons.

The input polygons must form a valid MultiPolygon (i.e.they must be non - overlapping).