[postgis-devel] ST_ConcaveHull in GEOS

[Regina Obe]

Martin,

 

Feel free to take a stab at updating the docs, but what you describe below sounds good to me to detail the change in shrink behavior.

I think the new GEOS concave hull is far more scientific about it than the old, so most people will prefer the new behavior.

 

 

From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On Behalf Of Martin Davis
Sent: Wednesday, January 26, 2022 2:55 PM
To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
Subject: Re: [postgis-devel] ST_ConcaveHull in GEOS

 

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 <mailto: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 <mailto: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/169a5825/attachment.html>