Now that I've had a chance to browse the Duckham paper, it looks like it
is proposing exactly the idea of a "weeded Delaunay triangulation".
Lucky them - first into a journal with this radical new concept! I
think I saw this mentioned on the FME wiki a while ago - I wonder if
they are aware of this? They do lots of investigation into the
properties of the shape, however. How refreshing to have a paper which
contains an algorithm which is actually easy to implement!
Martin Davis wrote:
Also interesting...
It looks to me like the LoCoH approach is not raster based, it's
vector. Basic idea seems to be unioning convex hulls of the k nearest
neighbours of each data point. So k is a parameter - not sure if they
have some way of choosing the best value of k. Shapes vary quite a
bit as k gets bigger, of course.
They also call this the k-NNCH algorithm - not sure how Moreria et al
can claim prior art since this seems similar to what they are talking
about.
Lots of different ways to skin this one, obviously, depending on what
your goal is. Pretty amusing to see the same basic problem tackled in
so many different ways and domains.
I still like the idea of a "weeded Delaunay triangulation" - it has a
nice computational-geometric basis, and should be pretty efficient to
compute. I might try and give this a go when I have some time.
Stefan Steiniger wrote:
...
Actually what I should add - I would need a concave hull
implementation too for my research but didn't found the time yet to
work on such thing (and doubt I will find it any time soon). We should
have made this a Google Summer of Code project.
However - I recently saw a presentation by a student of our department
who calculated "hulls" that are supposed to be animal habitats from
GPS tracks. She used Convex hull, kernel density (raster based), and
a further method - minimum convex hulls (LoCoH). Informations on the
latter method by Getz and Wilmers (2004) and Getz et al (2007) can be
found here:
http://locoh.cnr.berkeley.edu/
and
http://locoh.cnr.berkeley.edu/images/article.pdf
I haven't read the article yet - so it may be a raster based
approach. I have seen that derived polygons may contain holes. The
info says it is available for ArcGIS and R (which may indicate that
for R the source code is availble???). On the webpage you can even
upload you shp files.
maybe that is f interest too - or gives some more ideas for concave
hulls.
stefan
_______________________________________________
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
_______________________________________________
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
