Description of the Point Cover Algorithms

Description of the algorithm

The Point Cover algorithm replace a point cloud by polygons that cover the region occupied by clusters of the points. First clusters have to be computed, using any of the available techniques. Then, a Delaunay Triangulation of the geographic object is created, and the longest segments (and their associated triangles) on the boundary of the hull are eliminated one by one, in order to reduce its spatial shape to the very structure of the points of the object. The algorithm stops in 4 cases:

The initial paper from Duckham & Galton describing the Delaunay based concave hull can be found here

Parameter name Description Type Default value
minLength the minimal length of a triangulation segment to be kept as the outline of the hull double (meters)  

Examples of generalization

Below, a set of points representing shipwrecks covered with the Delaunay concave hull of the clusters.

A set of points representing shipwrecks covered with the Delaunay concave hull

Below, a set of points representing shipwrecks covered with the convex hull of the clusters.

A set of points representing shipwrecks covered with the convex hull

When to use the algorithm?

The algorithm tends to unsmooth geographic lines, and is rarely used to simplify geographic features. But it can be very useful to quickly filter the vertices of a line inside another algorithm.

See Also