cartagen.hull_delaunay

hull_delaunay(points, length)

Create the hull of a set of points using the Delaunay triangulation.

This algorithm was described by Duckham et al. [1] and is also described in Galton & Duckham [2] It first computes the Delaunay triangulation of the points, and then removes iteratively the boundary edges that are longer than a given parameter.

Parameters:

• points (list of Point) – The set of points.

• length (float) – The length in meters below which the Delaunay triangles edges are removed.

Returns:

Polygon

Warning

This algorithm cannot create multiple polygons, unlike hull_swinging_arm(). Using a length too low can produce an invalid geometry.

See also

hull_swinging_arm

Create a polygon from a set of points using the swinging arm algorithm.

References

[1]

Matt Duckham, Lars Kulik, Mike Worboys, and Antony Galton. Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition, 41(10):3224–3236, 2008. URL: https://www.sciencedirect.com/science/article/pii/S0031320308001180, doi:https://doi.org/10.1016/j.patcog.2008.03.023.

[2]

Antony Galton and Matt Duckham. What is the region occupied by a set of points? In International Conference Geographic Information Science. 2006. URL: https://api.semanticscholar.org/CorpusID:18406174.

Examples

>>> points = [ Point(1, 1), Point(6, 6), Point(1, 6), Point(6, 5), Point(2, 4), Point(2, 1), Point(1, 4) ]
>>> delaunay_hull(points, 2.0)
<POLYGON ((1 1, 1 4, 1 6, 6 6, 6 5, 2 4, 2 1, 1 1))>

(Source code)