Thanks for the analysis Michael. SS
2009/5/17 Michaël Michaud <michael.mich...@free.fr>: > 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 > jts-de...@lists.jump-project.org > http://lists.refractions.net/mailman/listinfo/jts-devel > > > > > ------------------------------------------------------------------------------ > Crystal Reports - New Free Runtime and 30 Day Trial > Check out the new simplified licensing option that enables > unlimited royalty-free distribution of the report engine > for externally facing server and web deployment. > http://p.sf.net/sfu/businessobjects > _______________________________________________ > Jump-pilot-devel mailing list > Jump-pilot-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > ------------------------------------------------------------------------------ Crystal Reports - New Free Runtime and 30 Day Trial Check out the new simplified licensing option that enables unlimited royalty-free distribution of the report engine for externally facing server and web deployment. http://p.sf.net/sfu/businessobjects _______________________________________________ Jump-pilot-devel mailing list Jump-pilot-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
