掌握C++计算几何利器（CGAL教程：从零开始构建几何算法）

安装CGAL（以Ubuntu为例）

在开始编码前，你需要先安装 CGAL 及其依赖项。以下是在 Ubuntu 系统上的安装步骤：

sudo apt updatesudo apt install libcgal-dev libcgal-qt5-dev

对于 Windows 用户，推荐使用 vcpkg 或预编译的二进制包。macOS 用户可通过 Homebrew 安装：brew install cgal。

第一个CGAL程序：计算凸包

我们从一个经典问题入手：给定一组二维点，求它们的凸包（Convex Hull）。凸包是包含所有点的最小凸多边形。

以下是完整的 C++ 代码示例：

#include <iostream>#include <vector>#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>#include <CGAL/convex_hull_2.h>// 定义几何内核using K = CGAL::Exact_predicates_inexact_constructions_kernel;using Point = K::Point_2;int main() {    // 创建点集    std::vector<Point> points = {        Point(0, 0),        Point(1, 0),        Point(0, 1),        Point(1, 1),        Point(0.5, 0.5)    };    // 存储凸包结果    std::vector<Point> hull;    // 调用CGAL凸包算法    CGAL::convex_hull_2(points.begin(), points.end(), std::back_inserter(hull));    // 输出凸包顶点    std::cout << "凸包顶点数量: " << hull.size() << std::endl;    for (const auto& p : hull) {        std::cout << "(" << p.x() << ", " << p.y() << ")" << std::endl;    }    return 0;}

编译与运行

将上述代码保存为 convex_hull.cpp，然后使用以下命令编译（需链接 CGAL）：

g++ -o convex_hull convex_hull.cpp -lCGAL -lgmp

运行程序后，你将看到输出：

凸包顶点数量: 4(0, 0)(1, 0)(1, 1)(0, 1)

为什么选择CGAL？

• 高精度：CGAL 使用精确谓词（Exact Predicates）避免浮点误差导致的拓扑错误。
• 模块化设计：你可以只使用所需的部分，无需引入整个库。
• 工业级稳定：被广泛应用于科研与工业项目中。
• 丰富文档：官方提供详尽的用户手册和示例。

结语

通过这个简单的例子，你应该已经感受到 CGAL 的强大与易用。无论是进行学术研究还是开发商业软件，C++计算几何 能力都能因 CGAL 而大幅提升。希望这篇 CGAL入门 教程能为你打开计算几何的大门！

记住，CGAL 不仅仅是一个 几何算法库，它更是一个让你专注于问题本身而非底层实现的强大工具。现在，就去尝试构建你自己的几何应用吧！