Edges of CGAL hyperbolic Delaunay triangulation

Question

I'm trying to do a hyperbolic Delaunay triangulation with CGAL. Below is my code. Rcpp is a library to use C++ with R.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Hyperbolic_Delaunay_triangulation_2.h>
#include <CGAL/Hyperbolic_Delaunay_triangulation_traits_2.h>
#include <CGAL/Triangulation_vertex_base_with_id_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Hyperbolic_Delaunay_triangulation_traits_2<K> HDtt;
typedef HDtt::Point_2 HPoint;
typedef CGAL::Triangulation_data_structure_2<
  CGAL::Triangulation_vertex_base_with_id_2<HDtt>,
  CGAL::Hyperbolic_triangulation_face_base_2<HDtt>>
HTds;
typedef CGAL::Hyperbolic_Delaunay_triangulation_2<HDtt, HTds> HDt;

Rcpp::IntegerMatrix htest(const Rcpp::NumericMatrix points) {
  std::vector<HPoint> hpts;
  const unsigned npoints = points.ncol();
  hpts.reserve(npoints);
  for(unsigned i = 0; i != npoints; i++) {
    const Rcpp::NumericVector pt = points(Rcpp::_, i);
    hpts.emplace_back(HPoint(pt(0), pt(1)));
  }
  HDt hdt;
  hdt.insert(hpts.begin(), hpts.end());
  const size_t nedges = hdt.number_of_hyperbolic_edges();
  Rcpp::IntegerMatrix Edges(2, nedges);
  size_t i = 0;
  for(HDt::All_edges_iterator ed = hdt.all_edges_begin();
      ed != hdt.all_edges_end(); ++ed) {
    Rcpp::IntegerVector edge_i(2);
    HDt::Vertex_handle sVertex = ed->first->vertex(HDt::cw(ed->second));
    edge_i(0) = sVertex->id();
    HDt::Vertex_handle tVertex = ed->first->vertex(HDt::ccw(ed->second));
    edge_i(1) = tVertex->id();
    Edges(Rcpp::_, i) = edge_i;
    i++;
  }
  return Edges;
}

I feed this function with some points in the unit circle. Then it returns an integer matrix, which is supposed to be the edges, but all entries of the matrix I get are equal to a huge integer instead. I also tried std::cout << sVertex->id() and this prints this huge integer.

Answer 1

There are isolated edges because the authors choose to filter out triangles whose circumscribing circle is "not compact" (i.e., it is not included in the Poincaré disk).

See the user manual https://doc.cgal.org/latest/Hyperbolic_triangulation_2/index.html#HT2_Euclidean_and_hyperbolic_Delaunay_triangulations " A Euclidean Delaunay face is hyperbolic if its circumscribing circle is contained in ?2. "

For more details: https://jocg.org/index.php/jocg/article/view/2926

Answer 2

Ok, I found a way. One has to set the ids, they were unset and that's why I got a huge integer. Also one has to take the vertices of the triangulation, because while these are the same as the input vertices, they are in another order.

  ......
  HDt hdt;
  hdt.insert(hpts.begin(), hpts.end());
  Rcpp::NumericMatrix Vertices(2, npoints);
  int index = 0;
  for(HDt::All_vertices_iterator vd = hdt.all_vertices_begin();
      vd != hdt.all_vertices_end(); ++vd){
    vd->id() = index;
    HPoint pt = vd->point();
    Vertices(0, index) = pt.x();
    Vertices(1, index) = pt.y();
    index++;
  }
  ......

However I don't know why there is an isolated edge: