CGAL users discussion list

[Damian Sheehy <>]

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.

 

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 <> 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