CGAL的周期三角剖分（相关信息较少）

CGAL的周期二维三角剖分类旨在表示二维平面上的一组点的三角剖分。该三角剖分形成其计算空间的分区。它是一个单纯复体，即它包含任何k-单纯形的所有关联j-单纯形（j<k），并且两个k-单纯形要么不重叠，要么共享一个公共的j-面，j<k。发生的维度小于等于2的单纯形称为顶点、边缘和面。

1、扁平环面

二维周期性三角剖分包计算了T2c空间中的三角剖分，该空间定义如下：设c属于R不等于0且G是（c·Z2，+）的群，其中c·Z表示包含所有整数倍c的集合。平环面是以下等式定义的空间：T2c:=R2/G。参数c定义了周期。

T2c的元素是R2中点集的等价类。我们称这些点为T2c元素的代表。实现不是直接在T2c的元素上工作，而是在R2的一些代表上工作。给定α和β，方块[α，α+c)×[β，β+c)包含T2c中每个元素的唯一代表。我们称其为原始域。从今以后，当我们谈论点时，我们通常指的是原始域内点的代表。请注意，任何输入点都需要是上述定义的原始域的半开方块的元素。

有一些单纯形包含了原始域内的点，但也包含了原始域外的点。原始域外的点是原始域内点的周期性副本。因此，要指定一个单纯形，我们需要点和一些附加信息来确定每个点的相应周期性副本。T2c的代表的集合是一个方块点网格。我们通过一个二维整数向量（ox，oy）来指定每个代表，称为偏移量。它代表原始域内的代表在x和y方向上必须平移的周期数量。（0,0）对应于原始域内的代表。要指定k单纯形，我们需要k+1个点偏移量对。

2、演示

三角剖分是通过关联和邻接关系连接在一起的顶点和面的集合。每个面都可以访问它的三个关联顶点、它们的相应偏移量以及它的三个相邻面。每个顶点都可以访问它的一个关联面。

面的三个顶点在正方向上用0、1和2表示。T2c中单形的方向被定义为R2中相应单形的方向，由各自偏移量确定的代表给出。

与基础组合三角剖分一样，面的邻居以0、1和2进行索引，使得索引为i的邻居与索引相同的顶点相对。边缘（1-面）没有明确表示：一条边缘由一个面和一个索引给出（面f的边缘i是f的边缘，与索引为i的顶点相对）。

一些点集在T2c中不承认三角剖分。在这种情况下，我们使用点集的9个周期拷贝，排列在一个边长为3c的正方形中。以这种方式构造的任何点集在R2/G'中都有三角剖分，其中G'=(3c⋅Z)2。因此，我们在这个空间中计算三角剖分，这是一个T2c的9片覆盖空间。

1个覆盖空间和9个覆盖空间中的相同周期三角剖分。

管理副本的功能在很大程度上对用户隐藏。但是有一些不可忽视的影响。例如，如果点集不允许在T2c中进行三角剖分，则组合迭代器（Face_iterator、Edge_iterator和Vertex_iterator）会返回内部存储的所有单形，对应于每个几何基元（三角形、线段和点）的9个周期副本。这是确保邻接关系一致性的必要条件。如果希望每个基元只有一个周期副本，我们提供几何迭代器。它们返回三角剖分的几何基元，而没有它们之间的关系。另一个影响是，当算法从9片覆盖切换到1片覆盖时，引用已删除项的Vertex_handles和Face_handles失效。

在数据结构中，每个顶点存储它对应的输入点。如果我们在 9 片覆盖空间中计算，每个顶点存储它对应的原始域内的代表。因此，与 T2c 的同一元素对应的 9 个顶点都在 R2 中存储了相同的代表，而不是不同的周期副本。

有效性：周期三角剖分被称为局部有效的，当且仅当： (a)-(b) 其基础组合图，三角剖分数据结构，在局部是有效的。（c）任何单元的顶点都是按照正方向排列的。

3、Delaunay三角剖分

类Periodic_2_Delaunay_triangulation_2实现了T2c中点集的Delaunay三角剖分。

Delaunay三角剖分具有空圆性质，即每个面的外接圆不包含三角剖分中的任何其他顶点。这些三角剖分是唯一定义的，除了四个点共圆的退化情况。但是请注意，即使在这些情况下，CGAL实现也会计算出唯一的三角剖分。

此实现是完全动态的：它支持插入点和删除顶点。

4、三角剖分的继承

Periodic_2_triangulation_hierarchy_2 类是第 2D_Triangulations 章三角剖分层次一节中描述的层次结构在周期情况下的改编。

类 Periodic_2_triangulation_hierarchy_2<Tr> 继承了作为模板参数 Tr 传递的三角剖分类型。插入、移动和删除成员函数被重写，以在每次操作时更新数据结构。定位查询也被重写，以利用数据结构进行快速处理。

5、软件设计

我们选择前缀“Periodic_2”来强调三角剖分在空间的所有两个方向上都是周期性的。还存在“圆柱形”周期性，其中三角剖分仅在空间的一个方向上是周期性的。

两个主要类Periodic_2_Delaunay_triangulation_2和Periodic_2_triangulation_2提供高级几何功能，并负责几何有效性。 Periodic_2_Delaunay_triangulation_2包含所有Delaunay三角剖分特有的功能，如点插入和顶点删除、圆边测试、查找给定点的冲突区域、对偶函数等。 Periodic_2_triangulation_2包含所有一般三角剖分通用的功能，如三角剖分中点的位置、访问函数、几何查询如方向测试等。

它们被构建为三角剖分数据结构之上的层，该结构存储了它们的组合结构。几何和组合之间的这种分离在软件设计中反映为三角剖分类采用两个模板参数的事实：

几何特征类，它提供了用作点的类型以及对它们的基本操作（谓词和构造）。此外，它还包含偏移类型。这个参数的概念在几何特征参数一节中有更详细的描述。应该细化的概念是 Periodic_2Triangulation Traits_2（用于 Periodic_2_triangulation_2）和 Periodic_2DelaunayTriangulation Traits_2（用于 Periodic_2_Delaunay_triangulation_2）。

5.1、几何特征参数

周期三角剖分类 Periodic_2_triangulation_2< Traits, Tds> 的第一个模板参数是几何特征类，由概念 Periodic_2Triangulation Traits_2 描述。类似地，Delaunay三角剖分类 Periodic_2_Delaunay_triangulation_2< Traits,Tds> 的第一个模板参数是几何特征类，由概念 TPeriodic_2DelaunayTriangulation raits_2 描述。这些概念与 Triangulation Traits_2 和 DelaunayTriangulation Traits_2）的不同之处在于，它们还使用偏移实现了所有对象、谓词和构造。

类 Periodic_2_Delaunay_triangulation_traits_2< Traits,Periodic_2Offset_2> 提供了所需的功能。它有两个模板参数：概念 DelaunayTriangulation Traits_2 的模型和概念 Periodic_2Offset_2 的模型。由于概念 Triangulation_Traits_2 细化了概念 DelaunayTriangulation Traits_2，类 Periodic_2_Delaunay_triangulation_traits_2< Traits,Periodic_2Offset_2> 也是概念 Triangulation Traits_2 的模型。

Cartesian、Homogeneous、Simple_cartesian、Simple_homogeneous 和 Filtered_kernel 核都可以用作 Traits 的模型。 Periodic_2_triangulation_traits_2 提供精确谓词和精确构造（如果 Traits 提供）。如果使用 Filtered_kernel<CK> 作为第一个模板参数，其中 CK 是不精确内核，则它提供精确谓词，但不提供精确构造。使用 Exact_predicates_inexact_constructions_kernel 作为 Traits 提供快速和精确谓词，但不提供精确构造，使用 Exact_predicates_exact_constructions_kernel 提供快速和精确谓词和精确构造。如果使用点、线段、三角形和四面体的对偶构造和构造，建议使用后者。

第二个参数Periodic_2Offset_2默认为Periodic_2_offset_2。

5.2、三角剖分数据结构参数

主要类 Periodic_2_triangulation_2 和 Periodic_2_Delaunay_triangulation_2(剖分方法) 的第二个模板参数是一个三角剖分数据结构类。该类必须是概念 TriangulationDataStructure_2 的模型，该概念描述了该类作为保持关联和邻接关系的面和顶点的容器的要求。

此外，概念 TriangulationDataStructure_2::Vertex 和 TriangulationDataStructure_2::Face 被扩展为支持周期性：顶点和面必须是 Periodic_2TriangulationVertexBase_2 和 Periodic_2TriangulationFaceBase_2 的模型。此类概念的一个模型是CGAL::Triangulation_data_structure_2。它由一个顶点基类和一个面基类参数化，这使得可以定制三角剖分数据结构使用的顶点和单元，从而使用它的几何三角剖分。提供了顶点和面概念的基本模型：CGAL::Periodic_2_triangulation_vertex_base_2 和CGAL::Periodic_2_triangulation_face_base_2。

所有三角剖分类中都提供了三角剖分数据结构参数的默认值，因此用户不需要指定，除非他想要使用不同的三角剖分数据结构或不同的顶点或单元基类。

5.3、设计的灵活性

Periodic_2_triangulation_2 使用 TriangulationDataStructure_2 的方式与 Triangulation_2 基本相同。这就是为什么软件设计中描述的灵活性以完全相同的方式适用。此外，类 Triangulation_vertex_base_with_info_2 和 Triangulation_face_base_with_info_2 可以直接重用。

6、性能

将二维周期性Delaunay三角剖分的性能与欧几里德二维Delaunay三角剖分进行比较。使用空间排序将点插入欧几里德二维Delaunay三角剖分中。在周期性三角剖分中，首先以随机顺序插入点，直到三角剖分在1个覆盖空间中有效。然后使用空间排序插入剩余的点。对于大型点集，首先插入虚拟点以在1个覆盖空间中创建有效的三角剖分。然后使用空间排序插入所有点。作为最后一步，再次删除虚拟点。