wow.. those geeky talks ;) I would like to know much more about Comp Geom.
Can I actually ask how Michael derived the algorithmic complexity empirical? - because if I ever see these things, for instance by M van Kreveld or in some optimiziation books (e.g. Z Michalewicz and DB Fogel 2000)- I don't get how this is really done (and proven - but maybe I just need to read those books in detail). thank you guys - if you talk, I always can learn some things stefan Martin Davis schrieb: > 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? >>>>>>> >>>>>>> ------------------------------------------------------------------------------ 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
