Right, I see the sorting step now. Out of curiosity, did you check to see if it was any faster using an array and Collections.sort, rather than a TreeSet? I would have thought building a tree was slower than doing a single sort of an array, followed by removing duplicates by traversing the array (perhaps by copying only unique points).
Interesting algorithm - that would be great to see a reference for this. So this isn't incremental insertion - the classic incremental insertion adds points randomly, locating their containing triangle, dividing it into 3 new triangles, and then restoring the Delaunay property by edge flipping. The location step is the potentially slow part. This sounds similar to the step you use for adding constraints. If you're adding Steiner points along constraint segments, then you have a Conformal Delaunay. A Constrained Delaunay contains the constraint edges exactly in the triangulation (and hence is not fully Delaunay). Shewchuck has a nice explanation: http://www.cs.cmu.edu/%7Equake/triangle.defs.html#conform Martin Michaël Michaud wrote: > Hi > >> I should have looked before I wrote - I just found the link you sent a >> while ago to your code (for others benefit - >> http://geo.michaelm.free.fr/OpenJUMP/resources/ ). >> >> So you are using Incremental insertion, with a Triangle- based data >> structure. It looks like your code handles Constrained Delaunay - or is >> it Conformal Delaunay? I'll have to look a bit more to see. >> >> > I'm not sure what incremental insertion is. > In my implementation, I sort points before starting the triangulation > (sorting points is included in my benchmark). > I think this makes a lot of optimisation possible (just have to walk > through the convex hull using triangle adjacency) > There is also an "incremental" part used for constrained Delaunay > triangulation as constraints are added to the > triangulation afterwards (I have no benchmark for this part yet, but it > should be much slower). > While adding constraints, Delaunay property is kept by adding points > along segments (steiner points ?). > Constrained triangulation is probably even slower due to new points > insertion. > If you try it, you must use 3d coordinates. > >> Anyway, very impressive timings. I'm curious to know where the speed >> different lies. It could be the point location search, or the data >> structure manipulation, or perhaps both? >> >> > I can try to find back a more precise description of the implementation. > > Michaël > >> Martin Davis wrote: >> >> >>> Interesting comparison, Michael. Is your code online somewhere? What >>> algorithm does it use, and what data structure for the triangulation? >>> >>> In the JTS API you don't have to create the triangles as a MultiPolygon >>> - that's just provided as a simple option for viewing them in the JTS >>> TestBuilder. In OJ I certainly wouldn't do that - I would split them >>> into one Feature per triangle. >>> >>> I figured that the JTS code was about O(n*sqrt(n)) as well - although >>> the theoretical performance of incremental insertion is actually >>> O(n^2)! But I think this is rarely seen in practice. >>> >>> Martin >>> >>> Michaël Michaud wrote: >>> >>> >>> >>>> 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 > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ------------------------------------------------------------------------------ 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
