concave hull ref

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

concave hull ref

Stefan Steiniger
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: concave hull ref

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: concave hull ref

Larry Becker
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...

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



--
http://amusingprogrammer.blogspot.com/

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: concave hull ref

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: concave hull ref

Stefan Steiniger
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: concave hull ref

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: concave hull ref

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: concave hull ref

Stefan Steiniger
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: concave hull ref

mbedward
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: concave hull ref

Martin Davis
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
Loading...