[postgis-users] non-convex or concave hull

[Paragon Corporation]

Andreas,

It is on our todo

http://trac.osgeo.org/postgis/ticket/312

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.

http://casoilresource.lawr.ucdavis.edu/drupal/node/919


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
PostGIS.

Hope that helps,
Regina

http://www.postgis.us
 

-----Original Message-----
From: postgis-users-bounces at postgis.refractions.net
[mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of Andreas
Neumann
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:

http://www.spatialanalysisonline.com/output/html/Non-convexhulls.html

>From the figure, version "d" is actually what I want as a result. Or here is
another pointer:
http://ubicomp.algoritmi.uminho.pt/local/concavehull.html

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?

Thanks,
Andreas

--
Andreas Neumann
http://www.carto.net/neumann/
http://www.svgopen.org/

_______________________________________________
postgis-users mailing list
postgis-users at postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-users