[GRASS-user] Concave hull of a set of points (alphashapes)

[Moritz Lennert]

On 10/08/08 09:21, Maciej Sieczka wrote:
> Andruit at gmx.de pisze:
>> Hello,
>> I have a set of points and would like to compute the concave hull of it.
>>
>> Is it possible within grass and has anybody done it before.


AFAIK, the problem with concave hull is that there is not one definitive 
answer, as you there are different ways of drawing the concave hull...

> 
> (Not tested idea:)
> 
> Connect all points with v.distance. Get rid of doubled lines with
> v.clean tool=rmdupl. Turn lines into boundaries with v.type - this
> creates areas without centroids. Add a centroid to each area. Make sure
> each centroid has the same category (use v.category if needed). Dissolve
> areas (v.dissolve) - you should get a single area with nodes only at the
> most outer points you had in your input dataset.

Which IIUC is the convex hull, i.e. the same result as v.hull. But you 
can reach something like a concave hull through the following steps 
(building on Maciej's suggestion):

- create map of lines connecting all points (I find it easier to do this 
with v.net.visibility, but v.distance works also)
- add a table with a column 'cat' and a column 'length double precision' 
and categories to these lines (v.db.addtable, v.category)
- upload the length of each line to the table (v.to.db)
- visually identify a length threshold above which the lines should not 
be used
- extract only those lines below that threshold (v.extract 
where="length<MAXLENGTH)
- convert the lines to boundaries (v.type)
- break overlapping lines (v.clean tool=break, there shouldn't be any 
duplicate lines, but just in case you can also use rmdupl)
- add centroids with the same category value to the boundaries 
(v.centroids step=0)
- dissolve the areas into one (v.dissolve)

I've attached an image to show the results:

green points: original points
blue line: result of v.hull
red line: result of above algorithm

Moritz
-------------- next part --------------
A non-text attachment was scrubbed...
Name: concave_hull.jpg
Type: image/jpeg
Size: 45410 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/grass-user/attachments/20080810/94ed21ae/concave_hull-0001.jpg