CGAL users discussion list

[Damian Sheehy <>]

Hi Monique,

Thanks for following through on this, I am keen to get to the bottom of the problem. Firstly, I am using the dt.insert(point) interface to avoid the internal shuffle. Also, I have observed the problem in both 2D and 3D triangulations.

I just performed a quick test and I have found that the triangulations appear to be equivalent in the presence of degeneracies, i.e based on visual inspection the triangulations look the same. However, the order of the triangles returned from the Finite_faces_iterator is likely to be different. I attached indices to the triangulation via vertex and face info and I have included screen shots that show the difference (See p1.jpg and p2.jpg). Notice that triangle pairs {T7, T12} and {T23, T28} have flipped. Is this the expected behaviour?


Best regards,

Damian

On Wed, Apr 15, 2009 at 12:16 PM, Monique Teillaud <> wrote:

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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Attachment: p1.jpg
Description: JPEG image

Attachment: p2.jpg
Description: JPEG image