CGAL: Delaunay triangulation vs triangulation in CGAL's example

Question

In my work, I need to obtain first shell of Voronoi neighbors for a focal particle. For this I use Delaunay triangulation which is the dual graph of Voronoi tessellation. The Version of CGAL which I use is 4.7. I always used the basic code in CGAL manual_4.7 as a template to create Delaunay triangulation. My problem is with the headers and typedefs in that example, because I recently discovered they are different from CGAL 4.14 which is the latest version available. In CGAL 4.7:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_2.h>
#include <CGAL/Periodic_2_triangulation_traits_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Periodic_2_triangulation_traits_2<K>                  Gt;
typedef CGAL::Triangulation_vertex_base_with_info_2<unsigned, Gt>   Vb;
typedef CGAL::Periodic_2_triangulation_face_base_2<Gt>              Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb>                 Tds;
typedef CGAL::Periodic_2_Delaunay_triangulation_2<Gt, Tds>          Delaunay;
typedef Delaunay::Point                                             Point;

and in CGAL 4.14:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_2.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_traits_2.h>
#include <CGAL/Periodic_2_triangulation_face_base_2.h>
#include <CGAL/Periodic_2_triangulation_vertex_base_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <iostream>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel             K;
typedef CGAL::Periodic_2_Delaunay_triangulation_traits_2<K>             Gt;
typedef CGAL::Periodic_2_triangulation_vertex_base_2<Gt>                Vbb;
typedef CGAL::Triangulation_vertex_base_with_info_2<unsigned, Gt, Vbb>  Vb;
typedef CGAL::Periodic_2_triangulation_face_base_2<Gt>                  Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb>                    Tds;
typedef CGAL::Periodic_2_Delaunay_triangulation_2<Gt, Tds>              Delaunay;
typedef Delaunay::Point                                                 Point;

then I double checked the manual to see if the explantions are different or not. As far as I understand, Software Design 4.14 and Software Design 4.7 are the same and match to second example. Since I need triangulation with empty circle property, and I just need to retrieve the indices of neighboring vertices in Delaunay triangulation, does the first also lead to the same results? I can check them for some points, but I just doubt that if they produce the same results for every set of points?

Mael Mael · Accepted Answer · 2019-05-13T08:01:25

This leads to exactly the same results.

For a more detailed explanation: the periodic triangulation expects a triangulation data structure with vertices and faces that provide a certain number of functions and members, described by concepts (see P2T2 concepts). In CGAL 4.7, the vertex and face classes did not meet these requirements: they were missing some periodic information that is only used in a few functions of P2T2. However everything compiled and ran just fine because the examples did not call these few functions. Some more recent compilers were over-zealous and decided they wanted to be able to compile all functions of the class, even if those that were not called, and thus the vertex and base classes that were being used were not satisfying anymore.

See also https://github.com/CGAL/cgal/pull/3624.

CGAL: Delaunay triangulation vs triangulation in CGAL's example

1 Answers