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.
Thanks
Andi
--
Psssst! Schon das coole Video vom GMX MultiMessenger gesehen?
Der Eine für Alle: http://www.gmx.net/de/go/messenger03
Andruit@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.
(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.
Let me know if this works.
Maciek
--
Maciej Sieczka
www.sieczka.org
On 10/08/08 09:21, Maciej Sieczka wrote:
Andruit@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
