1.1 CGAL简介与设计理念

“计算几何是算法的几何，CGAL是这些算法的可靠实现。”

—— CGAL开发团队

1.1.1 CGAL是什么？

CGAL（Computational Geometry Algorithms Library，计算几何算法库） 是一个开源的C++软件库，提供了大量计算几何领域的高效、可靠算法和数据结构实现。如果你曾经需要解决以下问题，CGAL就是你的得力助手：

计算两点之间的距离或判断它们是否相交
构建二维或三维的Delaunay三角剖分
计算凸包、Voronoi图或Minkowski和
进行多边形布尔运算（并、交、差）
在曲面上寻找最短路径
生成网格并进行网格处理

一个生活中的类比

想象你是一位建筑师，需要设计一座复杂的建筑。你当然可以从头开始计算每一根梁的角度、每一块玻璃的尺寸——但这既耗时又容易出错。CGAL就像是为你准备的一套精密工具箱：里面有经过严格测试的尺子、量角器、计算器，甚至还有自动绘图仪。你只需要告诉它”我想要一个三角形网格覆盖这个曲面”，它就能帮你完成复杂的计算。

CGAL的核心特点

特性	说明	对开发者的意义
Header-only	自5.0版本起，CGAL完全是头文件库	无需编译安装，直接包含即可使用
泛型编程	基于C++模板，算法与数据类型解耦	一次编写，适用于多种数值类型
稳健计算	精确谓词与过滤机制	避免浮点误差导致的几何错误
模块化设计	按功能划分为独立包	按需包含，减少编译依赖
丰富文档	详尽的API文档和示例	降低学习曲线，加速开发

谁在使用CGAL？

CGAL的应用领域极为广泛：

计算机图形学：网格生成、曲面重建、碰撞检测
地理信息系统（GIS）：地图叠加分析、路径规划
机器人学：运动规划、构型空间分析
计算机辅助设计（CAD）：布尔运算、偏移曲线
分子生物学：分子表面建模、蛋白质结构分析
有限元分析：高质量网格生成

1.1.2 历史演进：从欧几里得到现代计算几何

1995年：项目的诞生

CGAL的故事始于1995年，这是一个计算几何理论研究蓬勃发展的年代。当时，学术界已经积累了大量优雅的算法，但将这些算法转化为可靠的工业级代码却困难重重。主要挑战包括：

数值稳定性：浮点数计算的精度问题导致几何算法经常出现”意外”
代码重复：每个研究组都在重新实现相同的基础算法
缺乏标准化：没有统一的数据结构和接口规范

在这样的背景下，欧洲几个研究机构联合发起了CGAL项目，目标是创建一个开放、可靠、高效的计算几何算法库。

版本演进里程碑

CGAL版本演进时间线

1995  ─────────────────────────────────────────────────────────►
       │
       ├── 1997: CGAL 1.0 发布
       │   └── 首个公开版本，基于C++98
       │
       ├── 1999-2004: 2.x 系列
       │   └── 引入三维三角剖分、多边形运算
       │
       ├── 2006-2010: 3.x 系列
       │   └── 添加曲面重建、网格生成模块
       │
       ├── 2012-2019: 4.x 系列
       │   ├── C++11支持
       │   ├── 并行算法支持
       │   └── 大量新算法包
       │
       └── 2020至今: 5.x/6.x 系列
           ├── 5.0: 转为Header-only库
           ├── 6.0: 现代化CMake支持
           └── 持续更新中...

从”有库”到”Header-only”的革命（5.0版本）

在2020年发布的CGAL 5.0中，发生了一次架构性的重大转变：CGAL从传统的”编译为库”模式转变为纯头文件库（Header-only Library）。

传统库模式的痛点

在5.0之前，使用CGAL需要：

# 传统使用方式（CGAL 4.x及之前）
# 1. 下载源码
# 2. 编译CGAL库（可能需要数小时）
# 3. 安装到系统目录
# 4. 链接时指定 -lCGAL -lCGAL_Core

这种方式的问题：

编译时间长：首次安装可能需要数小时
版本冲突：系统CGAL版本与项目需求不匹配
部署困难：在不同机器上重复编译

Header-only的优势

CGAL 5.0+的使用方式：

# 现代使用方式（CGAL 5.0+）
# 1. 下载/克隆源码（或只用头文件包）
# 2. 在CMakeLists.txt中指定CGAL_DIR
# 3. 直接包含头文件使用，无需链接库

这种转变带来的好处：

方面	传统库模式	Header-only模式
安装时间	数小时	几分钟
版本管理	困难（系统级安装）	灵活（项目级包含）
编译优化	通用优化	针对具体使用场景优化
部署	需要目标机器有库	只需头文件和依赖
模板实例化	预编译有限实例	完全按需实例化

当前架构特点（CGAL 6.x）

CGAL 6.x延续了header-only架构，并进一步现代化：

CMake集成：现代化的CMake配置，支持find_package(CGAL)
C++17/20支持：充分利用现代C++特性
模块化包管理：每个包独立，按需包含
并行算法：广泛支持多线程和SIMD优化

1.1.3 设计理念深度解读

CGAL的设计深受**泛型编程（Generic Programming）**思想的影响，这一范式在C++标准模板库（STL）中也有充分体现。理解这些设计理念，将帮助你写出更优雅、更高效的CGAL代码。

理念一：泛型编程——算法与数据结构解耦

什么是泛型编程？

想象你要编写一个”排序”功能。传统做法是：

// 传统方式：为每种类型写单独的函数
void sort_int_array(int* arr, int n);      // 整数数组排序
void sort_double_array(double* arr, int n); // 浮点数组排序
// ... 还需要为字符串、自定义类型等写更多版本

而泛型编程的做法是：

// 泛型方式：一次编写，适用于所有类型
template<typename T>
void sort(T* arr, int n);  // 适用于任何可比较的类型T

核心思想：算法（排序的逻辑）与数据类型（整数、浮点、自定义类型）解耦。

CGAL中的泛型编程

CGAL将这一思想扩展到几何算法中。考虑”计算两点距离”这个简单操作：

#include <CGAL/Simple_cartesian.h>  // 包含笛卡尔坐标系内核
#include <CGAL/Point_2.h>           // 包含二维点类
#include <iostream>                  // 包含输入输出流
 
// 定义内核类型：使用double作为坐标类型，采用简单笛卡尔坐标系
typedef CGAL::Simple_cartesian<double> Kernel;
// 从内核中获取二维点类型
typedef Kernel::Point_2 Point_2;
 
int main() {
    // 创建两个二维点
    Point_2 p(0, 0);  // 原点
    Point_2 q(3, 4);  // 点(3, 4)
    
    // 计算并输出两点间的平方距离
    std::cout << "Distance: " << CGAL::squared_distance(p, q) << std::endl;
    return 0;
}

在这个例子中：

算法（squared_distance）与内核（Simple_cartesian<double>）是分离的
你可以在不修改算法代码的情况下，更换为不同的内核（如精确算术内核）

类比：乐高积木

CGAL的设计理念就像乐高积木：

基础积木块（内核）：提供点、线、面等基本几何对象
连接件（概念/Traits）：定义不同积木块之间的接口
成品模型（算法）：使用基础积木搭建的复杂结构

你可以用同一套”连接件”标准，组合不同系列的”基础积木”，搭建出各种”成品模型”。

理念二：稳健计算——精确谓词与过滤机制

计算几何的数值挑战

计算几何算法面临一个独特挑战：浮点数精度问题。

考虑一个简单的判断：三个点是否共线？

// 判断三点是否共线的数学公式
// 对于点A(x1,y1), B(x2,y2), C(x3,y3)，共线当且仅当：
// (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) = 0
 
bool are_collinear_approximate(double x1, double y1,
                                double x2, double y2,
                                double x3, double y3) {
    double det = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);
    return std::abs(det) < 1e-10;  // 使用一个很小的阈值
}

问题所在：

当三点接近共线时，浮点误差可能导致错误判断
这种错误会级联传播，导致算法崩溃或产生错误结果
在几何算法中，一个错误的”左转/右转”判断可能导致整个三角剖分失败

CGAL的解决方案：精确谓词

CGAL引入了**精确几何计算（Exact Geometric Computation）**的概念：

CGAL内核类型对比

┌─────────────────────────────────────────────────────────────┐
│ 内核类型                        │ 坐标表示    │ 计算特点    │
├─────────────────────────────────────────────────────────────┤
│ Simple_cartesian<double>        │ double      │ 快速，不精确 │
│ Exact_predicates_inexact_constructions_kernel │ 混合        │ 精确判断，近似构造│
│ Exact_predicates_exact_constructions_kernel   │ 任意精度    │ 完全精确    │
└─────────────────────────────────────────────────────────────┘

最常用的是 Exact_predicates_inexact_constructions_kernel（简称EPICK）：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
 
int main() {
    // 使用EPICK内核创建点
    Point_2 p(0, 0), q(1, 1), r(2, 2);
    
    // 判断三点是否共线 - 这是"谓词"，使用精确计算
    if (CGAL::collinear(p, q, r)) {
        std::cout << "三点共线" << std::endl;
    }
    
    // 计算中点 - 这是"构造"，使用double近似
    Point_2 mid = CGAL::midpoint(p, r);
    std::cout << "中点: (" << mid.x() << ", " << mid.y() << ")" << std::endl;
    
    return 0;
}

过滤机制：效率与正确性的平衡

精确计算通常比浮点计算慢得多。CGAL使用**过滤（Filtering）**技术来平衡效率和正确性：

过滤机制工作流程

输入: 一个几何谓词（如"点是否在三角形内"）
  │
  ▼
┌─────────────────┐
│ 步骤1: 快速浮点计算 │  ← 使用double快速计算
│ 并估计误差范围      │
└─────────────────┘
  │
  ▼
误差范围是否足够小？
  │
  ├── 是 ──► 返回浮点结果  ← 快速路径（90%+的情况）
  │
  └── 否 ──► 使用精确算术重新计算  ← 慢速路径（保证正确）

这种设计使得CGAL在保持几何正确性的同时，获得了接近纯浮点计算的性能。

理念三：效率与正确性的平衡——内核选择

CGAL提供了多种内核，让开发者根据应用需求在效率和正确性之间做出选择：

内核选择指南

// 场景1：只需要基本几何操作，不关心精确性
// 适用：可视化、快速原型开发
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double> Kernel;
 
// 场景2：需要精确的几何判断，但可以接受近似的构造结果
// 适用：大多数实际应用（推荐）
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
 
// 场景3：需要完全精确的结果
// 适用：需要精确输出的算法（如CAD/CAM）
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;

性能对比示例

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <vector>
#include <chrono>
#include <iostream>
 
// 定义三种内核
typedef CGAL::Simple_cartesian<double> Simple_K;
typedef CGAL::Exact_predicates_inexact_constructions_kernel EPICK;
typedef CGAL::Exact_predicates_exact_constructions_kernel EPECK;
 
typedef Simple_K::Point_2 Simple_Point;
typedef EPICK::Point_2 EPICK_Point;
typedef EPECK::Point_2 EPECK_Point;
 
template<typename Point>
void test_orientation(const std::vector<Point>& points) {
    // 测试大量方向判断的性能
    auto start = std::chrono::high_resolution_clock::now();
    
    int count = 0;
    for (size_t i = 0; i < points.size() - 2; ++i) {
        auto result = CGAL::orientation(points[i], points[i+1], points[i+2]);
        if (result == CGAL::LEFT_TURN) ++count;
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "Time: " << duration.count() << " us, Left turns: " << count << std::endl;
}
 
int main() {
    // 生成测试数据
    std::vector<Simple_Point> simple_points;
    std::vector<EPICK_Point> epick_points;
    std::vector<EPECK_Point> epeck_points;
    
    for (int i = 0; i < 10000; ++i) {
        double x = i * 0.001;
        double y = i * 0.002;
        simple_points.emplace_back(x, y);
        epick_points.emplace_back(x, y);
        epeck_points.emplace_back(x, y);
    }
    
    std::cout << "Simple_cartesian: ";
    test_orientation(simple_points);
    
    std::cout << "EPICK: ";
    test_orientation(epick_points);
    
    std::cout << "EPECK: ";
    test_orientation(epeck_points);
    
    return 0;
}

典型性能表现（仅供参考，实际取决于硬件和编译器）：

内核	相对速度	精确性	适用场景
Simple_cartesian	1.0x	低	快速原型、可视化
EPICK	1.1x	谓词精确	大多数应用（推荐）
EPECK	10-100x	完全精确	CAD/CAM、精确输出

理念四：模块化设计——按需包含头文件

模块化架构

CGAL采用**包（Package）**作为基本组织单元。每个包专注于一个特定的计算几何领域：

CGAL包组织结构

CGAL/
├── Kernel/                    # 几何内核（点、向量、矩阵）
├── Number_types/              # 数值类型支持
├── STL_Extension/             # STL扩展工具
├── Algebraic_foundations/     # 代数基础
├── Circulator/                # 循环迭代器
├── Property_map/              # 属性映射
│
├── Convex_hull_2/             # 二维凸包
├── Convex_hull_3/             # 三维凸包
├── Triangulation_2/           # 二维三角剖分
├── Triangulation_3/           # 三维三角剖分
├── Mesh_2/                    # 二维网格生成
├── Mesh_3/                    # 三维网格生成
├── Surface_mesher/            # 曲面网格生成
├── Polygon_mesh_processing/   # 多边形网格处理
├── Surface_mesh_shortest_path/# 曲面上最短路径
├── Boolean_set_operations_2/  # 二维布尔运算
├── Minkowski_sum_2/           # 二维Minkowski和
├── Arrangement_on_surface_2/  # 曲面排列
├── Voronoi_diagram_2/         # 二维Voronoi图
└── ... (更多包)

按需包含

使用CGAL时，你只需要包含实际需要的头文件：

// 只需要二维凸包算法
#include <CGAL/convex_hull_2.h>
 
// 只需要Delaunay三角剖分
#include <CGAL/Delaunay_triangulation_2.h>
 
// 不需要包含整个CGAL库
// #include <CGAL/CGAL.h>  // 这样的头文件不存在！

这种设计的好处：

编译时间：只编译需要的部分
依赖管理：清晰的依赖关系
代码体积：最终可执行文件只包含使用的功能

1.1.4 模块化架构全景图

核心模块分类

CGAL的模块可以分为三个层次：

CGAL模块层次结构

┌─────────────────────────────────────────────────────────────┐
│                    第三层：高层算法包                         │
│  ┌─────────────┐ ┌─────────────┐ ┌─────────────────────┐   │
│  │ 网格生成    │ │ 曲面重建    │ │ 布尔运算            │   │
│  │ Mesh_2/3    │ │ Poisson_    │ │ Boolean_set_        │   │
│  │             │ │ reconstruction│ │ operations_2       │   │
│  └─────────────┘ └─────────────┘ └─────────────────────┘   │
├─────────────────────────────────────────────────────────────┤
│                    第二层：基础算法包                         │
│  ┌─────────────┐ ┌─────────────┐ ┌─────────────────────┐   │
│  │ 三角剖分    │ │ 凸包算法    │ │ 排列与Voronoi图     │   │
│  │ Triangulation│ │ Convex_hull │ │ Arrangement_2       │   │
│  │ _2/_3       │ │ _2/_3/d     │ │ Voronoi_diagram_2   │   │
│  └─────────────┘ └─────────────┘ └─────────────────────┘   │
├─────────────────────────────────────────────────────────────┤
│                    第一层：基础支撑包                         │
│  ┌─────────────┐ ┌─────────────┐ ┌─────────────────────┐   │
│  │ 几何内核    │ │ 数值类型    │ │ 数据结构            │   │
│  │ Kernel      │ │ Number_types│ │ STL_Extension       │   │
│  │             │ │ Modular_    │ │ Circulator          │   │
│  │             │ │ arithmetic  │ │ Property_map        │   │
│  └─────────────┘ └─────────────┘ └─────────────────────┘   │
└─────────────────────────────────────────────────────────────┘

第一层：基础支撑包

这些包提供了CGAL的基础设施，大多数算法包都依赖它们。

Kernel（几何内核）

内核定义了基本几何对象及其操作：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;        // 二维点
typedef K::Point_3 Point_3;        // 三维点
typedef K::Vector_2 Vector_2;      // 二维向量
typedef K::Segment_2 Segment_2;    // 二维线段
typedef K::Line_2 Line_2;          // 二维直线
typedef K::Triangle_2 Triangle_2;  // 二维三角形
typedef K::Circle_2 Circle_2;      // 二维圆

Number_types（数值类型）

CGAL支持多种数值类型，从快速的浮点数到任意精度数：

#include <CGAL/double.h>           // 标准double
#include <CGAL/Gmpq.h>             // GMP有理数（精确）
#include <CGAL/Gmpz.h>             // GMP整数（任意精度）
#include <CGAL/MP_Float.h>         // 多精度浮点
#include <CGAL/CORE_Expr.h>        // CORE表达式（精确求值）
#include <CGAL/Interval_nt.h>      // 区间算术（用于过滤）

数据结构扩展

#include <CGAL/Doubly_connected_list.h>  // 双向连通列表
#include <CGAL/Compact_container.h>       // 紧凑容器（用于网格）
#include <CGAL/Handle.h>                  // 句柄类

第二层：基础算法包

Triangulation_2/3（三角剖分）

三角剖分是计算几何中最基础的数据结构之一：

#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K> Delaunay;
typedef K::Point_2 Point_2;
 
int main() {
    Delaunay dt;  // 创建Delaunay三角剖分对象
    
    // 插入点
    dt.insert(Point_2(0, 0));
    dt.insert(Point_2(1, 0));
    dt.insert(Point_2(0, 1));
    dt.insert(Point_2(1, 1));
    dt.insert(Point_2(0.5, 0.5));
    
    // 遍历所有有限面（三角形）
    for (auto face = dt.finite_faces_begin(); 
         face != dt.finite_faces_end(); ++face) {
        std::cout << "Triangle: ";
        for (int i = 0; i < 3; ++i) {
            std::cout << "(" << face->vertex(i)->point() << ") ";
        }
        std::cout << std::endl;
    }
    
    std::cout << "Number of vertices: " << dt.number_of_vertices() << std::endl;
    std::cout << "Number of faces: " << dt.number_of_faces() << std::endl;
    
    return 0;
}

Convex_hull_2/3（凸包）

凸包计算是另一个基础算法：

#include <CGAL/convex_hull_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <vector>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
 
int main() {
    // 创建一组随机点
    std::vector<Point_2> points;
    points.push_back(Point_2(0, 0));
    points.push_back(Point_2(1, 0));
    points.push_back(Point_2(0.5, 0.5));
    points.push_back(Point_2(0, 1));
    points.push_back(Point_2(1, 1));
    points.push_back(Point_2(0.5, -0.5));
    
    // 计算凸包
    std::vector<Point_2> hull;
    CGAL::convex_hull_2(points.begin(), points.end(), std::back_inserter(hull));
    
    std::cout << "Convex hull has " << hull.size() << " vertices:" << std::endl;
    for (const auto& p : hull) {
        std::cout << "(" << p.x() << ", " << p.y() << ")" << std::endl;
    }
    
    return 0;
}

第三层：高层算法包

Mesh_2/3（网格生成）

二维和三维网格生成是CGAL的强大功能：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Delaunay_mesher_2.h>
#include <CGAL/Delaunay_mesh_face_base_2.h>
#include <CGAL/Delaunay_mesh_vertex_base_2.h>
#include <CGAL/Delaunay_mesh_size_criteria_2.h>
 
// 定义网格类型
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_mesh_vertex_base_2<K> Vb;
typedef CGAL::Delaunay_mesh_face_base_2<K> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
typedef CGAL::Constrained_Delaunay_triangulation_2<K, Tds> CDT;
typedef CGAL::Delaunay_mesh_size_criteria_2<CDT> Criteria;
typedef CGAL::Delaunay_mesher_2<CDT, Criteria> Mesher;
 
typedef CDT::Vertex_handle Vertex_handle;
typedef CDT::Point Point;
 
int main() {
    CDT cdt;
    
    // 定义一个矩形边界
    Vertex_handle va = cdt.insert(Point(-1, -1));
    Vertex_handle vb = cdt.insert(Point(1, -1));
    Vertex_handle vc = cdt.insert(Point(1, 1));
    Vertex_handle vd = cdt.insert(Point(-1, 1));
    
    // 添加约束边（边界）
    cdt.insert_constraint(va, vb);
    cdt.insert_constraint(vb, vc);
    cdt.insert_constraint(vc, vd);
    cdt.insert_constraint(vd, va);
    
    // 创建网格生成器并设置参数
    Mesher mesher(cdt);
    mesher.set_criteria(Criteria(0.125, 0.5));  // 形状标准，最大单元大小
    mesher.refine_mesh();  // 执行网格细化
    
    std::cout << "Number of vertices: " << cdt.number_of_vertices() << std::endl;
    
    return 0;
}

Polygon_mesh_processing（多边形网格处理）

这是CGAL 4.7+引入的现代网格处理包：

#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <iostream>
#include <string>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
 
namespace PMP = CGAL::Polygon_mesh_processing;
 
int main(int argc, char* argv[]) {
    // 从文件读取网格
    std::string filename = (argc > 1) ? argv[1] : "data/elephant.off";
    Mesh mesh;
    
    if (!PMP::IO::read_polygon_mesh(filename, mesh)) {
        std::cerr << "Error: cannot read file " << filename << std::endl;
        return 1;
    }
    
    std::cout << "Input mesh:" << std::endl;
    std::cout << "  Vertices: " << mesh.number_of_vertices() << std::endl;
    std::cout << "  Faces: " << mesh.number_of_faces() << std::endl;
    std::cout << "  Edges: " << mesh.number_of_edges() << std::endl;
    
    // 确保所有面都是三角形
    PMP::triangulate_faces(mesh);
    
    std::cout << "After triangulation:" << std::endl;
    std::cout << "  Faces: " << mesh.number_of_faces() << std::endl;
    
    return 0;
}

包之间的依赖关系

理解包之间的依赖关系有助于你选择合适的头文件：

典型依赖关系示例

Surface_mesh_shortest_path/
├── 依赖: Surface_mesh 或 Polyhedron_3（网格数据结构）
├── 依赖: Kernel（几何内核）
└── 依赖: BGL（Boost Graph Library，用于图算法）

Polygon_mesh_processing/
├── 依赖: Surface_mesh / Polyhedron_3 / OpenMesh
├── 依赖: Kernel
├── 依赖: Principal_component_analysis（用于某些算法）
└── 依赖: Solver_interface（用于需要求解器的算法）

Mesh_3/
├── 依赖: Triangulation_3
├── 依赖: Kernel
├── 依赖: Mesh_2（某些功能）
└── 依赖: ImageIO（如果需要从图像生成网格）

如何选择需要的包

面对众多的CGAL包，选择合适包的策略：

明确你的需求：
- 需要二维还是三维？
- 输入是点云还是已有网格？
- 输出需要什么质量？
查阅官方文档：
- 每个包都有详细的文档和示例
- 从简单示例开始，逐步深入
参考示例代码：
- examples/ 目录下有每个包的使用示例
- 从最接近你需求的示例开始修改
选择指南：

你的需求	推荐的包
从点云重建曲面	`Poisson_surface_reconstruction_3`
生成体网格	`Mesh_3`
网格简化/细分	`Polygon_mesh_processing`
计算测地线	`Surface_mesh_shortest_path`
多边形布尔运算	`Boolean_set_operations_2`
点定位	`Triangulation_2/3`

1.1.5 如何阅读本书

本书采用渐进式学习的方法，从基础概念到高级应用，逐步深入。

初学者路线图

如果你是CGAL的初学者，建议按照以下路径学习：

初学者学习路线图

第1阶段：基础入门（第1-3章）
├── 第1章：CGAL简介与设计理念
│   └── 理解CGAL是什么，为什么选择CGAL
├── 第2章：几何内核详解
│   └── 掌握点、向量、内核类型的使用
└── 第3章：第一个CGAL项目
    └── 学习如何配置CMake，编译运行程序

第2阶段：核心算法（第4-7章）
├── 第4章：三角剖分
├── 第5章：凸包与Voronoi图
├── 第6章：网格生成
└── 第7章：多边形处理

第3阶段：高级应用（第8-12章）
├── 第8章：曲面重建
├── 第9章：网格处理算法
├── 第10章：空间搜索与定位
├── 第11章：排列与布尔运算
└── 第12章：实际项目案例

不同应用场景的学习重点

根据你的应用领域，可以有不同的学习重点：

计算机图形学/游戏开发

重点学习内容：

三角剖分和网格生成（第4、6章）
多边形网格处理（第7、9章）
空间搜索结构（第10章）
曲面重建（第8章）

科学计算/有限元分析

重点学习内容：

高质量网格生成（第6章）
数值稳定性（第2章）
三维数据结构（第4章）

机器人学/路径规划

重点学习内容：

排列与构型空间（第11章）
Minkowski和计算
最短路径算法（Surface_mesh_shortest_path）
碰撞检测相关算法

GIS/地图应用

重点学习内容：

二维布尔运算（第11章）
二维三角剖分（第4章）
Voronoi图（第5章）

从示例到源码的阅读方法

CGAL的代码库非常庞大，学会高效阅读源码很重要：

1. 从示例开始

每个CGAL包都有配套的示例代码：

PackageName/
└── examples/PackageName/
    ├── example1.cpp      # 基础示例
    ├── example2.cpp      # 进阶示例
    └── CMakeLists.txt    # 构建配置

2. 理解头文件结构

// 典型的CGAL头文件包含层次
#include <CGAL/PackageName/Algorithm.h>  // 算法入口
// 这会自动包含：
//   - CGAL/PackageName/internal/Helper.h  // 内部辅助函数
//   - CGAL/Kernel/Point_2.h               // 依赖的内核类型
//   - CGAL/Number_types/Gmpq.h            // 依赖的数值类型

3. 阅读源码的技巧

先读文档：每个类都有详细的Doxygen注释
关注概念（Concept）：CGAL大量使用C++概念来描述接口要求
从具体实例入手：先理解一个具体内核的实现，再推广到泛型
使用IDE的跳转功能：现代IDE可以方便地跳转到定义

4. 调试技巧

// 启用CGAL断言（在Debug模式下）
#define CGAL_DEBUG 1
#include <CGAL/assertions.h>
 
// 自定义错误处理
CGAL::set_error_handler([](const char* type, const char* expr, 
                           const char* file, int line, const char* msg) {
    std::cerr << "CGAL Error: " << type << std::endl;
    std::cerr << "  Expression: " << expr << std::endl;
    std::cerr << "  Location: " << file << ":" << line << std::endl;
    if (msg) std::cerr << "  Message: " << msg << std::endl;
    // 根据需要处理错误
});

1.1.6 你的第一个CGAL程序

让我们从一个完整的、可编译运行的程序开始。这个程序展示了CGAL的基本用法：创建几何对象、计算距离、使用不同内核。

完整代码

// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
// 第一个CGAL程序：基础几何操作演示
 
#include <CGAL/Simple_cartesian.h>                              // 简单笛卡尔内核（快速但不精确）
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> // 精确谓词内核（推荐）
#include <CGAL/Point_2.h>                                       // 二维点类
#include <CGAL/Point_3.h>                                       // 三维点类
#include <CGAL/squared_distance_2.h>                            // 二维平方距离计算
#include <CGAL/squared_distance_3.h>                            // 三维平方距离计算
#include <iostream>                                             // 标准输入输出
#include <vector>                                               // 标准向量容器
 
// 定义类型别名，简化代码
// 使用精确谓词内核（推荐用于大多数应用）
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
// 从内核中获取二维点类型
typedef Kernel::Point_2 Point_2;
// 从内核中获取三维点类型
typedef Kernel::Point_3 Point_3;
// 从内核中获取二维向量类型
typedef Kernel::Vector_2 Vector_2;
 
int main() {
    // ============================================================
    // 第一部分：基础几何对象创建
    // ============================================================
    
    std::cout << "=== CGAL基础几何操作演示 ===" << std::endl << std::endl;
    
    // 创建二维点
    // Point_2的构造函数接受两个坐标值（x, y）
    Point_2 origin(0, 0);           // 原点
    Point_2 p1(3, 4);               // 点(3, 4)
    Point_2 p2(6, 8);               // 点(6, 8)
    
    std::cout << "【二维点操作】" << std::endl;
    std::cout << "原点: (" << origin.x() << ", " << origin.y() << ")" << std::endl;
    std::cout << "点p1: (" << p1.x() << ", " << p1.y() << ")" << std::endl;
    std::cout << "点p2: (" << p2.x() << ", " << p2.y() << ")" << std::endl;
    
    // ============================================================
    // 第二部分：距离计算
    // ============================================================
    
    // 计算两点间的平方距离
    // 使用squared_distance比distance更快（避免了开方运算）
    Kernel::FT sq_dist = CGAL::squared_distance(origin, p1);
    
    std::cout << std::endl << "【距离计算】" << std::endl;
    std::cout << "原点到p1的平方距离: " << sq_dist << std::endl;
    std::cout << "原点到p1的距离: " << CGAL::sqrt(sq_dist) << std::endl;
    
    // 验证：原点(0,0)到(3,4)的距离应该是5（勾股定理）
    // 3^2 + 4^2 = 9 + 16 = 25，sqrt(25) = 5
    std::cout << "预期距离: 5" << std::endl;
    
    // ============================================================
    // 第三部分：几何谓词（Predicate）
    // ============================================================
    
    // 谓词是CGAL中的重要概念，它进行几何判断而不构造新对象
    // 常见的谓词包括：
    // - orientation(): 判断三点的方向（左转、右转、共线）
    // - collinear(): 判断三点是否共线
    // - left_turn(): 判断是否左转
    
    std::cout << std::endl << "【几何谓词】" << std::endl;
    
    // 测试三个点的方向
    // orientation返回：CGAL::LEFT_TURN, CGAL::RIGHT_TURN, 或 CGAL::COLLINEAR
    auto orient = CGAL::orientation(origin, p1, p2);
    std::cout << "原点 -> p1 -> p2 的方向: ";
    if (orient == CGAL::LEFT_TURN) {
        std::cout << "左转 (LEFT_TURN)" << std::endl;
    } else if (orient == CGAL::RIGHT_TURN) {
        std::cout << "右转 (RIGHT_TURN)" << std::endl;
    } else {
        std::cout << "共线 (COLLINEAR)" << std::endl;
    }
    
    // 因为(0,0), (3,4), (6,8)在同一条直线上（斜率都是4/3），所以应该是共线
    
    // 测试共线判断
    bool is_collinear = CGAL::collinear(origin, p1, p2);
    std::cout << "三点是否共线: " << (is_collinear ? "是" : "否") << std::endl;
    
    // ============================================================
    // 第四部分：三维点操作
    // ============================================================
    
    std::cout << std::endl << "【三维点操作】" << std::endl;
    
    // 创建三维点
    Point_3 p3d_1(0, 0, 0);     // 原点
    Point_3 p3d_2(1, 1, 1);     // 点(1, 1, 1)
    Point_3 p3d_3(2, 2, 2);     // 点(2, 2, 2)
    
    std::cout << "3D点1: (" << p3d_1.x() << ", " << p3d_1.y() << ", " << p3d_1.z() << ")" << std::endl;
    std::cout << "3D点2: (" << p3d_2.x() << ", " << p3d_2.y() << ", " << p3d_2.z() << ")" << std::endl;
    
    // 计算三维距离
    Kernel::FT sq_dist_3d = CGAL::squared_distance(p3d_1, p3d_2);
    std::cout << "3D点1到点2的平方距离: " << sq_dist_3d << std::endl;
    // 预期：1^2 + 1^2 + 1^2 = 3
    
    // ============================================================
    // 第五部分：批量操作
    // ============================================================
    
    std::cout << std::endl << "【批量点处理】" << std::endl;
    
    // 创建一组点
    std::vector<Point_2> points;
    points.push_back(Point_2(0, 0));
    points.push_back(Point_2(1, 0));
    points.push_back(Point_2(0.5, 1));
    points.push_back(Point_2(0.5, 0.3));
    
    // 计算所有点到原点的距离
    std::cout << "各点到原点的距离:" << std::endl;
    for (size_t i = 0; i < points.size(); ++i) {
        Kernel::FT d = CGAL::squared_distance(origin, points[i]);
        std::cout << "  点" << i << " (" << points[i].x() << ", " << points[i].y() 
                  << "): 平方距离 = " << d << std::endl;
    }
    
    // ============================================================
    // 第六部分：类型转换
    // ============================================================
    
    std::cout << std::endl << "【类型转换】" << std::endl;
    
    // 将CGAL类型转换为标准double
    double x_coord = CGAL::to_double(p1.x());
    double y_coord = CGAL::to_double(p1.y());
    std::cout << "p1的double坐标: (" << x_coord << ", " << y_coord << ")" << std::endl;
    
    // ============================================================
    // 总结
    // ============================================================
    
    std::cout << std::endl << "=== 演示结束 ===" << std::endl;
    std::cout << "这个程序展示了CGAL的基础用法：" << std::endl;
    std::cout << "1. 创建二维和三维点" << std::endl;
    std::cout << "2. 计算点之间的距离" << std::endl;
    std::cout << "3. 使用几何谓词进行判断" << std::endl;
    std::cout << "4. 批量处理点集" << std::endl;
    std::cout << "5. 类型转换" << std::endl;
    
    return 0;
}

编译和运行

使用CMake（推荐）

创建 CMakeLists.txt：

# 指定最低CMake版本
cmake_minimum_required(VERSION 3.12...3.31)
# 定义项目名称
project(FirstCGALProgram)
 
# 查找CGAL包
find_package(CGAL REQUIRED OPTIONAL_COMPONENTS Core)
 
# 创建可执行文件
create_single_source_cgal_program("first_cgal_program.cpp")

编译步骤：

# 创建构建目录
mkdir build && cd build
 
# 配置（假设CGAL源码在/path/to/cgal）
cmake -DCGAL_DIR=/path/to/cgal ..
 
# 编译
make
 
# 运行
./first_cgal_program

直接编译（简单测试）

如果你已经安装了CGAL头文件：

# 编译（需要C++17或更高版本）
g++ -std=c++17 -I/path/to/cgal/include first_cgal_program.cpp -o first_cgal_program -lmpfr -lgmp
 
# 运行
./first_cgal_program

预期输出

=== CGAL基础几何操作演示 ===

【二维点操作】
原点: (0, 0)
点p1: (3, 4)
点p2: (6, 8)

【距离计算】
原点到p1的平方距离: 25
原点到p1的距离: 5
预期距离: 5

【几何谓词】
原点 -> p1 -> p2 的方向: 共线 (COLLINEAR)
三点是否共线: 是

【三维点操作】
3D点1: (0, 0, 0)
3D点2: (1, 1, 1)
3D点1到点2的平方距离: 3

【批量点处理】
各点到原点的距离:
  点0 (0, 0): 平方距离 = 0
  点1 (1, 0): 平方距离 = 1
  点2 (0.5, 1): 平方距离 = 1.25
  点3 (0.5, 0.3): 平方距离 = 0.34

【类型转换】
p1的double坐标: (3, 4)

=== 演示结束 ===
这个程序展示了CGAL的基础用法：
1. 创建二维和三维点
2. 计算点之间的距离
3. 使用几何谓词进行判断
4. 批量处理点集
5. 类型转换

1.1.7 常见问题与故障排除

问题1：找不到CGAL头文件

症状：

fatal error: CGAL/Simple_cartesian.h: No such file or directory

解决方案：

确认CGAL已正确下载或安装
在CMakeLists.txt中正确设置CGAL_DIR：
```
cmake -DCGAL_DIR=/path/to/cgal ..
```

或者直接指定包含路径：

include_directories(/path/to/cgal/include)

问题2：链接错误（undefined reference）

症状：

undefined reference to `CGAL::assertion_fail(...)`

解决方案：

CGAL 5.0+是header-only，通常不需要链接。但如果使用某些特定功能，可能需要链接GMP和MPFR：

find_package(GMP REQUIRED)
find_package(MPFR REQUIRED)
target_link_libraries(your_target gmp mpfr)

问题3：编译时间过长

原因：

CGAL大量使用模板，实例化需要时间
包含不必要的头文件

优化建议：

使用前向声明减少头文件包含：

// 在头文件中使用前向声明
namespace CGAL {
    template<typename K> class Point_2;
}

使用显式模板实例化（对于大型项目）：

// 在.cpp文件中显式实例化常用类型
template class CGAL::Delaunay_triangulation_2<Kernel>;

使用预编译头（PCH）：

target_precompile_headers(your_target PRIVATE 
    <CGAL/Exact_predicates_inexact_constructions_kernel.h>
)

问题4：运行时断言失败

症状：

CGAL ERROR: assertion violation!

解决方案：

检查输入数据的有效性（如重复的顶点、退化的几何体）
在Debug模式下运行以获取更多信息

使用try-catch捕获CGAL异常：

try {
    // CGAL操作
} catch (const CGAL::Assertion_exception& e) {
    std::cerr << "CGAL assertion failed: " << e.what() << std::endl;
}

问题5：精度问题

症状：算法产生意外结果或崩溃

解决方案：

切换到更精确的内核：

// 从
typedef CGAL::Simple_cartesian<double> Kernel;
// 改为
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;

检查输入数据的数值范围，避免过大或过小的坐标值
使用CGAL::Lazy_exact_nt进行惰性精确计算

获取帮助

如果你遇到无法解决的问题：

查阅官方文档：https://doc.cgal.org/
查看示例代码：每个包都有配套的示例
搜索邮件列表：cgal-discuss@inria.fr
GitHub Issues：https://github.com/CGAL/cgal/issues
Stack Overflow：使用cgal标签提问

1.1.8 本章小结

本章介绍了CGAL的基础知识和设计理念，让我们回顾一下重点内容：

核心概念

CGAL是什么：一个开源的C++计算几何算法库，提供高效、可靠的几何算法实现
历史演进：从1995年启动到2020年转为header-only库，CGAL不断演进以适应现代C++开发
设计理念：
- 泛型编程：算法与数据类型解耦，提高代码复用性
- 稳健计算：精确谓词与过滤机制保证几何正确性
- 效率与正确性平衡：多种内核供不同场景选择
- 模块化设计：按需包含，减少依赖
架构层次：
- 第一层（基础）：Kernel、Number_types、数据结构
- 第二层（算法）：Triangulation、Convex_hull、Arrangement
- 第三层（应用）：Mesh_generation、Surface_reconstruction、PMP

关键技能

能够编写和编译第一个CGAL程序
理解不同内核的区别和选择方法
掌握几何谓词的概念和使用
了解CGAL的模块化组织结构

下一步

在下一章中，我们将深入探讨几何内核，这是CGAL的基石。你将学习：

内核的详细分类和选择指南
点、向量、矩阵等几何对象的操作
如何自定义和扩展内核
数值类型和精度控制

1.1.9 练习

练习1：环境搭建

目标：成功编译并运行本章的第一个CGAL程序

步骤：

下载或克隆CGAL源码
创建CMakeLists.txt
编译程序
运行并验证输出

验证标准：程序输出与1.1.6节中的预期输出一致

练习2：内核比较

目标：比较不同内核的性能和精度

任务：

修改第一个程序，使用三种不同的内核：
- Simple_cartesian<double>
- Exact_predicates_inexact_constructions_kernel
- Exact_predicates_exact_constructions_kernel
对每种内核，测试以下操作：
- 创建10000个随机点
- 计算所有点对之间的距离
- 进行10000次方向判断
记录每种内核的执行时间

思考问题：

为什么EPICK和Simple_cartesian的速度接近？
EPECK在什么场景下是必需的？

练习3：几何谓词探索

目标：深入理解CGAL的几何谓词

任务：

编写程序测试以下谓词：

CGAL::orientation()      // 三点方向
CGAL::collinear()        // 共线判断
CGAL::left_turn()        // 左转判断
CGAL::right_turn()       // 右转判断
CGAL::coplanar()         // 共面判断（3D）

创建测试用例，包括：
- 一般位置（无三点共线）
- 退化情况（多点共线）
- 接近退化的情况
比较不同内核对这些情况的处理

练习4：探索CGAL包

目标：熟悉CGAL的模块化结构

任务：

浏览CGAL源码目录，列出你感兴趣的5个包
对每个包：
- 阅读包的doc/目录下的描述
- 查看examples/目录下的示例代码
- 尝试编译并运行至少一个示例
创建一个表格，总结这些包的功能和依赖关系

练习5：距离计算函数

目标：练习CGAL的基本几何操作

任务：编写一个函数，计算一个点到一组点中最近点的距离：

// 函数原型
double find_min_distance(const Point_2& query, 
                         const std::vector<Point_2>& points);
 
// 要求：
// 1. 使用CGAL的squared_distance提高效率
// 2. 处理points为空的情况
// 3. 返回实际距离（不是平方距离）

扩展：

修改函数返回最近点的索引
添加一个阈值参数，只返回距离小于阈值的点
使用空间搜索结构（如Kd-tree）优化大规模数据

练习6：阅读源码

目标：学习阅读CGAL源码

任务：

找到squared_distance函数的定义位置
阅读其实现，理解它是如何工作的
追踪它使用的其他CGAL组件
写一篇简短的总结（200-300字），描述：
- 函数的位置和文件路径
- 主要实现逻辑
- 使用的关键技术

恭喜！ 你已经完成了CGAL的第一章学习。通过本章，你了解了CGAL的历史、设计理念和基本用法。这些知识将为你后续学习更复杂的算法打下坚实基础。

在继续下一章之前，建议完成至少练习1和练习2，以确保你的开发环境配置正确，并对CGAL的基本概念有直观理解。

Chunibyo

Explorer

1.1 CGAL简介与设计理念

1.1.1 CGAL是什么？ §

一个生活中的类比 §

CGAL的核心特点 §

谁在使用CGAL？ §

1.1.2 历史演进：从欧几里得到现代计算几何 §

1995年：项目的诞生 §

版本演进里程碑 §

从”有库”到”Header-only”的革命（5.0版本） §

传统库模式的痛点 §

Header-only的优势 §

当前架构特点（CGAL 6.x） §

1.1.3 设计理念深度解读 §

理念一：泛型编程——算法与数据结构解耦 §

什么是泛型编程？ §

CGAL中的泛型编程 §

类比：乐高积木 §

理念二：稳健计算——精确谓词与过滤机制 §

计算几何的数值挑战 §

CGAL的解决方案：精确谓词 §

过滤机制：效率与正确性的平衡 §

理念三：效率与正确性的平衡——内核选择 §

内核选择指南 §

性能对比示例 §

理念四：模块化设计——按需包含头文件 §

模块化架构 §

按需包含 §

1.1.4 模块化架构全景图 §

核心模块分类 §

第一层：基础支撑包 §

Kernel（几何内核） §

Number_types（数值类型） §

数据结构扩展 §

第二层：基础算法包 §

Triangulation_2/3（三角剖分） §

Convex_hull_2/3（凸包） §

第三层：高层算法包 §

Mesh_2/3（网格生成） §

Polygon_mesh_processing（多边形网格处理） §

包之间的依赖关系 §

如何选择需要的包 §

1.1.5 如何阅读本书 §

初学者路线图 §

不同应用场景的学习重点 §

计算机图形学/游戏开发 §

科学计算/有限元分析 §

机器人学/路径规划 §

GIS/地图应用 §

从示例到源码的阅读方法 §

1. 从示例开始 §

2. 理解头文件结构 §

3. 阅读源码的技巧 §

4. 调试技巧 §

1.1.6 你的第一个CGAL程序 §

完整代码 §

编译和运行 §

使用CMake（推荐） §

直接编译（简单测试） §

预期输出 §

1.1.7 常见问题与故障排除 §

问题1：找不到CGAL头文件 §

问题2：链接错误（undefined reference） §

问题3：编译时间过长 §

问题4：运行时断言失败 §

问题5：精度问题 §

获取帮助 §

1.1.8 本章小结 §

核心概念 §

关键技能 §

下一步 §

1.1.9 练习 §

练习1：环境搭建 §

练习2：内核比较 §

练习3：几何谓词探索 §

练习4：探索CGAL包 §

练习5：距离计算函数 §

练习6：阅读源码 §

Graph View

1.1.1 CGAL是什么？

一个生活中的类比

CGAL的核心特点

谁在使用CGAL？

1.1.2 历史演进：从欧几里得到现代计算几何

1995年：项目的诞生

版本演进里程碑

从”有库”到”Header-only”的革命（5.0版本）

传统库模式的痛点

Header-only的优势

当前架构特点（CGAL 6.x）

1.1.3 设计理念深度解读

理念一：泛型编程——算法与数据结构解耦

什么是泛型编程？

CGAL中的泛型编程

类比：乐高积木

理念二：稳健计算——精确谓词与过滤机制

计算几何的数值挑战

CGAL的解决方案：精确谓词

过滤机制：效率与正确性的平衡

理念三：效率与正确性的平衡——内核选择

内核选择指南

性能对比示例

理念四：模块化设计——按需包含头文件

模块化架构

按需包含

1.1.4 模块化架构全景图

核心模块分类

第一层：基础支撑包

Kernel（几何内核）

Number_types（数值类型）

数据结构扩展

第二层：基础算法包

Triangulation_2/3（三角剖分）

Convex_hull_2/3（凸包）

第三层：高层算法包

Mesh_2/3（网格生成）

Polygon_mesh_processing（多边形网格处理）

包之间的依赖关系

如何选择需要的包

1.1.5 如何阅读本书

初学者路线图

不同应用场景的学习重点

计算机图形学/游戏开发

科学计算/有限元分析

机器人学/路径规划

GIS/地图应用

从示例到源码的阅读方法

1. 从示例开始

2. 理解头文件结构

3. 阅读源码的技巧

4. 调试技巧

1.1.6 你的第一个CGAL程序

完整代码

编译和运行

使用CMake（推荐）

直接编译（简单测试）

预期输出

1.1.7 常见问题与故障排除

问题1：找不到CGAL头文件

问题2：链接错误（undefined reference）

问题3：编译时间过长

问题4：运行时断言失败

问题5：精度问题

获取帮助

1.1.8 本章小结

核心概念

关键技能

下一步

1.1.9 练习

练习1：环境搭建

练习2：内核比较

练习3：几何谓词探索

练习4：探索CGAL包

练习5：距离计算函数

练习6：阅读源码