CGAL users discussion list

[Monique Teillaud <>]

Damian Sheehy wrote:
> Hi Monique,
>
>                 Just to be clear about this. If I construct a CGAL 2D 
> Delaunay triangulation from a set of points that I insert in a fixed 
> order, the resulting triangulation will not be the same during 
> re-execution if the point set contains a degeneracy.

Hi Damian,

yes, it _will_ be the same.
Unless there is a problem somewhere, then please report...

Still, you should be careful that if you use the insertion from a range
        template < class InputIterator >
        int     dt.insert ( InputIterator first, InputIterator last)
then the order of insertion is modified to get some speedup.
Unless I am wrong (this is apparently not mentioned in the manual).
So, you might get a different result in case of degeneracies.

To be on the safe side regarding ordering, you can just use 
insert(point) in a loop.

        Monique Teillaud

> Degeneracy can be very common in the meshing of engineering components. 
> For example, in situations where the meshing algorithm starts by 
> generating an initial coarse mesh from “seeds” distributed on the 
> boundary of the object, and subsequently refining that mesh. In the 
> initial coarse meshing phase, two edges of equal seed density meeting at 
> a convex vertex, and obviously seeding distributions around circular 
> holes will give rise to degeneracy.
>
> Best regards,
>  
> Damian

> On Wed, Apr 15, 2009 at 10:00 AM, Monique Teillaud 
> < 
> <mailto:>> wrote:
>
>     Hi
>
>     In 2D the result may depend on the order in which your algorithm is
>     adding new points, in case of co-circular points.
>
>     But in any case CGAL triangulations stay deterministic and reproducible.
>     If you insert the same points in the same order, all runs will give
>     you the same Delaunay triangulation.
>
>     best
>            Monique Teillaud
>
>
>     Andreas Fabri wrote:
>
>
>         Hello,
>
>         If you develop an algorithm ON TOP OF CGAL, how can you expect
>         us to tell you
>         if your algorithm is deterministic. We don't know your code.
>
>         CGAL Delaunay triangulations as such may give you different results
>         when you have co-circular points, for example points on a grid.
>         The diagonals can be oriented differently, and this even in
>         every run.
>
>         andreas
>
>
>         panayiotis foteinos wrote:
>
>             Hello all.
>
>             I have implemented a Delaunay Refinement algorithm on CGAL.
>             All the decisions made in the algorithm are deterministic:
>             multiple runs on the same input PSLG should produce exactly
>             the same mesh.
>
>             I observed, however, that the output mesh is not the same
>             after each run. Fortunately, the ouput mesh is the "correct"
>             one after each run (I am sure about the correctness of the
>             refined output mesh), but different. For example, the
>             meshing of the PSLG for the first time yields 1500 faces,
>             while the second time yields 1510.
>
>             I am sorry I am asking you this but (after spending a lot of
>             time debugging) I have to be sure:
>                Is this behavior possible or there is a bug in my code?
>             Should I expect the        same answers from CGAL (with the
>             same input) when no exact constructions are used?
>
>             The number type I am using is double, while the predicates
>             are exact.
>
>             Thanks,
>             Panagiotis
>
>
>
>
>     -- 
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://lists-sop.inria.fr/wws/info/cgal-discuss