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
[email protected]
http://lists.refractions.net/mailman/listinfo/jts-devel
|
