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

[Rob Tester]

CGAL has an open source implementation of the algorithm. (Along with some
other really neat things like vonoroi).

http://www.cgal.org/




-----Original Message-----
From: postgis-users-bounces at postgis.refractions.net
[mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of Tim
Bowden
Sent: Monday, November 24, 2008 9:50 PM
To: PostGIS Users Discussion
Subject: Re: [postgis-users] Get concave hull from an array of longitude
inlatitude points


On Mon, 2008-11-24 at 11:37 -0800, 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. 

There is a paper published on this algorithm:
http://hdl.handle.net/1822/6429 but if you click through you get a form
to fill in requesting a copy from the authors and your reason for
wanting a copy.  I have no idea why it's restricted but there you go.

It would certainly be a useful piece of functionality.  I've wasted many
hours over the years building boundaries for tin's.  On large data sets
it's a cumbersome job.

> 
> 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

The problem with this approach is for most data sets (at least those
I've dealt with) there is no clear division between the longest wanted
tin face and the shortest unwanted tin vertex.  That method will do a
gross cleanup, but fine tuning will always be needed.

Regards,
Tim Bowden

> 
> 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
> >
> >
> > -----Original Message-----
> > From: postgis-users-bounces at postgis.refractions.net on behalf of 
> > Martin Davis
> > Sent: Mon 11/24/2008 1:58 PM
> > To: PostGIS Users Discussion
> > Subject: Re: [postgis-users] Get concave hull from an array of 
> > longitude inlatitude points
> >
> > What's a concave hull?
> >
> > Ales Kecman wrote:
> > > Hi!
> > >
> > >
> > > I'm new to Postgis and would really like to get some help on getting a
> > > concave hull from an array of points.
> > >
> > > For example:
> > >
> > > I have an array of points - longitude and latitude of buildings in
> > > particular area in the city. I already managed to get a convex hull
> > > polygon from this array of points, but this is not really helpful.
> > > What I'm trying to get is some kind of concave hull polygon from an
> > > array of points, which I would further like to use in Google Earth kml
> > > file.
> > >
> > > Thanks.
> > >
------------------------------------------------------------------------
> > >
> > > _______________________________________________
> > > postgis-users mailing list
> > > postgis-users at postgis.refractions.net
> > > http://postgis.refractions.net/mailman/listinfo/postgis-users
> > >  
> >
> > --
> > 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
> >
> > ------------------------------------------------------------------------
> >
> > *The substance of this message, including any attachments, may be 
> > confidential, legally privileged and/or exempt from disclosure 
> > pursuant to Massachusetts law. It is intended solely for the 
> > addressee. If you received this in error, please contact the sender 
> > and delete the material from any computer. *
> >
> > ------------------------------------------------------------------------
> >
> > * Help make the earth a greener place. If at all possible resist 
> > printing this email and join us in saving paper. *
> >
> > * *
> >
> > * *
> >
> > ------------------------------------------------------------------------
> >
> > _______________________________________________
> > postgis-users mailing list
> > postgis-users at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-users
> >   
> 
-- 
Experience is that marvelous thing that enables you recognize a mistake
when you make it again.

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