[postgis-users] non-convex or concave hull

[Dylan Beaudette]

On Monday 31 May 2010, Paragon Corporation wrote:
> 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
>

One small note on the 'alphahull' [1] package is based on code that does not 
comply with the GPL... So check out the attached license [2] if you plan on 
including it in your work.

1. http://cran.r-project.org/web/packages/alphahull/index.html
2. http://cran.r-project.org/web/packages/alphahull/LICENSE

Cheers,
Dylan


> 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
>
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users



-- 
Dylan Beaudette
Soil Resource Laboratory
http://casoilresource.lawr.ucdavis.edu/
University of California at Davis
530.754.7341