Apollonius crashes because of Vertex_handle

[stla]

Hello,

I have some sites and some radii for which the following code crashes the session:

  ApolloniusGraph ag;
  for(int i = 0; i < nsites; i++) {
    Point2 p(sites(i, 0), sites(i, 1));
    Site2 s(p, radii(i));
    ApolloniusGraph::Vertex_handle v = ag.insert(s);
    v->info() = i + 1;
  }

But if I do ag.insert(s) only, not do

    ApolloniusGraph::Vertex_handle v = ag.insert(s);
    v->info() = i + 1;

then it works.

If I change the radii, it works too (and use Vertex_handle), it works too: it crashes for particular radii.

There's no error message, no "segfault" or thing like that, just the R session closes brutally.

Gonna prepare a minimal example and try gdb.

[stla]

Here is the minimal example:

#define CGAL_EIGEN3_ENABLED 1
#include <CGAL/Apollonius_graph_2.h>
#include <CGAL/Apollonius_graph_traits_2.h>
#include <CGAL/Apollonius_graph_vertex_base_2.h>
#include <CGAL/Apollonius_site_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_face_base_with_info_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel       K;
typedef K::Point_2                                                Point2;
typedef CGAL::Apollonius_graph_traits_2<K>                        Traits;
typedef CGAL::Triangulation_vertex_base_with_info_2<int, K>       Vbi2;
typedef CGAL::Apollonius_graph_vertex_base_2<Traits, false, Vbi2>  Vb;
typedef CGAL::Triangulation_face_base_with_info_2<int, K>         Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb>              Tds;
typedef CGAL::Apollonius_graph_2<Traits, Tds>                     ApolloniusGraph;
typedef ApolloniusGraph::Site_2                                   Site2;
typedef Traits::Line_2                                            Line2;
typedef Traits::Object_2                                          Object2;
typedef ApolloniusGraph::Triangulation_data_structure             Tds;
typedef Tds::Face_handle                                          Face_handle;

// [[Rcpp::export]]
int crash() {

  Point2 p1(-1, -1);
  Point2 p2(-1, 1);
  Point2 p3(1, 1);
  Point2 p4(1, -1);
  Point2 p5(0, 0);

  Site2 s1(p1, 2);
  Site2 s2(p2, 2);
  Site2 s3(p3, 2);
  Site2 s4(p4, 2);
  Site2 s5(p5, 2);

  // make Apollonius graph
  ApolloniusGraph ag;
  ApolloniusGraph::Vertex_handle v1 = ag.insert(s1);
  ApolloniusGraph::Vertex_handle v2 = ag.insert(s2);
  ApolloniusGraph::Vertex_handle v3 = ag.insert(s3);
  ApolloniusGraph::Vertex_handle v4 = ag.insert(s4);
  ApolloniusGraph::Vertex_handle v5 = ag.insert(s5);
  for(int i = 1; i <= 12; i++) {
    double a = 2.0 * M_PI * i / 12.0;
    Point2 pt(2 * cos(a), 2 * sin(a));
    Site2  st(pt, 1);
    ApolloniusGraph::Vertex_handle v = ag.insert(st);
    v->info() = i + 1;
  }
  // validate the Apollonius graph
  assert(ag.is_valid(true, 1));

  return 0;
}

If you change the first five radii from 2 to 1.5, there's no crash:

  Site2 s1(p1, 1.5);
  Site2 s2(p2, 1.5);
  Site2 s3(p3, 1.5);
  Site2 s4(p4, 1.5);
  Site2 s5(p5, 1.5);

[stla]

Here are the graphs for radius = 1, 1.2, 1.4, 1.6. For 1.8, crash.

[stla]

The same graphs but showing the circles in addition:

[stla]

Sh**. My Linux laptop is broken and I'm using the Windows laptop of my work. I don't have gdb and not sure I can install it without admin rights.

[stla]

I installed gdb with pacman 👍

But it only returns:

OK -1
[Thread 15724.0x117c exited with code 3221225477]
[Thread 15724.0x472c exited with code 3221225477]

Program terminated with signal SIGTRAP, Trace/breakpoint trap.
The program no longer exists.

[stla]

I have a guess. Here are the circles for radius=2:

There are tangent circles. I didn't carefully read the doc yet, but I have seen that there can be a vertex conflict when there are tangent circles, and a vertex is destroyed when there is such a conflict. So maybe one cannot assign a Vertex_handle to the output of ag.insert(site) when the vertex is destroyed. I recall that if I don't assign the output to a Vertex_handle, there's no crash.

[stla]

That's correct! I modified my code to:

  // make the Apollonius graph
  ApolloniusGraph ag;
  for(int i = 0; i < nsites; i++) {
    Point2 p(sites(i, 0), sites(i, 1));
    Site2 s(p, radii(i));
    ag.insert(s);
  }

  Rcpp::Rcout << "number of vertices: " << ag.number_of_vertices() << "\n"; // this prints 9

  int nvertices = 0;
  for(auto v = ag.all_vertices_begin(); v != ag.all_vertices_end(); v++) {
    ApolloniusGraph::Vertex_handle vh(v);
    vh->info() = nvertices + 1;
    nvertices++;
  }

  Rcpp::Rcout << "number of vertices: " << nvertices << "\n"; // this prints 10

  // validate the Apollonius graph
  if(!ag.is_valid(true, 1)) { // this returns "AGDS is ok... Apollonius diagram is NOT valid"
    Rcpp::stop("The Apollonius graph is not valid."); // this is then executed and the program is stopped
  }

Should I really stop the program when the graph is not valid? Or can we get something from an invalid graph?

[stla]

I checked with Valgrind now. It returns an error message:

 *** caught segfault ***
address 0x18, cause 'memory not mapped'

But no problem, everything is OK with my modified code.

Maybe you should warn the user in the doc about this issue?