CGAL users discussion list

[Camille Wormser <>]

Bernhard Kornberger a écrit :

I have reported a bug in the regular triangulation of CGAL 3.3 on
friday.

The original code works. But if one changes the Kernel to

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel K;

then the software crashes:

Shouldn't it also work with the exact kernel? What can I do?

Hi,
Christophe and I found the bug. The reason is that the insertion method first insert the point in the triangulation and then apply a regularize method by maintaining a list of incident faces still to be regularized (by potential flips). During the flips, the list was not properly updated, and some deleted faces stayed in the list.

The problem pops up only with the exact constructions kernel because it is the one which detects uninitialized data. The reason why one of the vertices of the deleted face is uninitialized (note that it is NOT the infinite vertex), and not some hidden vertex, is because of the way the 3-to-1 merge is performed: in order not to delete a degree 3 vertex v that should now be hidden, v is replaced by a temporary vertex w, which is deleted during the merge, along with two of the three faces L and R. Because of the bug, one of them (L or R) stayed in the list of faces still to be dealt with, and w is the (deleted) uninitialized vertex whose coordinates are accessed.

A better alternative would be to reimplement the regularize method by walking around the vertex (without an explicit incident faces list), but here is a fix. You just need to rewrite stack_flip_4_2 in Regular_triangulation_2.h in the following way (I attach the diff):

template < class Gt, class Tds >
void
Regular_triangulation_2<Gt,Tds>::
stack_flip_4_2(Face_handle f, int i, int j, Faces_around_stack & faces_around)
{
    int k = 3-(i+j);
    Face_handle g=f->neighbor(k);
    if (!faces_around.empty())
    {
      if (faces_around.front() == g)
      faces_around.pop_front();
      else if (faces_around.back() == g)
      faces_around.pop_back();
    }
   
    //union f with  g and f->neihgbor(i) with g->f->neihgbor(i)
    Face_handle fn = f->neighbor(i);
    //Face_handle gn = g->neighbor(g->index(f->vertex(i)));
    Vertex_handle vq = f->vertex(j);
   
    this->_tds.flip( f, i); //not using flip because the vertex j is flat.
    update_hidden_points_2_2(f,fn);
    Face_handle h1 = ( j==ccw(i) ? fn : f);    // simpler test (not important)
    //hide_vertex(h1, vq);
    hide_remove_degree_3(g,vq);
    if(j == ccw(i)) {                          // order of insertion should vary
      faces_around.push_front(h1);
      faces_around.push_front(g);
    }
    else {
      faces_around.push_front(g);
      faces_around.push_front(h1);
    }
}

--
Camille

Index: Regular_triangulation_2.h
===================================================================
--- Regular_triangulation_2.h   (révision 39246)
+++ Regular_triangulation_2.h   (copie de travail)
@@ -1882,11 +1882,17 @@
     
     this->_tds.flip( f, i); //not using flip because the vertex j is flat.
     update_hidden_points_2_2(f,fn);
-    Face_handle h1 = ( f->has_vertex(vq) ? fn : f);
+    Face_handle h1 = ( j == ccw(i) ? fn : f);
     //hide_vertex(h1, vq);
     hide_remove_degree_3(g,vq);
-    faces_around.push_front(g);
-    faces_around.push_front(h1);    
+    if(j == ccw(i)) {
+      faces_around.push_front(h1); 
+      faces_around.push_front(g);
+    }
+    else {
+      faces_around.push_front(g);
+      faces_around.push_front(h1); 
+    }
 }