Computational Geometry Algorithms Library
世界领先的计算几何算法库，为复杂几何问题提供精确、高效的解决方案
CGAL是一个强大的C++计算几何算法库，就像是几何世界的"瑞士军刀"。它包含了从基础的点线面操作到复杂的三维重建、网格处理等上百种经过严格验证的算法。
核心理念：为科研人员和工程师提供精确、可靠、高效的几何计算工具，让复杂的几何问题变得简单易解。
在几何计算中，精度就是生命。CGAL采用精确算术和鲁棒几何谓词，确保计算结果的正确性，避免了浮点数误差导致的灾难性后果。
独特优势：基于严格的数学理论，每个算法都经过理论证明和大量测试，是工业界和学术界的首选。
CGAL包含100多个专业算法包，覆盖计算几何的各个领域
点、线、面等基本几何对象的表示和操作，提供精确的几何谓词和构造函数。
凸包计算、Delaunay三角剖分、Voronoi图、多边形操作等经典二维几何算法。
三维凸包、四面体剖分、三维Voronoi图、球面几何等三维空间算法。
表面网格生成、网格简化、网格修复、网格分割等网格处理算法。
半边数据结构、多面体表示、线性单元复形等拓扑建模工具。
空间索引、最近邻搜索、范围查询、几何优化等高效算法。
NURBS曲线、贝塞尔曲面、曲线拟合、曲面重建等参数化几何。
多边形和多面体的并、交、差等布尔运算，支持复杂几何操作。
从学术研究到工业应用，CGAL在各个领域发挥着重要作用
游戏引擎、3D建模软件、动画制作工具
计算机辅助设计、制造业、建筑设计
生物信息学、物理仿真、数值分析
GIS软件、地形分析、城市规划
路径规划、碰撞检测、机器视觉
医学图像处理、三维重建、手术规划
让我们通过一个简单的例子来看看CGAL的使用方式。下面的代码展示了如何计算二维点集的凸包：
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
int main() {
// 创建一组二维点
std::vector<Point_2> points = {
Point_2(0, 0), Point_2(1, 0), Point_2(0, 1),
Point_2(1, 1), 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 << "凸包包含 " << hull.size() << " 个顶点" << std::endl;
return 0;
}代码解释：这个例子展现了CGAL的典型使用模式 - 选择合适的几何内核，定义数据类型，然后调用算法函数。简洁而强大！
几何内核的选择：CGAL提供多种几何内核供选择。Exact_predicates_inexact_constructions_kernel是最常用的内核，它在保证谓词精确性的同时提供了良好的性能。对于需要绝对精确结果的应用，可以选择Exact_predicates_exact_constructions_kernel。
性能优化：CGAL的算法经过高度优化，但选择合适的数据结构和参数设置仍然很重要。阅读文档中的性能建议可以帮助您获得最佳性能。
欧洲多个研究机构联合发起，目标是创建一个通用的计算几何算法库。
CGAL 1.0发布，包含基础的几何内核和一些核心算法。
GeometryFactory公司成立，为CGAL提供商业支持和咨询服务。
CGAL 3.0发布，采用现代C++设计，性能和易用性大幅提升。
大部分CGAL模块采用开源许可证，促进了更广泛的应用。
CGAL 5.0发布，支持C++14/17，集成更多前沿算法。