geos::algorithm::hull::ConcaveHull Class Reference

`#include <ConcaveHull.h>`

## Public Member Functions

| ConcaveHull (const Geometry *geom)
void | setMaximumEdgeLength (double edgeLength)
void | setMaximumEdgeLengthRatio (double edgeLengthRatio)
void | setHolesAllowed (bool holesAllowed)
void | setAlpha (double newAlpha)
std::unique_ptr< Geometry > | getHull ()

## Static Public Member Functions

static double | uniformEdgeLength (const Geometry *geom)
static std::unique_ptr< Geometry > | concaveHullByLength (const Geometry *geom, double maxLength)
static std::unique_ptr< Geometry > | concaveHullByLength (const Geometry *geom, double maxLength, bool isHolesAllowed)
static std::unique_ptr< Geometry > | concaveHullByLengthRatio (const Geometry *geom, double lengthRatio)
static std::unique_ptr< Geometry > | concaveHullByLengthRatio (const Geometry *geom, double lengthRatio, bool isHolesAllowed)
static std::unique_ptr< Geometry > | alphaShape (const Geometry *geom, double alpha, bool isHolesAllowed)

## Detailed Description

Constructs a concave hull of a set of points. 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 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-independent.
- Maximum Area Ratio - the ratio of the concave hull area to the convex hull area will be no larger than this value
- 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 criterium 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 concavity present.

Other length criteria can be used by setting the Maximum Edge Length. 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() value.

The computed hull is always a single connected geom::Polygon (unless it is degenerate, in which case it will be a geom::Point or a geom::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 calling setHolesAllowed(boolean).

Author
  mdavis

## Member Function Documentation

## alphaShape()

std::unique_ptr< Geometry > geos::algorithm::hull::ConcaveHull::alphaShape | ( | const Geometry * | geom,
|  | double | alpha,
|  | bool | isHolesAllowed )

static

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

## concaveHullByLength()

std::unique_ptr< Geometry > geos::algorithm::hull::ConcaveHull::concaveHullByLength | ( | const Geometry * | geom,
|  | double | maxLength )

static

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

Parameters

  geom | the input geometry
  maxLength | the target maximum edge length

Returns
  the concave hull

References concaveHullByLength().

Referenced by concaveHullByLength().

## concaveHullByLengthRatio() [1/2]

std::unique_ptr< Geometry > geos::algorithm::hull::ConcaveHull::concaveHullByLengthRatio | ( | const Geometry * | geom,
|  | double | lengthRatio )

static

Computes the concave hull of the vertices in a geometry using the target criteria 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() [2/2]

std::unique_ptr< Geometry > geos::algorithm::hull::ConcaveHull::concaveHullByLengthRatio | ( | const Geometry * | geom,
|  | double | lengthRatio,
|  | bool | isHolesAllowed )

static

Computes the 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
  lengthRatio | the target maximum edge length
  isHolesAllowed | whether holes are allowed in the result

Returns
  the concave hull

## getHull()

std::unique_ptr< Geometry > geos::algorithm::hull::ConcaveHull::getHull | ( |  | ) |

Gets the computed concave hull.

Returns
  the concave hull

## setAlpha()

void geos::algorithm::hull::ConcaveHull::setAlpha | ( | double | newAlpha | ) |

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

  newAlpha | the alpha radius

## setHolesAllowed()

void geos::algorithm::hull::ConcaveHull::setHolesAllowed | ( | bool | holesAllowed | ) |

Sets whether holes are allowed in the concave hull polygon.

Parameters

  holesAllowed | true if holes are allowed in the result

## setMaximumEdgeLength()

void geos::algorithm::hull::ConcaveHull::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 value may be used as the basis for estimating an appropriate target maximum edge length.

Parameters

  edgeLength | a non-negative length

## setMaximumEdgeLengthRatio()

void geos::algorithm::hull::ConcaveHull::setMaximumEdgeLengthRatio | ( | double | edgeLengthRatio | ) |

Sets the target maximum edge length ratio for the concave hull. The edge length ratio is a fraction of the length delta between the longest and shortest edges in the Delaunay Triangulation of the input points. A value of 1.0 produces the convex hull. A value of 0.0 produces a concave hull of minimum area that is still connected.

Parameters

  edgeLengthRatio | a length ratio value between 0 and 1

## uniformEdgeLength()

double geos::algorithm::hull::ConcaveHull::uniformEdgeLength | ( | const Geometry * | geom | ) |

static

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

The documentation for this class was generated from the following file:

- ConcaveHull.h