[prev in list] [next in list] [prev in thread] [next in thread] 

List:       postgis-users
Subject:    =?iso-8859-15?Q?Re:_[postgis-users]_Get_concave_hull_from_an_array_of=09?=
From:       Stefan Zweig <stefanzweig1881 () web ! de>
Date:       2008-11-24 22:24:06
Message-ID: 911439418 () web ! de
[Download RAW message or body]

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@refractions.net>
> Gesendet: 24.11.08 21:04:28
> An: PostGIS Users Discussion <postgis-users@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@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

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


[prev in list] [next in list] [prev in thread] [next in thread]