CGAL中2D三角剖分的数据结构

本文介绍: 三角剖分数据结构是一种设计用于处理二维三角剖分表示的数据结构。三角剖分数据结构的概念主要是设计用作CGAL2D三角剖分类的数据结构，这些类是嵌入平面中的三角剖分。然而，这个概念似乎更一般，可以用于任何可定向的无边界三角剖分曲面，无论三角剖分嵌入的空间维数是多少。

1、定义

三角剖分数据结构是一种设计用于处理二维三角剖分表示的数据结构。三角剖分数据结构的概念主要是设计用作CGAL2D三角剖分类的数据结构，这些类是嵌入平面中的三角剖分。然而，这个概念似乎更一般，可以用于任何可定向的无边界三角剖分曲面，无论三角剖分嵌入的空间维数是多少。

1.1、一种基于面和顶点的数据结构

CGAL2D三角剖分的表示基于面和顶点，边仅通过两个面之间的邻接关系隐式表示。

三角剖分数据结构可以被看作是面和顶点的容器，用于维护它们之间的关联和邻接关系。

每个三角形面都可以访问它的三个入射顶点和它的三个相邻面。每个顶点都可以访问它的一个入射面，并通过该面访问它的入射面的循环列表。

面的三个顶点用索引0、1和2。面的邻居也用索引0、1、2，这样用i 索引的邻居与具有相同索引的顶点相对。见下图，该图所示的函数 ccw(i)和cw(i)分别计算 i+1和i-1模3。

每个边都有两个隐式表示：与索引为i的顶点相对的面f的边，可以表示为f的邻居(i)的边。

这种对单形复体的表示在任何维度上都是可扩展的。更准确地说，在维度 d 中，数据结构将显式表示单元（即最大维度的面）和顶点（即维度为 0 的面）。所有介于 1 和 d-1 之间的维度的面都将有一个隐式表示。二维三角剖分数据结构可以表示 2、1 或 0 维的单形复体。

1.2、顶点和面的集合

二维三角剖分数据结构所维护的面集合是每个边缘与两个面相交的集合。换句话说，所维护的面集合在拓扑上等价于二维三角剖分的球体。

此规则扩展到出现在退化情况或三角剖分具有少于三个顶点的情况下的低维三角剖分数据结构。一维三角剖分结构维护一组顶点和边，它们形成一个环，在拓扑上等价于一个1-球体。

零维三角剖分数据结构只包括两个相邻的顶点，在拓扑上等价于一个0-球体。

2、三角剖分数据结构的概念

可以看出，Triang ul a ti onDa t aSt ructure _2模型有一个用于三角剖分面和顶点的容器。这个类还负责三角剖分的组合完整性。这意味着在进行三角剖分的组合修改时，三角剖分数据结构保持三角剖分顶点和面之间的适当关联和邻接关系。组合修改一词是指不涉及三角剖分几何嵌入知识的操作。例如，在给定面或给定边缘中插入新顶点，抑制度为三的顶点，翻转两条边是在数据结构级别执行的组合操作的例子。

三角测量数据结构需要提供：三角剖分的顶点和面的类型 Ve rte x 和 Face；类型Ve rte x _handl e和Face _handl e，它们是Handle 概念的模型，通过它们可以访问顶点和面；迭代器，用于访问三角剖分的所有顶点、边和面；循环器访问给定顶点相关的所有顶点、边和面；三角剖分数据结构负责创建和删除面和顶点（内存管理）。它提供的功能可以给出三角剖分中的面、边和顶点的数量。

三角剖分数据结构提供成员函数以执行三角剖分的以下组合变换：两个相邻面的翻转；添加一个新的顶点来分割给定的面；添加分割给定边的新顶点；增加一个新的顶点，使退化的低维三角测量的维数增加一；移除入射到三个面的顶点；删除降低三角测量尺寸的顶点

3、默认的三角剖分数据结构

CGAL提供了类 Triang ul a ti on_data _structur e _2<Vb,Fb> 作为默认的三角剖分数据结构。

3.1、灵活性

为了提供灵活性，默认的三角剖分数据结构由两个参数模板化，这两个参数分别代表顶点基类和面基类。概念Triang ul a tionDSVe rte xBa se_2和Triang ulationDSFaceBase_2描述了三角剖分数据结构的顶点和面类的要求。

这种设计允许用户插入三角剖分数据结构，其中包含针对其应用而调整的自己的顶点或面类。

3.2、模板 参数的循环依赖性

由于邻接关系和关联关系存储在顶点和面中，因此顶点和面类必须知道三角剖分数据结构提供的面和顶点上的句柄类型。因此，顶点和面类需要由三角剖分数据结构模板化。由于三角剖分数据结构本身是由顶点和面类模板化的，这导致了一种循环依赖关系。

3.3、重新绑定 机制

CGAL提出的解决这种循环依赖的解决方案基于类似于标准分配器类 std:: allocator 中使用的机制的重新绑定机制。插入三角剖分数据结构实例化的顶点和面类本身是用一个伪数据结构实例化的。然后，三角剖分数据结构将重新绑定这些类，将自己插入伪数据结构的位置，然后再使用它们来派生顶点和面类。重新绑定是通过顶点和面类中的嵌套模板类 Rebind _TDS 执行的，该类将重新绑定的类作为称为 Other 的类型提供。

这是它的工作原理图。首先，这是三角剖分数据结构中的重新绑定。

template < class Vb, class Fb &gt;
class Triangulation_data_structure
{
typedef Triangulation_data_structure<Vb,Fb> Self;
// Rebind the vertex and face base to the actual TDS (Self).
typedef typename Vb::template Rebind_TDS<Self>::Other VertexBase;
typedef typename Fb::template Rebind_TDS<Self>::Other FaceBase;
// ... further internal machinery leads to the final public types:
public:
typedef ... Vertex;
typedef ... Face;
typedef ... Vertex_handle;
typedef ... Face_handle;
};

3.4、使用灵活性

有几种方法可以利用三角测量数据结构提供的灵活性。

首先，当用户需要在顶点和面中拥有不依赖于三角剖分数据结构所定义类型的附加信息时，可以插入预定义的类 Triangulation_vertex_base_wi th_info_2 和 Triangulation_face_base_wi th_info_2。这些类有一个模板参数 Info，由用户定义的类型实例化。它们存储此类型的数据成员，并允许对其进行访问。

其次，用户可以从默认基类中派生自己的基类：Triangulation_ds_vertex_base_2和Triangulation_ds_face_base_2是默认基类，可插入单独使用的三角剖分数据结构。三角剖分类需要一个数据结构，其中已经插入了其他基类。大多数三角剖分类的默认基类是Triangulation_vertex_base_2，而Triangulation_face_base_2是三角剖分数据结构插入三角剖分类时的默认基类。

最后，用户可以编写自己的基类。如果单独使用三角剖分数据结构，则基类的要求由概念TriangulationDSVertexBase_2和TriangulationDSFaceBase_2描述。如果三角剖分数据结构被插入到三角剖分类中，则顶点和基类的概念取决于三角剖分类。适用于基本三角剖分和Delaunay三角剖分的最基本概念是TriangulationVertexBase_2和TriangulationFaceBase_2。