Re: [jts-devel] Re: concave hull ref

[Michael Bedward]

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
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel

Re: [jts-devel] polygonizer and line strings

[Michael Bedward]

Well done Dragan - you've got Martin interested :-)  I suspect he will
find a solution slightly faster than I will !

Michael


2009/4/4 Martin Davis :
> Two possibilities:
>
> 1. bug in Polygonizer
> 2. your input is not fully noded.
>
> I would suspect #2.  Can you post sample data?  (to the list or to me
> directly).
> I'd like to see the concave hull paper you mention as well - I'm quite
> interested in an implementation of this.  Although as pointed out there is
> no single interpretation of how concave hull should be defined - so there
> could be several ways to compute something reasonable)
>
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel

[jts-devel] Re: concave hull ref

[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
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel

Re: [jts-devel] 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
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

Re: [jts-devel] 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
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

[jts-devel] Re: concave hull ref

[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
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel

Re: [jts-devel] basic questions

[Martin Davis]

#1: as others have replied, JTS operates purely on a Cartesian plane.  
It does not perform calculations in a spherical or spheroidal space.


#2: as mentioned by others, easiest way is to modify the underlying 
Coordinate of a Point geometry.  If you do this, you need to call 
geiometryChanged() to update the cached information in the Geometry (the 
Envelope at the moment).  Be aware that of course any references to this 
geometry will not be aware of this change, so you will have to update 
them as required (e.g. JTS indexes are not aware of changes to contained 
geometries).


Generally it's not encouraged to modify Geometry objects, since this can 
lead to nasty aliasing bugs, but it's not prevented for just this reason 
- in some cases it's more efficient to modify geometry objects in place.


roberto.cal...@gmail.com wrote:
I'm a beginner and have two questions I couldn't find the answer in 
documentation:


- Is it possible to define a projection system for my calculations? 
Example, I want to calculate the distance in km between two points 
that has coordinates in latitude/longitude degrees in a given 
projection system for Earth.


- I made a class that represents a moving object, so I used Coordinate 
implement its location (that changes all the time). I wanted to use 
Point, but Coordinate is the best class for dynamic info. So I'm 
instantiating a new Geometry everytime I need to perform calculation 
using this objects, is that right?


Thank you.


___
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

Re: [jts-devel] polygonizer and line strings

[Martin Davis]

Two possibilities:

1. bug in Polygonizer
2. your input is not fully noded.

I would suspect #2.  Can you post sample data?  (to the list or to me 
directly). 

I'd like to see the concave hull paper you mention as well - I'm quite 
interested in an implementation of this.  Although as pointed out there 
is no single interpretation of how concave hull should be defined - so 
there could be several ways to compute something reasonable)


As for a user guide to JTS, I realize this would be very nice to have.  
I'd very much like to provide something for this.  Unfortunately it's 
quite time-consuming to create, and it's been hard for me to find the 
time to put to it.  For the time being I try and keep enhancing the 
Javadoc whenever it looks like it could be improved.


Martin


Dragan Blagojevic wrote:

Hi,

I have question regarding proper use of Polygonizer class (I'm using NTS, but 
it shouldn't matter I hope)

I'm working on utility to create convex hull of a point set.

Result of first step of that utility is whole bunch of line strings 
representing convex hull or point set.

Then I'm using Polygonizer to transform list of line strings to polygon.

Problem is that sometime result of polygonizer is not one 'Big' outlining 
polygon (having potentially some holes in it), but instead lot of small 
polygons.

I suspect that problem is when some line segments lie on the boundary and as 
well form smaller hole in polygon that somehow create probelm.

It's a bit difficult to describe, but I'll try to simplify it as much as 
possible.

Imagine chess board (8x8 square) having line segments of lenght 1 all arround. 
If it happens that there are line segments arroung some of little squares arround the edges (e.g. field C1) then instead or returning big polygon (8x8) polygonizer return only small one (1x1 C1 square).


My guess is that line segment on the edge get assigned to that small polygon, 
and then rest of the line segments do not form closed ring.

That is of course totaly different of what I need, as I want to get back 
largest possible polygon, potentially discarding all those smaller but it seem 
that they take precedence and mess up desired output.

Is there any way to control how polygonizer work so that i get my big polygon 
back.


Thanks
Dragan Blagojevic


  


--
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

Re: [jts-devel] 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 > 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
jts-devel@lists.jump-project.org

http://lists.refractions.net/mailman/listinfo/jts-devel

___
jts-devel mailing list
jts-devel@lists.jump-project.org

http://lists.refractions.net/mailman/listinfo/jts-devel




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


___
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

Re: [jts-devel] 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 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
>> jts-devel@lists.jump-project.org
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>>  ___
> jts-devel mailing list
> jts-devel@lists.jump-project.org
> http://lists.refractions.net/mailman/listinfo/jts-devel
>



-- 
http://amusingprogrammer.blogspot.com/
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel

Re: [jts-devel] 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
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel


___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel

[jts-devel] 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
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel