Triangulation_3: bug in Triangulation_segment_cell_iterator_3 in 2D

[lrineau]

Issue Details

With a 2D triangulation, the class Triangulation_segment_cell_iterator_3 does not work, and crashes.

Source Code

See the full code at https://gist.github.com/lrineau/d2002ee2044502a8200ad49de6dc7058. Extract:

int main()
{
  std::cerr.precision(17);
  std::cout.precision(17);

  Tr tr;
  std::istringstream iss(triangulation_content);
  iss >> tr;
  assert(tr.is_valid());
  std::cerr << "dimension: " << tr.dimension() << std::endl;
  std::cerr << "number of vertices: " << tr.number_of_vertices() << std::endl;
  std::cerr << "number of facets: " << tr.number_of_facets() << std::endl;
  std::cerr << "number of cells: " << tr.number_of_cells() << std::endl;
  dump_triangulation(tr);
  dump_segment(segment[0], segment[1]);
  Tr::Vertex_handle va, vb;
  const bool va_ok = tr.is_vertex(segment[0], va);
  const bool vb_ok = tr.is_vertex(segment[1], vb);
  assert(va_ok && vb_ok);
  auto it = tr.segment_traverser_cells_begin(va, vb);
  const auto end = tr.segment_traverser_cells_end();
  for (int i = 0; it != end; ++it, ++i) {
    std::cerr << "current cell: " << it->vertex(0)->point() << " "
              << it->vertex(1)->point() << " " << it->vertex(2)->point()
              << '\n';
    dump_triangle(it->vertex(0)->point(), it->vertex(1)->point(),
                  it->vertex(2)->point(), i);
  }
}

There is a self-contained .cpp file, and CMakeLists.txt file. The .cpp loads a pre-existing 2D Triangulation_3<Epick> object, that is valid.

There is also a .js file to load with the CGAL 3D demo, to load that scene:

The black lines are a triangulation in the plane z==0, and the red line is the query segment for Triangulation_segment_cell_iterator_3.

In the following picture, the visited cells, are: [1, 2, 3, 4] and then a crash:

CGAL error: assertion violation!
Expression : oxz_pqr != COLLINEAR
File       : /home/lrineau/Git/cgal/Cartesian_kernel/include/CGAL/predicates/kernel_ftC3.h
Line       : 190
Explanation: 
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: oxz_pqr != COLLINEAR
File: /home/lrineau/Git/cgal/Cartesian_kernel/include/CGAL/predicates/kernel_ftC3.h
Line: 190

But the correct cell sequence should be [2, 3, 5, 6].

The problem seems in void Triangulation_segment_cell_iterator_3<Tr,Inc>::walk_to_next_2().

[lrineau]

Note: I encountered that issue while working on CDT_3. My data set was not 2D, but as the triangulation is built incrementally, segment by segment, if the the first loaded segments are in the xy-plane, I have that issue. That is not a blocker bug.

[lrineau]

As for the gist, the easiest is to clone it locally:

git clone https://gist.github.com/d2002ee2044502a8200ad49de6dc7058.git

I tried it with CGAL-5.5.x and master.