[postgis-devel] ST_ConcaveHull in GEOS

[Martin Davis]

As part of the replacement effort, the PostGIS doco needs some changes to
accurately describe the new Concave Hull behaviour.   In particular, there
are a few key differences:
- the target_percent parameter now defines a length ratio, rather than an
area ratio (see doc below).  This should make it easier to choose a
target_percent value that applies to a wider range of potential inputs,
since edge length is a less-constraining criterion than area.
- the concave hull algorithm only uses the vertices of the input geometry.
It does not respect the geometry linework (if any).  I think this is a
change from the current behaviour?
- because only vertices are considered, there is no longer a need to use
ST_Union to compute the hull of a set of polygons (and the input does not
even have to be valid)

New doc (comments welcome):
--------------------------------------------
Description
A concave hull of a geometry is a possibly concave geometry that encloses
the vertices of the input geometry. The result is a single polygon, line or
point. It will not contain holes unless the optional allow_holes argument
is specified as true.

One can think of a concave hull as a geometry obtained by "shrink-wrapping"
a set of points. This is different to the convex hull, which is more like
wrapping a rubber band around the points. The concave hull generally has a
smaller area and represents a more natural boundary for the input points.

The target_percent controls the concaveness of the computed hull. A value
of 1 produces the convex hull. A value of 0 produces a hull with maximum
concaveness (but still a single polygon). Values between 1 and 0 produce
hulls of increasing concaveness. Choosing a suitable value depends on the
nature of the input data, but often values between 0.4 and 0.2 produce
reasonable results.

Technically, the target percent determines a length as a fraction of the
difference between the longest and shortest edges in the Delaunay
Triangulation of the input points. Edges longer than this length are
"eroded" from the triangulation. The triangles remaining form the concave
hull.

This is not an aggregate function. To compute the concave hull of a set of
geometries use ST_Collect (e.g. ST_ConcaveHull( ST_Collect( geom ), 0.80).
---------------------

On Tue, Jan 25, 2022 at 2:38 PM Paul Ramsey <pramsey at cleverelephant.ca>
wrote:

> Hey all,
> The native ST_ConcaveHull in GEOS is in GEOS main now, so I have hooked it
> up into PostGIS in this branch
>
> https://github.com/pramsey/postgis/tree/master-concavehull
>
>
> Under this function for now.
>
> CREATE OR REPLACE FUNCTION _ST_GEOSConcaveHull(
>   geom geometry,
>   area_ratio float8,
>   allow_holes boolean DEFAULT false)
>
> I would like to just flip the old ST_ConcaveHull out and replace it with
> the new one, for folks with GEOS 3.11+, but I figured an interval to look
> at them side by side for a while on a test branch might be appreciated.
> Currently the case of point inputs is worth looking at. Polygon inputs that
> respect the polygon are (hull doesn't cross interior of input polygon)
> coming down the line.
>
> P
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20220126/a1cb7899/attachment-0001.html>