Hi,
anothe recent artile by Matt Duckham on Concave Hulls. The draft (not the final version) is here: http://www.geosensor.net/papers/duckham08.PR.pdf But I am not sure if these authors will chare their code. More articles on that have been published by one of the authors - Anthony Galton. Furthermore if you read the stuff you will see that there is no unique solution. stefan _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Fascinating stuff...
Here's a couple of the Galton papers Stefan refers to. http://www.comp.leeds.ac.uk/ontology/FOGI-WS/statements/Antony-Galton.pdf http://www.latingeo.net/datos_latingeo/noticias_doc/108Polyhulls-Galton.pdf He appears to be taking a psycho-computational approach to the problem. Interesting, but hard to see how this will translate into a concrete algorithm. (Although I guess the Duckham et al paper might have ideas on this). There was a thread on this on the PostGIS a while back, I think. There's definitely some non-patented approaches out there. See this for instance: http://n2.nabble.com/Concave-hull-of-a-set-of-points-(alphashapes)-td1880426.html#a1880426 Stefan Steiniger wrote: > Hi, > > anothe recent artile by Matt Duckham on Concave Hulls. The draft (not > the final version) is here: > http://www.geosensor.net/papers/duckham08.PR.pdf > > But I am not sure if these authors will chare their code. More > articles on that have been published by one of the authors - Anthony > Galton. Furthermore if you read the stuff you will see that there is > no unique solution. > > stefan > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Everyone seems to use length as a parameter to determine the solution set. Length is dataset dependent. I wonder if this dependency could be factored out by specifying a percent of extent, or perhaps a target fractal dimension.
Larry On Fri, Apr 3, 2009 at 10:48 AM, Martin Davis <[hidden email]> wrote: Fascinating stuff... -- http://amusingprogrammer.blogspot.com/ _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
That's an interesting idea too. It's always nice to look for ways to
remove "magic numbers" from algorithms, and this one seems like a good candidate for doing that. Galton's approach of looking for some sort of minima on the "Pareto front" sounds like it's heading in this direction (although I admit I don't fully understand it, or how it leads to a workable algorithm). Larry Becker wrote: > Everyone seems to use length as a parameter to determine the solution > set. Length is dataset dependent. I wonder if this dependency could > be factored out by specifying a percent of extent, or perhaps a target > fractal dimension. > > Larry > > On Fri, Apr 3, 2009 at 10:48 AM, Martin Davis <[hidden email] > <mailto:[hidden email]>> wrote: > > Fascinating stuff... > > Here's a couple of the Galton papers Stefan refers to. > > http://www.comp.leeds.ac.uk/ontology/FOGI-WS/statements/Antony-Galton.pdf > http://www.latingeo.net/datos_latingeo/noticias_doc/108Polyhulls-Galton.pdf > > He appears to be taking a psycho-computational approach to the > problem. Interesting, but hard to see how this will translate > into a concrete algorithm. (Although I guess the Duckham et al > paper might have ideas on this). > > > There was a thread on this on the PostGIS a while back, I think. > There's definitely some non-patented approaches out there. See > this for instance: > http://n2.nabble.com/Concave-hull-of-a-set-of-points-(alphashapes)-td1880426.html#a1880426 > <http://n2.nabble.com/Concave-hull-of-a-set-of-points-%28alphashapes%29-td1880426.html#a1880426> > > > > > > > Stefan Steiniger wrote: > > Hi, > > anothe recent artile by Matt Duckham on Concave Hulls. The > draft (not the final version) is here: > http://www.geosensor.net/papers/duckham08.PR.pdf > > But I am not sure if these authors will chare their code. More > articles on that have been published by one of the authors - > Anthony Galton. Furthermore if you read the stuff you will > see that there is no unique solution. > > stefan > > _______________________________________________ > jts-devel mailing list > [hidden email] > <mailto:[hidden email]> > http://lists.refractions.net/mailman/listinfo/jts-devel > > _______________________________________________ > jts-devel mailing list > [hidden email] > <mailto:[hidden email]> > http://lists.refractions.net/mailman/listinfo/jts-devel > > > > > -- > http://amusingprogrammer.blogspot.com/ > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
In reply to this post by Stefan Steiniger
...
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 [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
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 > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
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 >> [hidden email] >> http://lists.refractions.net/mailman/listinfo/jts-devel >> > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
In reply to this post by Stefan Steiniger
Martin, I love your comment:
>> How refreshing to have a paper which >> contains an algorithm which is actually easy to implement! as I am not sure if this one would give me a head-ache or not (i - pseudo code looks nice..but still, ii - do you have a delauney triangulation already implemented in JTS? - I didn't know that) I am glad that there are people out there like you that are a) into programming and b) still understand all that computational geometry stuff - I wished I would be a 'math' person sometimes. stefan PS: if somebody needs the original/final version from a paper mentioned - ask me. We have pretty good access to all the major journals/publishers here at UofC. _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Here is the reference about an alpha-shapes approach that Dragan has
been basing his implementation on. > http://www.isprs.org/congresses/beijing2008/proceedings/3b_pdf/37.pdf > Stefan, I'm interested in the student presentation that you mentioned involving animal tracking data. I'm working with similar data, both real and simulated. Michael _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
In reply to this post by Stefan Steiniger
Believe me, even given the dependence on Delaunay Triangulation this
algorithm is simple compared to most that appear in papers! There's lots of public code for DT out there (as always, the trick is finding high quality, robust, performant code! ) I do have DT code which I'm hoping to roll into JTS in a month or two. Stay tuned... Thanks for the offer about papers - sometimes it's very hard to get your hands on academic papers, so that could be very useful. M Stefan Steiniger wrote: > Martin, I love your comment: > > >> How refreshing to have a paper which > >> contains an algorithm which is actually easy to implement! > > as I am not sure if this one would give me a head-ache or not (i - > pseudo code looks nice..but still, ii - do you have a delauney > triangulation already implemented in JTS? - I didn't know that) > > I am glad that there are people out there like you that are a) into > programming and b) still understand all that computational geometry > stuff - I wished I would be a 'math' person sometimes. > > stefan > > PS: if somebody needs the original/final version from a paper > mentioned - ask me. We have pretty good access to all the major > journals/publishers here at UofC. > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Free forum by Nabble | Edit this page |