Re: [postgis-users] Get concave hull from an array of longitude inlatitude points

[Stefan Zweig]

hi,

maybe will like that:
there is already a solution that has been developed for the pgrouting postgis extension. they call the algorithm "alpha shape" which to me seems to be the same like the concave hull algorithms. cf. the applet on this page: http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

i can find the natural c++ function which was written for postgis (http://pgrouting.postlbs.org/browser/tags/release-1.0/trunk/extra/driving_distance/src/alpha.c?rev=53), but unfortuneately can't find the pl/sql for postgis. but maybe you can find answers in the pgrouting lists.

regards,
stefan


> -----Ursprüngliche Nachricht-----
> Von: "Martin Davis" <mbdavis at refractions.net>
> Gesendet: 24.11.08 21:04:28
> An: PostGIS Users Discussion <postgis-users at postgis.refractions.net>
> Betreff: Re: [postgis-users] Get concave hull from an array of	longitude	inlatitude points


> Another approach is here:  
> http://www.fmepedia.com/index.php/Concave_Hull_Creator_Workspace
> 
> This looks like it builds a Delaunay TIN on the pointset, discards any 
> edges longer than a given tolerance, polygonizes the remaining edges, 
> and then merges all polygons.  This seems like it would be faster than 
> the approach on the Grass wiki.  It also has the nice property that 
> every vertex of the result is an input point.
> 
> Fascinating!
> 
> Martin Davis wrote:
> > Yeah, I saw that too.  Unfortunately the algorithm is only available 
> > by email, and is implemented in Mathematica.   It also sounds somewhat 
> > complex.
> > But I guess this sort of answers my question - there are algorithms 
> > which people have called "concave hull", and they produce concave 
> > polygons from sets of points in some kind of way.  I don't think 
> > there's any consensus on what algorithm to use, though.
> >
> > One interesting approach is here: 
> > http://grass.osgeo.org/wiki/Create_concave_hull
> >
> > In any case, obviously this isn't in PostGIS right now.
> >
> > Obe, Regina wrote:
> >>
> >> Evidentally its this thing
> >> http://ubicomp.algoritmi.uminho.pt/local/concavehull.html
> >>
> >> So I guess basically you take the boundary and you get rid of points
> >> that have points sitting to the right/left/top/or bottom of it and then
> >> you form a polygon from the remaining points.
> >>
> >> Well at least that is what it seems like to me visually.  Just not 
> >> quite sure how to program such a thing without writing yuck 
> >> procedural code.
> >>
> >> Hope that helps,
> >> Regina
> >>
> >>
> >
> 
> -- 
> Martin Davis
> Senior Technical Architect
> Refractions Research, Inc.
> (250) 383-3022
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
> 


____________________________________________________________________
Psssst! Schon vom neuen WEB.DE MultiMessenger gehört? 
Der kann`s mit allen: http://www.produkte.web.de/messenger/?did=3123