[postgis-users] non-convex or concave hull
Paragon Corporation
lr at pcorp.us
Mon May 31 11:31:28 PDT 2010
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
More information about the postgis-users
mailing list