CGAL：Delaunay 三角剖分与 CGAL 示例中的三角剖分

Question

在我的工作中，我需要首先获得 shell 个焦点粒子的 Voronoi 邻居。为此，我使用 Delaunay 三角剖分，它是 Voronoi 镶嵌的对偶图。我使用的 CGAL 版本是 4.7。我一直使用 CGAL manual_4.7 中的基本代码作为模板来创建 Delaunay 三角剖分。我的问题在于该示例中的 headers 和 typedef，因为我最近发现它们与最新可用版本 CGAL 4.14 不同。在 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;

并在 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;

然后我仔细检查了手册，看看解释是否不同。据我了解， Software Design 4.14 and Software Design 4.7 与第二个示例相同且匹配。由于我需要空圆属性的三角剖分，并且我只需要检索 Delaunay 三角剖分中相邻顶点的索引，第一个是否也会导致相同的结果？我可以检查它们的某些点，但我只是怀疑它们是否对每组点产生相同的结果？

Answer 1

这会导致完全相同的结果。

更详细的解释：周期性三角剖分需要一个三角剖分数据结构，其顶点和面提供一定数量的函数和成员，由概念描述（参见P2T2 concepts）。在 CGAL 4.7 中，顶点和面 classes 不满足这些要求：它们缺少一些仅在 P2T2 的少数功能中使用的周期性信息。然而，所有编译的东西和运行都很好，因为示例没有调用这几个函数。一些更新的编译器是 over-zealous 并决定他们希望能够编译 class 的所有函数，即使那些函数没有被调用，因此顶点和基 classes正在使用中不再令人满意。

另见 https://github.com/CGAL/cgal/pull/3624。

CGAL：Delaunay 三角剖分与 CGAL 示例中的三角剖分

CGAL: Delaunay triangulation vs triangulation in CGAL's example

voronoi

delaunay

triangulation

cgal