Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Getting different results...

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Getting different results...


Chronological Thread 
  • From: Andreas Fabri <>
  • To:
  • Subject: Re: [cgal-discuss] Getting different results...
  • Date: Thu, 16 Apr 2009 09:16:41 +0200

Damian Sheehy wrote:
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?

Hi Damian,

Well, geometrically speaking you have two times the same triangulation.
The different order of iterators on the finite faces may come from the
fact that the insert(Point) method first does a locate(Point). If the
located point lies on an Edge, you might get the (fh,i) or (fh->neighbor(i),
fh->neighbor(i)->index(fh))
because the locate method performs a random walk towards the point.
The order of the two new trianges will be different for the two outcomes
of the locate method.

Best regards,

andreas




Best regards,

Damian



On Wed, Apr 15, 2009 at 12:16 PM, Monique Teillaud < <mailto:>> 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:>

<mailto:

<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



------------------------------------------------------------------------


------------------------------------------------------------------------





Archive powered by MHonArc 2.6.16.

Top of Page