[postgis-users] non-convex or concave hull

Paragon Corporation lr at pcorp.us
Mon May 31 11:31:28 PDT 2010


It is on our todo


I have a version that sort of works, but Martin Davis threw a curve ball at
me by pointing out a case where my algorithm fails so I was going to rewrite
it.  Just haven't had the motivation or time to revisit.

If you have the R package -- there are concave hull packages available too
though those would be messier to use than a native PostgreSQL function.


I can provide you what I have so far (but I haven't really stress tested it)
- it utilizes some of the new distance functions introduced in PostGIS 1.5 -
ST_ClosestPoint (possibly another), so won't work on lower versions on

Hope that helps,


-----Original Message-----
From: postgis-users-bounces at postgis.refractions.net
[mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of Andreas
Sent: Monday, May 31, 2010 4:44 AM
To: postgis-users at postgis.refractions.net
Subject: [postgis-users] non-convex or concave hull

Hi all,

I am looking for a method that generates me an enclosing polygon that should
contain all input geometries but is not as big as the polygon generated by
the ST_ConvexHull() command. The input should be a list of different
geometries (point,linestring,polygon), and the output should be one polygon
that can contain concave outlines but needs to guarantee that all input
geometries are inside. I don't know if any term exists for such a polygon.
Concave-hull? Non-convex hull?

Googling around I came across:


>From the figure, version "d" is actually what I want as a result. Or here is
another pointer:

My question now: Are there existing methods in Postgis or geos that would
help me generate such polygons? If not - how many hours would a Postgis
programmer potentially need to implement such an algorithm in Postgis?


Andreas Neumann

postgis-users mailing list
postgis-users at postgis.refractions.net

More information about the postgis-users mailing list