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

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

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

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

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

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

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

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;
};