How to get the vertex indices of the faces of a spherical Delaunay triangulation?

[stla]

Hello,

I spent a couple of hours on this problem. I'm doing a spherical Delaunay triangulation, and I want to get the faces given by the indices of their vertices. I can easily get the coordinates of the vertices, but not the indices.

Finally I use the following solution but I don't like it. I iterate over all faces, and for each face f I iterate over all vertices of the triangulation and I do f->has_vertex(*v) for each vertex v. This works but isn't there a better solution? I didn't find something similar to the triangulation_vertex_with_info for spherical triangulations, which would allow to attach an index in v->info() and then to easily and efficiently get the vertex indices per face.

int sdelaunay() {
  std::vector<Point3> points;
  points.emplace_back( 3,  1,  1);
  points.emplace_back(-8,  1,  1);
  points.emplace_back( 1,  2,  1);
  points.emplace_back( 1, -2,  1);
  points.emplace_back( 1,  1, 10);
  Traits traits(Point3(1,1,1)); // radius is 1 by default
  DToS2 dtos(traits);
  Traits::Construct_point_on_sphere_2 cst = traits.construct_point_on_sphere_2_object();
  for(const auto& pt : points) {
    dtos.insert(cst(pt));
  }
  std::cout << "The triangulation has dimension: " << dtos.dimension() << " and\n";
  std::cout << dtos.number_of_vertices() << " vertices" << std::endl;
  std::cout << dtos.number_of_edges() << " edges" << std::endl;
  std::cout << dtos.number_of_faces() << " faces" << std::endl;
  std::cout << dtos.number_of_ghost_faces() << " ghost faces" << std::endl;

  DToS2::Vertex_handles vhs = dtos.vertex_handles();

  DToS2::All_faces_iterator itbegin = dtos.all_faces_begin();
  DToS2::All_faces_iterator itend = dtos.all_faces_end();

  int faceIndex = 0;
  for(auto f = itbegin; f != itend; f++) {
    std::cout << "\n--------------\n" << std::endl;
    std::cout << "Dealing with face " << faceIndex++ << std::endl;
    std::cout << "This face is ghost: " << f->is_ghost() << std::endl;
    std::cout << "Vertex indices of this face:" << std::endl;
    int i = 0;
    int count = 0;
    for(auto v = vhs.begin(); v != vhs.end(); v++) {
      if(f->has_vertex(*v)) {
        std::cout << i << std::endl;
        if(count++ == 3) {
          break;
        }
      }
      i++;
    }
  }

  return 1;
}

[MaelRL]

The Triangulation_vertex/face_base_with_info_2 are compatible with the spherical triangulations; just include it in the stack as you would for an Euclidean Delaunay triangulation:

(roughly:)
using K = ...;
using Traits = Projection_on_sphere_traits_3<K>;
using Vbb = Triangulation_vertex_with_info_2<...>;
using Vb =  Triangulation_on_sphere_vertex_base_2<Traits, Vbb>;
using Fb = Triangulation_on_face_vertex_base_2<Traits>;
using Tds = Triangulation_data_structure_2<Vb, Fb>;
using DToS = Delaunay_triangulation_on_sphere_2<Traits, Tds>;

[stla]

Thanks! Wonderful.

[afabri]

Note that there is also an example in the User Manual.

[stla]

I have:

typedef CGAL::Exact_predicates_inexact_constructions_kernel       K;
typedef CGAL::Projection_on_sphere_traits_3<K>                    Traits;
typedef Traits::Point_3                                           SPoint3;
typedef CGAL::Triangulation_vertex_base_with_info_2<int, K>       Vbi2;
typedef CGAL::Triangulation_on_sphere_vertex_base_2<Traits, Vbi2> Vb;
typedef CGAL::Triangulation_on_sphere_face_base_2<Traits>         Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb>              Tds;
typedef CGAL::Delaunay_triangulation_on_sphere_2<Traits, Tds>     DToS;

But some assertions fail in Delaunay_triangulation_on_sphere_2.h when I try to insert the points: dtos.insert(std::make_pair(p, i));. The pair is not accepted.

[MaelRL]

There is no "zipping" support in DToS2 currently. There's nothing prevent it, it's just work that was not done.

[stla]

I've found!!!

      DToS::Vertex_handle v = dtos.insert(p);
      int& j = v->info();
      j = i;