Delaunay_triangulation (d dimensions) crashes on simple instance

[michaelkerber]

Issue Details

In the program below, when I add two points, remove one of them and add another, the program crashes:

terminate called after throwing an instance of 'CGAL::Precondition_exception'
what(): CGAL ERROR: precondition violation!
Expr: s1 != Full_cell_handle()
File: /home/kerber/software/CGAL-5.6.1/include/CGAL/Triangulation_data_structure.h
Line: 506
Aborted (core dumped)

This happens both with Epeck/Epick and with Dimension_tag<2>/Dynamic_dimension_tag. It does work for Delaunay_triangulation_2.

Source Code

#include <iostream>

#include <CGAL/Epick_d.h>
#include <CGAL/Epeck_d.h>
#include <CGAL/Delaunay_triangulation.h>

typedef CGAL::Dynamic_dimension_tag Dim_tag;
//typedef CGAL::Dimension_tag<2> Dim_tag;

typedef CGAL::Epick_d< Dim_tag >  Kernel;
typedef CGAL::Delaunay_triangulation<Kernel> Triangulation;

typedef typename Triangulation::Vertex_handle Vertex_handle;
typedef typename Triangulation::Point Point;

Point create_point(double x,double y) {
    std::vector<double> c;
    c.push_back(x);
    c.push_back(y);
    return Point(2,c.begin(),c.end());
}

int main() {

    Triangulation T(2);
    
    Point p1=create_point(2, 3);
    Point p2=create_point(6, 3);
    Point p3=create_point(0, 4);
    
    Vertex_handle vh1=T.insert(p1);
    Vertex_handle vh2=T.insert(p2);
    T.remove(vh1);
    
    Vertex_handle vh3=T.insert(p3);
    
    std::cout << "Exit normally" << std::endl;

    return 0;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Debian Linux
• Compiler: gcc 12.2.0
• Release or debug mode: Debug
• Specific flags used (if any): none
• CGAL version: 5.6.1
• Boost version: 1.74.0.3
• Other libraries versions if used (Eigen, TBB, etc.): Eigen 3.4.0-4

[mglisse]

I can confirm the assertion failure. My current understanding (could be completely off) is that after remove, the full cells have only 1 vertex, but we leave an old Vertex_handle as second vertex (from when the cell was actually of dimension 1), which should be harmless since in dimension 0 we should only look at one vertex. However, insert (do_insert_increase_dimension in particular) looks at S->vertex(cur_dim) where cur_dim has already been increased to 1, i.e. it looks at this second vertex.

TODO: understand why insert does that exactly, and determine whether we can avoid it or we need to clean up the vertex arrays.

[mglisse]

cgal/Triangulation/include/CGAL/Triangulation_data_structure.h

Lines 830 to 833 in 847df9a

	inf1->set_vertex(1, Vertex_handle());
	inf1->set_vertex(1, Vertex_handle());
	inf2->set_neighbor(1, Full_cell_handle());
	inf2->set_neighbor(1, Full_cell_handle());

this looks like a copy-pasto, we do twice the same operation, instead of doing both operations for inf1 and inf2.

[michaelkerber]

Hi Marc, thanks for looking into this. I just tried, and I can confirm that with the obvious fix in Triangulation_data_structure.h, my little test program runs through, and also in my bigger program (where I do inserts and deletes all the time) everything seems fine, also in dimensions 3 and 4.