Normally in academic papers/textbooks the algorithmic complexity is derived symbolically, based on the characteristics and data structures used in the algorithm. It's always seems like a bit of a black art to me - the proofs are often much more complicated than the algorithm (which may itself be complicated!)
I usually do exactly what Michael has done, and guesstimate it from a set of timings. But note that this provides an estimate of the complexity in the average case - the worst-case complexity (the big-O expression) is often much worse (eg for the Delaunay incremental insertion algorithm it's O(n^2) - but this is rarely or never seen in practice). Stefan Steiniger wrote: > 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 > > -- 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
