CGAL users discussion list

[Andreas Fabri <>]

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