Question on use cases of JTS trianguation API

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

Question on use cases of JTS trianguation API

Martin Davis
To those that are interested in the upcoming JTS triangulation API, a
question:

What type of input and output structures would you find useful?

Currently I'm developing the following:

INPUT:
- Geometry (from which the site/vertex coordinates are extracted)
- Collection of Coordinates

OUTPUT:
- MultiLineString containing triangulation edges
- GeometryCollection of Polygons containing triangles

You can also work directly with the internal datastructures of the
triangulation (Vertices, QuadEdges, etc), but this requires a higher
level of understanding.

Is there any other option I haven't though of?

--
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: [JPP-Devel] Question on use cases of JTS trianguation API

michaelm-2
Hi Martin,

You may already know the benchmark done by Erwan's team with some java
implementations
(http://conference.osgeo.org/index.php/foss4g/2008/paper/view/282/177)
It eventually shows the triangulator I have written a few years ago
(available on http://geo.michaelm.free.fr/OpenJUMP/resources/) is very
fast (I have to add it is not 100% robust as it sometimes fails for
large datasets  - more than 100k points)
They also wrote a more recent paper about their new implementation for
orbisgis :
http://hal.archives-ouvertes.fr/docs/00/32/95/03/PDF/CDT-paper.pdf

Now about your question :

INPUT
- should be able to input ponctual (sites) , lineal (breaklines),
polygonal geometries (points and breaklines to be extracted)
- collection of coordinates

INPUT/OUTPUT
- in my plugin, I decided that when the input was a single polygon, the
output should be a triangulation containing only triangles inside the
polygon (not all triangles inside the convex hull)
 (may not concern the low level api)

OUTPUT
- in my Triangulation class, I decided to return a simple Coordinate[]
array containing n*3 objects (elements 0, 1 and 2 composing the first
triangle...)
  I'm not that sure, but I think this structure just contained
references to input coordinates (memory-friendly)
- i would prefer a collection of Linestrings or a collection of Polygons
than a MultiLinestring or MultiPolygon, because I'm not sure a
mutigeometry of one million elements is easy to deal with (spatial
indexation inefficient for example). Moreover, individual geometries can
give the oppurtunity to keep the tin structure with links between
elements represented as attributes, or to compute height, slope,
orientation on every individual triangle and keep them as attributes. I
understand why a Tin structure is interesting (no duplicate), but not a
multi-geometry.

My 2 cents

Michaël


Martin Davis a écrit :

> To those that are interested in the upcoming JTS triangulation API, a
> question:
>
> What type of input and output structures would you find useful?
>
> Currently I'm developing the following:
>
> INPUT:
> - Geometry (from which the site/vertex coordinates are extracted)
> - Collection of Coordinates
>
> OUTPUT:
> - MultiLineString containing triangulation edges
> - GeometryCollection of Polygons containing triangles
>
> You can also work directly with the internal datastructures of the
> triangulation (Vertices, QuadEdges, etc), but this requires a higher
> level of understanding.
>
> Is there any other option I haven't though of?
>
>  

_______________________________________________
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: [JPP-Devel] Question on use cases of JTS trianguation API

Thomas Leduc
2009/4/29 Michaël Michaud <[hidden email]>
Hi Martin,

You may already know the benchmark done by Erwan's team with some java implementations (http://conference.osgeo.org/index.php/foss4g/2008/paper/view/282/177)
It eventually shows the triangulator I have written a few years ago (available on http://geo.michaelm.free.fr/OpenJUMP/resources/) is very fast (I have to add it is not 100% robust as it sometimes fails for large datasets  - more than 100k points)
They also wrote a more recent paper about their new implementation for orbisgis : http://hal.archives-ouvertes.fr/docs/00/32/95/03/PDF/CDT-paper.pdf

good evening,
Indeed, in 2008, several (C)DT implementations (including famous "Triangle" implementation) have been coupled with OrbisGIS so as to compare performances. It seems the one of Michaël (thanks to him for his useful help) was the fastest one. I've also tried to "enhance" his own implementation adding a sweepline and a (not fully debug yet - job was postponed) soft breakline insertion method. All those dev will be published asap.

--
Thomas LEDUC

_______________________________________________
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: [JPP-Devel] Question on use cases of JTS trianguation API

Thomas Leduc
In reply to this post by michaelm-2
2009/4/29 Michaël Michaud <[hidden email]>
Hi Martin,

You may already know the benchmark done by Erwan's team with some java implementations (http://conference.osgeo.org/index.php/foss4g/2008/paper/view/282/177)
It eventually shows the triangulator I have written a few years ago (available on http://geo.michaelm.free.fr/OpenJUMP/resources/) is very fast (I have to add it is not 100% robust as it sometimes fails for large datasets  - more than 100k points)
They also wrote a more recent paper about their new implementation for orbisgis : http://hal.archives-ouvertes.fr/docs/00/32/95/03/PDF/CDT-paper.pdf


good morning,
Indeed, in 2008, several (C)DT implementations (including famous "Triangle" one) have been coupled with OrbisGIS so as to compare performances. It seems the one of Michaël (thanks to him for his useful help) was the fastest one. I've also tried to "enhance" his own implementation adding a sweepline and a (not fully debug yet - job was postponed) soft breakline insertion method. All those dev will be published asap.

--

--
Thomas LEDUC

_______________________________________________
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: Question on use cases of JTS trianguation API

mbedward
In reply to this post by Martin Davis
2009/4/30 Martin Davis <[hidden email]>:
> INPUT:
> - Geometry (from which the site/vertex coordinates are extracted)
> - Collection of Coordinates
>
> OUTPUT:
> - MultiLineString containing triangulation edges
> - GeometryCollection of Polygons containing triangles
>

One of my common needs is to navigate between neighbouring points,
akin to a (highly) constrained random walk. To do this with the above
outputs I guess I would build data structure(s) that related input
coords to output triangles, allowing forward and reverse lookup.  If
such a thing is generally useful it would be nice to have it as an
output, possibly optional.  Unless, of course, there is already an
easier and more elegant way of accomplishing this.

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: Question on use cases of JTS trianguation API

Martin Davis
Michael,

The triangulation code uses a Quad-Edge Subdivision as its underlying
structure.  This is a topological structure which directly supports the
kind of navigation that you require.  It's a wee bit tricky to
understand, however.

Alternatively, you could load the generated edges into a PlanarGraph and
traverse them that way.  That might have an easier API to use.  If you
end up doing this, consider contributing the code back into JTS - it
might be generally useful.

Martin

Michael Bedward wrote:

> 2009/4/30 Martin Davis <[hidden email]>:
>  
>> INPUT:
>> - Geometry (from which the site/vertex coordinates are extracted)
>> - Collection of Coordinates
>>
>> OUTPUT:
>> - MultiLineString containing triangulation edges
>> - GeometryCollection of Polygons containing triangles
>>
>>    
>
> One of my common needs is to navigate between neighbouring points,
> akin to a (highly) constrained random walk. To do this with the above
> outputs I guess I would build data structure(s) that related input
> coords to output triangles, allowing forward and reverse lookup.  If
> such a thing is generally useful it would be nice to have it as an
> output, possibly optional.  Unless, of course, there is already an
> easier and more elegant way of accomplishing this.
>
> Michael
> _______________________________________________
> 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: Question on use cases of JTS trianguation API

mbedward
That sounds very good - many thanks Martin.

I'll experiment and happily contribute anything useful that results.

Michael

2009/5/5 Martin Davis <[hidden email]>:

> Michael,
>
> The triangulation code uses a Quad-Edge Subdivision as its underlying
> structure.  This is a topological structure which directly supports the kind
> of navigation that you require.  It's a wee bit tricky to understand,
> however.
>
> Alternatively, you could load the generated edges into a PlanarGraph and
> traverse them that way.  That might have an easier API to use.  If you end
> up doing this, consider contributing the code back into JTS - it might be
> generally useful.
>
> Martin
_______________________________________________
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: [JPP-Devel] Question on use cases of JTS trianguation API

michaelm-2
In reply to this post by michaelm-2
Hi Martin,

Today, I compared the new JTS triangulation api with the triangulation plugin I wrote some years ago.
In my tests, I just compared speed for triangulation of a random set of points (no constraint, no real data).
Measures include initialization, triangulation, and feature(s) creation.

Both libraries worked well. I did not check result correctness.
Processing time was faster with my code (and ratio between two consecutive figures are always better).
Of course, triangulation speed is only one thing and may not be the most important. Just want to show that there is still room for improvement.
 
In OpenJUMP, memory usage was better with JTS api than with my plugin (1560Mb vs 2033Mb).
I suppose this is partly due to the number of features created (about 1M features in my case, only one feature in your case).
On the other hand, as I told you  before, playing with a MultiPolygon composed of 1M triangles is not easy.
In OJ, with a MultiPolygon of 1M triangles, the user interface do not respond anymore and I could not explode the MultiPolygon (if I had to implement a plugin, I would probably make it possible to explode it before it is displayed).

I did not look at your implementation, but I tried to find its complexity in an empiric way. I found that your algo has about a n*sqrt(n) complexity, but this deduction may be due to measurement errors :
MM : n*log(n)*2.4E-6
MD : n*sqrt(n)*0.1E-6

Even if it is not yet the fastest, I have no doubt JTS triangulation api will soon be a reference in the java world.
Thank you to share your excellent work.

Michaël

Figures (times in sec for sets from 50 000 to 1 000 000 points)





 


Michaël Michaud a écrit :
Hi Martin,

You may already know the benchmark done by Erwan's team with some java implementations (http://conference.osgeo.org/index.php/foss4g/2008/paper/view/282/177)
It eventually shows the triangulator I have written a few years ago (available on http://geo.michaelm.free.fr/OpenJUMP/resources/) is very fast (I have to add it is not 100% robust as it sometimes fails for large datasets  - more than 100k points)
They also wrote a more recent paper about their new implementation for orbisgis : http://hal.archives-ouvertes.fr/docs/00/32/95/03/PDF/CDT-paper.pdf

Now about your question :

INPUT
- should be able to input ponctual (sites) , lineal (breaklines), polygonal geometries (points and breaklines to be extracted)
- collection of coordinates

INPUT/OUTPUT
- in my plugin, I decided that when the input was a single polygon, the output should be a triangulation containing only triangles inside the polygon (not all triangles inside the convex hull)
(may not concern the low level api)

OUTPUT
- in my Triangulation class, I decided to return a simple Coordinate[] array containing n*3 objects (elements 0, 1 and 2 composing the first triangle...)
 I'm not that sure, but I think this structure just contained references to input coordinates (memory-friendly)
- i would prefer a collection of Linestrings or a collection of Polygons than a MultiLinestring or MultiPolygon, because I'm not sure a mutigeometry of one million elements is easy to deal with (spatial indexation inefficient for example). Moreover, individual geometries can give the oppurtunity to keep the tin structure with links between elements represented as attributes, or to compute height, slope, orientation on every individual triangle and keep them as attributes. I understand why a Tin structure is interesting (no duplicate), but not a multi-geometry.

My 2 cents

Michaël


Martin Davis a écrit :
To those that are interested in the upcoming JTS triangulation API, a question:

What type of input and output structures would you find useful?

Currently I'm developing the following:

INPUT:
- Geometry (from which the site/vertex coordinates are extracted)
- Collection of Coordinates

OUTPUT:
- MultiLineString containing triangulation edges
- GeometryCollection of Polygons containing triangles

You can also work directly with the internal datastructures of the triangulation (Vertices, QuadEdges, etc), but this requires a higher level of understanding.

Is there any other option I haven't though of?

 

_______________________________________________
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
Loading...