7.1 二维三角化基础 (Triangulation_2)

下一节: 7.2 二维Delaunay三角化

1. 数学理论基础

1.1 三角化的定义

三角化 (Triangulation) 是计算几何中的核心概念，指将平面点集划分为一组三角形，使得：

覆盖性：所有三角形的并集等于点集的凸包
无重叠性：任意两个三角形的交集要么是空集，要么是一个公共顶点，要么是一条公共边
顶点一致性：三角形的顶点恰好是给定的点集

形式化定义：给定平面点集 $P = {p_{1}, p_{2}, ..., p_{n}}$ ，三角化 $T$ 是满足以下条件的一组三角形 ${t_{1}, t_{2}, ..., t_{m}}$ ：

$⋃_{i = 1}^{m} t_{i} = conv (P)$

$\forall i \neq = j : t_{i} \cap t_{j} \in {\emptyset, vertex, edge}$

1.2 欧拉公式与三角化性质

对于平面三角化，欧拉公式成立：

$V - E + F = 2$

其中：

$V$ = 顶点数
$E$ = 边数
$F$ = 面数（包括外部面）

对于具有 $n$ 个顶点的点集（假设无三点共线， $h$ 个点在凸包上）：

三角形数量： $2 n - 2 - h$
边数量： $3 n - 3 - h$

1.3 组合数据结构

CGAL的Triangulation_2使用双向连通边表 (Doubly Connected Edge List, DCEL) 的变体：

顶点 (Vertex): 存储几何坐标 + 指向一条关联边的指针
边 (Edge): 由两个有向半边(Halfedge)组成
面 (Face): 存储指向边界半边的指针 + 可能存储三个顶点指针
半边 (Halfedge): 存储源顶点、目标面、对偶半边、下一条半边

1.4 三角化的对偶图

三角化的对偶图将每个三角形映射为一个节点，相邻三角形之间用边连接。这种结构在：

点定位算法
邻域查询
网格细化

等操作中非常有用。

2. 类架构分析

2.1 核心类层次结构

Triangulation_2<Traits, Tds>                    // 基类
    ├── Delaunay_triangulation_2<Traits, Tds>   // Delaunay三角化
    ├── Constrained_triangulation_2<Traits, Tds, Itag>  // 约束三角化
    │       └── Constrained_Delaunay_triangulation_2     // 约束Delaunay
    └── Regular_triangulation_2<Traits, Tds>    // 正则三角化

其中：
- Traits: 几何特征类 (Geometric Traits)
- Tds: 三角化数据结构 (Triangulation Data Structure)
- Itag: 交集标签 (Intersection Tag)

2.2 模板参数详解

Traits (几何特征类)

// 概念: TriangulationTraits_2
class TriangulationTraits_2 {
public:
    // 几何类型
    typedef Point_2          Point;           // 点类型
    typedef Segment_2        Segment;         // 线段类型
    typedef Triangle_2       Triangle;        // 三角形类型
    
    // 谓词 (Predicates)
    typedef Orientation_2    Orientation;     // 方向测试
    typedef Side_of_oriented_circle_2 Side_of_oriented_circle;  // 圆测试
    
    // 构造器 (Constructions)
    typedef Construct_segment_2 Construct_segment;
    typedef Construct_triangle_2 Construct_triangle;
    typedef Construct_circumcenter_2 Construct_circumcenter;
};

常用Traits实现：

CGAL::Exact_predicates_inexact_constructions_kernel (推荐)
CGAL::Exact_predicates_exact_constructions_kernel (需要精确构造)
CGAL::Cartesian<FT> / CGAL::Homogeneous<RT>

Tds (三角化数据结构)

// 概念: TriangulationDataStructure_2
// 默认实现: CGAL::Triangulation_data_structure_2<Vb, Fb>
 
// 顶点基类
class Triangulation_ds_vertex_base_2 {
public:
    Face_handle face();  // 指向一个关联面
    void set_face(Face_handle f);
};
 
// 面基类
class Triangulation_ds_face_base_2 {
public:
    Vertex_handle vertex(int i);     // 第i个顶点 (i=0,1,2)
    Face_handle neighbor(int i);     // 第i条对边的邻接面
    int index(Face_handle n);        // 邻接面n在本面的索引
    bool is_constrained(int i);      // 第i条边是否为约束边
};

2.3 关键类型定义

typedef Triangulation_2<Traits, Tds>            Triangulation;
 
typedef Traits::Point_2                         Point;
typedef Traits::Segment_2                       Segment;
typedef Traits::Triangle_2                      Triangle;
 
// 句柄 (Handles) - 类似智能指针
typedef Tds::Vertex_handle                      Vertex_handle;
typedef Tds::Face_handle                        Face_handle;
typedef Tds::Edge                               Edge;  // pair<Face_handle, int>
 
// 迭代器 (Iterators)
typedef Tds::Vertex_iterator                    Vertex_iterator;
typedef Tds::Edge_iterator                      Edge_iterator;
typedef Tds::Face_iterator                      Face_iterator;
typedef Tds::Face_circulator                    Face_circulator;  // 绕顶点的面循环器
 
// 特殊值
static Vertex_handle                            Vertex_handle(NULL);  // 无限远顶点
static Face_handle                              Face_handle(NULL);    // 无限远面

3. 实现细节

3.1 内部表示

// 面的内部存储结构
class Face {
    Vertex_handle vertices[3];    // 三个顶点
    Face_handle   neighbors[3];   // 三个邻接面 (对边邻接)
    // 边i的对边是vertices[(i+1)%3]到vertices[(i+2)%3]
    // neighbors[i] 共享边i的对边
};
 
// 顶点存储
class Vertex {
    Point point;                  // 几何坐标
    Face_handle face;             // 指向一个关联面
};

3.2 无限面处理

CGAL使用虚拟无限顶点 (infinite vertex) 技术处理无界区域：

// 概念：添加一个"无限远"顶点，使所有面都成为三角形
// 凸包边与无限顶点形成"无限面"
 
// 判断面是否为无限面
bool is_infinite(Face_handle f) {
    return f->vertex(0) == Vertex_handle(NULL) ||
           f->vertex(1) == Vertex_handle(NULL) ||
           f->vertex(2) == Vertex_handle(NULL);
}
 
// 获取有限面
Face_circulator incident_faces(Vertex_handle v) {
    // 返回绕顶点v的所有有限面
}

3.3 点定位策略

// 点定位返回包含查询点的面
Face_handle locate(const Point& query, Face_handle start = Face_handle());
 
// 实现策略：
// 1. 行走法 (Walking strategy): 从start面开始，沿方向向查询点移动
// 2. 历史DAG (Delaunay): 维护插入历史的有向无环图
// 3. 层次结构 (Hierarchy): 多级粗化网格加速
 
// 定位结果类型
enum Locate_type {
    VERTEX,      // 查询点与顶点重合
    EDGE,        // 查询点在边上
    FACE,        // 查询点在面内部
    OUTSIDE_CONVEX_HULL,  // 查询点在凸包外
    OUTSIDE_AFFINE_HULL   // 查询点与点集共线/共点
};

3.4 插入算法

// 基本插入 - 使用翻转算法
Vertex_handle insert(const Point& p, Face_handle start = Face_handle());
 
// 插入到指定面中
Vertex_handle insert_in_face(const Point& p, Face_handle f);
 
// 插入到边上
Vertex_handle insert_in_edge(const Point& p, Face_handle f, int i);
 
// 批量插入优化
void insert(Iterator first, Iterator last);

插入算法步骤：

定位：找到包含点p的面f
分裂：将f分裂为3个新面（点在内部）或2个新面（点在边上）
恢复Delaunay性质（仅Delaunay三角化）：边翻转

// 边翻转 (Edge Flip)
void flip(Face_handle f, int i) {
    // 翻转面f的边i
    // 前提：四边形必须是凸的
    //       f和neighbors[i]形成凸四边形
    
    Face_handle n = f->neighbor(i);
    int j = n->index(f);  // f在n中的索引
    
    // 重新连接边
    // 更新顶点关联关系
}

4. 完整代码示例

4.1 基础三角化示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_2.h>
#include <iostream>
#include <vector>
 
// 定义内核和三角化类型
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
using Triangulation = CGAL::Triangulation_2<K>;
 
using Point = K::Point_2;
using Vertex_handle = Triangulation::Vertex_handle;
using Face_handle = Triangulation::Face_handle;
using Vertex_circulator = Triangulation::Vertex_circulator;
using Face_circulator = Triangulation::Face_circulator;
 
int main() {
    // 创建三角化对象
    Triangulation tri;
    
    // ========== 插入点 ==========
    std::cout << "=== 插入点 ===" << std::endl;
    
    // 方法1: 逐个插入
    Vertex_handle v0 = tri.insert(Point(0, 0));
    Vertex_handle v1 = tri.insert(Point(1, 0));
    Vertex_handle v2 = tri.insert(Point(0.5, 1));
    
    std::cout << "插入3个点后，顶点数: " << tri.number_of_vertices() << std::endl;
    std::cout << "面数: " << tri.number_of_faces() << std::endl;
    
    // 方法2: 批量插入 (更高效)
    std::vector<Point> points = {
        Point(2, 0), Point(2, 1), Point(1.5, 0.5),
        Point(0, 2), Point(1, 2), Point(0.5, 1.5)
    };
    tri.insert(points.begin(), points.end());
    
    std::cout << "批量插入后，顶点数: " << tri.number_of_vertices() << std::endl;
    std::cout << "面数: " << tri.number_of_faces() << std::endl;
    
    // ========== 遍历操作 ==========
    std::cout << "\n=== 遍历所有顶点 ===" << std::endl;
    for (auto vit = tri.vertices_begin(); vit != tri.vertices_end(); ++vit) {
        std::cout << "顶点: (" << vit->point().x() << ", " 
                  << vit->point().y() << ")" << std::endl;
    }
    
    std::cout << "\n=== 遍历所有面 (有限面) ===" << std::endl;
    for (auto fit = tri.faces_begin(); fit != tri.faces_end(); ++fit) {
        std::cout << "三角形: ";
        for (int i = 0; i < 3; ++i) {
            Point p = fit->vertex(i)->point();
            std::cout << "(" << p.x() << ", " << p.y() << ") ";
        }
        std::cout << std::endl;
    }
    
    // ========== 点定位 ==========
    std::cout << "\n=== 点定位 ===" << std::endl;
    Point query(0.5, 0.5);
    Face_handle loc = tri.locate(query);
    
    if (tri.is_infinite(loc)) {
        std::cout << "查询点在凸包外" << std::endl;
    } else {
        std::cout << "查询点 (0.5, 0.5) 位于面内，顶点为:" << std::endl;
        for (int i = 0; i < 3; ++i) {
            Point p = loc->vertex(i)->point();
            std::cout << "  (" << p.x() << ", " << p.y() << ")" << std::endl;
        }
    }
    
    // ========== 邻域查询 ==========
    std::cout << "\n=== 顶点邻域查询 ===" << std::endl;
    std::cout << "顶点 (0,0) 的相邻顶点:" << std::endl;
    
    Vertex_circulator vc = tri.incident_vertices(v0), done(vc);
    if (vc != nullptr) {
        do {
            if (!tri.is_infinite(vc)) {
                Point p = vc->point();
                std::cout << "  (" << p.x() << ", " << p.y() << ")" << std::endl;
            }
        } while (++vc != done);
    }
    
    std::cout << "\n顶点 (0,0) 的关联面:" << std::endl;
    Face_circulator fc = tri.incident_faces(v0), fdone(fc);
    if (fc != nullptr) {
        int count = 0;
        do {
            if (!tri.is_infinite(fc)) {
                std::cout << "  面 " << ++count << ": ";
                for (int i = 0; i < 3; ++i) {
                    Point p = fc->vertex(i)->point();
                    std::cout << "(" << p.x() << ", " << p.y() << ") ";
                }
                std::cout << std::endl;
            }
        } while (++fc != fdone);
    }
    
    // ========== 几何查询 ==========
    std::cout << "\n=== 几何查询 ===" << std::endl;
    
    // 获取凸包
    std::list<Point> convex_hull;
    tri.incident_vertices(tri.infinite_vertex(), 
                          std::back_inserter(convex_hull));
    std::cout << "凸包顶点数: " << convex_hull.size() << std::endl;
    
    // 判断点是否在凸包内
    Point inside_point(0.5, 0.3);
    Face_handle f = tri.locate(inside_point);
    std::cout << "点 (0.5, 0.3) 在凸包内: " 
              << (!tri.is_infinite(f) ? "是" : "否") << std::endl;
    
    return 0;
}

4.2 自定义顶点信息示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <CGAL/Triangulation_data_structure_2.h>
#include <CGAL/Triangulation_2.h>
#include <iostream>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
 
// 自定义顶点信息类型
struct VertexInfo {
    int id;
    double weight;
    std::string label;
    
    VertexInfo(int i = -1, double w = 0.0, std::string l = "")
        : id(i), weight(w), label(l) {}
};
 
// 定义带信息的顶点基类
using Vb = CGAL::Triangulation_vertex_base_with_info_2<VertexInfo, K>;
using Fb = CGAL::Triangulation_face_base_2<K>;
using Tds = CGAL::Triangulation_data_structure_2<Vb, Fb>;
using Triangulation = CGAL::Triangulation_2<K, Tds>;
 
using Point = K::Point_2;
using Vertex_handle = Triangulation::Vertex_handle;
 
int main() {
    Triangulation tri;
    
    // 插入带信息的点
    auto v0 = tri.insert(Point(0, 0));
    v0->info() = VertexInfo(0, 1.0, "origin");
    
    auto v1 = tri.insert(Point(1, 0));
    v1->info() = VertexInfo(1, 2.0, "x-axis");
    
    auto v2 = tri.insert(Point(0, 1));
    v2->info() = VertexInfo(2, 3.0, "y-axis");
    
    auto v3 = tri.insert(Point(1, 1));
    v3->info() = VertexInfo(3, 4.0, "corner");
    
    // 遍历并访问自定义信息
    std::cout << "顶点信息:" << std::endl;
    for (auto vit = tri.vertices_begin(); vit != tri.vertices_end(); ++vit) {
        Point p = vit->point();
        VertexInfo& info = vit->info();
        std::cout << "点 (" << p.x() << ", " << p.y() << "): "
                  << "id=" << info.id 
                  << ", weight=" << info.weight
                  << ", label=" << info.label << std::endl;
    }
    
    // 基于信息查找顶点
    std::cout << "\n查找weight > 2.0的顶点:" << std::endl;
    for (auto vit = tri.vertices_begin(); vit != tri.vertices_end(); ++vit) {
        if (vit->info().weight > 2.0) {
            Point p = vit->point();
            std::cout << "  " << vit->info().label 
                      << " at (" << p.x() << ", " << p.y() << ")" << std::endl;
        }
    }
    
    return 0;
}

4.3 高级遍历与修改示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_2.h>
#include <iostream>
#include <map>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
using Triangulation = CGAL::Triangulation_2<K>;
 
using Point = K::Point_2;
using Vertex_handle = Triangulation::Vertex_handle;
using Face_handle = Triangulation::Face_handle;
using Edge = Triangulation::Edge;
 
int main() {
    Triangulation tri;
    
    // 创建网格
    std::vector<Point> points;
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            points.push_back(Point(i, j));
        }
    }
    tri.insert(points.begin(), points.end());
    
    std::cout << "三角化统计:" << std::endl;
    std::cout << "  顶点数: " << tri.number_of_vertices() << std::endl;
    std::cout << "  面数: " << tri.number_of_faces() << std::endl;
    std::cout << "  边数: " << tri.number_of_edges() << std::endl;
    
    // ========== 边遍历与分类 ==========
    std::cout << "\n=== 边分类 ===" << std::endl;
    
    int boundary_edges = 0;
    int interior_edges = 0;
    
    for (auto eit = tri.edges_begin(); eit != tri.edges_end(); ++eit) {
        Face_handle f = eit->first;
        int i = eit->second;
        Face_handle n = f->neighbor(i);
        
        if (tri.is_infinite(n)) {
            ++boundary_edges;  // 边界边（邻接无限面）
        } else {
            ++interior_edges;  // 内部边
        }
    }
    
    std::cout << "边界边数: " << boundary_edges << std::endl;
    std::cout << "内部边数: " << interior_edges << std::endl;
    
    // ========== 计算每个顶点的度数 ==========
    std::cout << "\n=== 顶点度数 ===" << std::endl;
    
    std::map<Vertex_handle, int> degree_map;
    for (auto vit = tri.vertices_begin(); vit != tri.vertices_end(); ++vit) {
        int degree = 0;
        auto vc = tri.incident_vertices(vit), done(vc);
        if (vc != nullptr) {
            do {
                if (!tri.is_infinite(vc)) {
                    ++degree;
                }
            } while (++vc != done);
        }
        degree_map[vit] = degree;
    }
    
    for (const auto& [vh, deg] : degree_map) {
        Point p = vh->point();
        std::cout << "顶点 (" << p.x() << ", " << p.y() << "): 度数=" << deg << std::endl;
    }
    
    // ========== 面邻接图遍历 ==========
    std::cout << "\n=== 面邻接关系 ===" << std::endl;
    
    int face_id = 0;
    std::map<Face_handle, int> face_ids;
    for (auto fit = tri.finite_faces_begin(); fit != tri.finite_faces_end(); ++fit) {
        face_ids[fit] = face_id++;
    }
    
    for (auto fit = tri.finite_faces_begin(); fit != tri.finite_faces_end(); ++fit) {
        std::cout << "面 " << face_ids[fit] << " 的邻居: ";
        for (int i = 0; i < 3; ++i) {
            Face_handle n = fit->neighbor(i);
            if (!tri.is_infinite(n)) {
                std::cout << face_ids[n] << " ";
            } else {
                std::cout << "inf ";
            }
        }
        std::cout << std::endl;
    }
    
    // ========== 线段遍历 (边迭代器) ==========
    std::cout << "\n=== 所有边线段 ===" << std::endl;
    
    for (auto eit = tri.finite_edges_begin(); eit != tri.finite_edges_end(); ++eit) {
        auto segment = tri.segment(*eit);
        std::cout << "边: (" << segment.source().x() << ", " << segment.source().y() 
                  << ") -> (" << segment.target().x() << ", " << segment.target().y() 
                  << ")" << std::endl;
    }
    
    return 0;
}

5. 复杂度分析

5.1 时间复杂度

操作	平均复杂度	最坏复杂度	说明
insert(p)	O(1)	O(n)	随机插入平均O(1)，有序点最坏O(n)
insert(first, last)	O(n log n)	O(n²)	批量插入，使用随机化
locate(p)	O(√n)	O(n)	行走定位，Delaunay可用O(log n)
remove(v)	O(1)	O(n)	顶点删除，需重建局部区域
move(v, p)	O(1)	O(n)	顶点移动
incident_vertices(v)	O(d)	O(n)	d为顶点度数
incident_faces(v)	O(d)	O(n)	d为顶点度数
遍历所有面	O(n)	O(n)	线性遍历
凸包遍历	O(h)	O(n)	h为凸包顶点数

5.2 空间复杂度

存储项目	空间
顶点	O(n)
面	O(n)
边	O(n) (隐式存储)
总计	O(n)

精确计算（64位系统）：

每个顶点：约 24-32 字节（坐标 + 指针 + 可能的信息）
每个面：约 48-64 字节（3个顶点指针 + 3个邻接面指针）
n个点的三角化总空间：约 100n-150n 字节

5.3 性能优化建议

// 1. 批量插入而非逐个插入
std::vector<Point> points = ...;
tri.insert(points.begin(), points.end());  // O(n log n)
 
// 避免:
for (const auto& p : points) {
    tri.insert(p);  // 最坏O(n²)
}
 
// 2. 使用空间排序预处理
CGAL::spatial_sort(points.begin(), points.end());
tri.insert(points.begin(), points.end());
 
// 3. 预分配空间
tri.reserve(points.size());
 
// 4. 重用定位句柄
Face_handle hint;
for (const auto& p : points) {
    hint = tri.insert(p, hint);  // 使用上一次的定位结果作为提示
}
 
// 5. 选择合适的内核
// 如果不需要精确构造，使用:
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
// 而非:
// using K = CGAL::Exact_predicates_exact_constructions_kernel;

5.4 与Delaunay三角化的比较

特性	Triangulation_2	Delaunay_triangulation_2
插入复杂度	O(1) avg	O(log n) avg
空外接圆性质	无	有
最大化最小角	否	是
点定位	O(√n)	O(log n)
应用场景	一般三角化	高质量网格、插值

6. 总结

Triangulation_2是CGAL二维三角化的基础类，提供了：

灵活的模板设计：通过Traits和Tds参数化几何和数据结构
完整的组合操作：插入、删除、移动、遍历
高效的点定位：支持行走策略和提示优化
丰富的查询功能：邻域查询、凸包、面遍历

理解Triangulation_2的架构是掌握更高级三角化（Delaunay、约束三角化、正则三角化）的基础。后续章节将在这一基础上介绍具有特殊性质的三角化变体。

Chunibyo

Explorer

7.1 二维三角化基础 (Triangulation_2)

7.1 二维三角化基础 (Triangulation_2)

1. 数学理论基础

1.1 三角化的定义

1.2 欧拉公式与三角化性质

1.3 组合数据结构

1.4 三角化的对偶图

2. 类架构分析

2.1 核心类层次结构

2.2 模板参数详解

Traits (几何特征类)

Tds (三角化数据结构)

2.3 关键类型定义

3. 实现细节

3.1 内部表示

3.2 无限面处理

3.3 点定位策略

3.4 插入算法

4. 完整代码示例

4.1 基础三角化示例

4.2 自定义顶点信息示例

4.3 高级遍历与修改示例

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 性能优化建议

5.4 与Delaunay三角化的比较

6. 总结

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

7.1 二维三角化基础 (Triangulation_2)

7.1 二维三角化基础 (Triangulation_2) §

1. 数学理论基础 §

1.1 三角化的定义 §

1.2 欧拉公式与三角化性质 §

1.3 组合数据结构 §

1.4 三角化的对偶图 §

2. 类架构分析 §

2.1 核心类层次结构 §

2.2 模板参数详解 §

Traits (几何特征类) §

Tds (三角化数据结构) §

2.3 关键类型定义 §

3. 实现细节 §

3.1 内部表示 §

3.2 无限面处理 §

3.3 点定位策略 §

3.4 插入算法 §

4. 完整代码示例 §

4.1 基础三角化示例 §

4.2 自定义顶点信息示例 §

4.3 高级遍历与修改示例 §

5. 复杂度分析 §

5.1 时间复杂度 §

5.2 空间复杂度 §

5.3 性能优化建议 §

5.4 与Delaunay三角化的比较 §

6. 总结 §

Graph View

Table of Contents

Backlinks

7.1 二维三角化基础 (Triangulation_2)

1. 数学理论基础

1.1 三角化的定义

1.2 欧拉公式与三角化性质

1.3 组合数据结构

1.4 三角化的对偶图

2. 类架构分析

2.1 核心类层次结构

2.2 模板参数详解

Traits (几何特征类)

Tds (三角化数据结构)

2.3 关键类型定义

3. 实现细节

3.1 内部表示

3.2 无限面处理

3.3 点定位策略

3.4 插入算法

4. 完整代码示例

4.1 基础三角化示例

4.2 自定义顶点信息示例

4.3 高级遍历与修改示例

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 性能优化建议

5.4 与Delaunay三角化的比较

6. 总结