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
