1
什么是CGAL？
CGAL项目成立于1996年，由欧洲和以色列的8个研究机构组成的联合体负责研发。CGAL以C++库的形式提供对高效可靠的几何算法的便捷访问。CGAL用于需要几何计算的各个领域，如地理信息系统、计算机辅助设计、分子生物学、医学成像、计算机图形和机器人技术。
正如C++的开发者们或多或少都应该了解一点Boost库一样，作为一名HMI的开发人员，了解一些常用的计算几何算法，对提升自己的开发效率也是大有裨益。而CGAL(The Computational Geometry Algorithms Library)正是一个集合了绝大部分的计算几何算法的一个C++库。
CGAL支持Windows、Linux以及MacOS系统，部分功能需要依赖Boost库支持，部分功能依赖 Eigen库（一个用于线性代数，向量及矩阵运算的C++模板库）。CGAL支持GPL、LGPL协议，同时也可从GeometryFactory购买商用协议。
2
CGAL能做什么？
那么，让我们来具体看一下，CGAL都提供了哪些功能：
凸包算法：即Convex Hull Algorithms，以二维空间距离，给定一组点，从其中选择部分点构成凸多边形，该多边形可以将其余点全部包含在内的算法。CGAL提供了2D和3D的凸包算法的集中不同实现，使用者可根据实际情况选择合适的算法。凸包算法可用在像构建多边形碰撞轮廓（PhyX引擎中的复杂碰撞）功能上。
多边形算法：例如2D空间的可见性判断，多边形集合运算（相交，包含等关系的判断）。
三角化和德劳内三角化(Triangulations and Delaunay Triangulations)：三角剖分是计算几何中特别重要的一个部分，同时也是HMI程序开发中经常用得到的一个功能。所谓三角剖分，就是将给定的多边形拆分成为多个三角形，其中的三角形要么不重合，要么仅有一条公共边。
2D及3D的Mesh生成：利用Delaunay refinement算法，重建2D或者3D模型。
空间搜索与排序算法：例如，快速找到限定区域内，距离给定点最远及最近的点，验证射线是否与多边形相交，两个多边形之间的最近距离等功能。
3
功能应用举例
接下来，我会以2D三角化(Triangulations and Delaunay Triangulations)的功能举例，介绍下如何使用CGAL特定模块的功能。
1. 从官方网站下载CGAL以及Boost的源码，将include文件夹下的文件配置到工程中，作为第三方的库目录。同时配置预处理器宏命令CGAL_HEADER_ONLY=1，因为CGAL本身是C++模板库，支持以Header Only的形式去使用，不需要提前编译。
2. 根据CGAL官方的样例代码，三角化的过程中两个数据是必要的。一个是需要被三角化的多边形的全部顶点，另外就是约束条件。所谓的约束条件，指的是拆分后的三角形不能跨越原有多边形的边界。如下图所示，给定多边形P1~P8。
如果在不限定约束边界的条件下，三角化后会形成如下Mesh：
这并不是我们原有期望的图形，因为多边形的轮廓已经被破坏掉了。所以我们需要增加边界限定条件，当我们增加了边约束的先顶后，重新拆分可得到如下的图形：
这正是我们希望得到的样子。
3. 三角剖分在HMI中的可能使用场景：
a) 在有关自动驾驶的HMI开发中，如果障碍物识别信息是多边形构成的轮廓，由于障碍物需要动态生成，并且多边形形状不固定，无法做更多假设，则需要实时的创建该多边形轮廓。
b) 同样是在自动驾驶HMI开发中，部分图商的高精地图的路面数据是由离散点构成的多边形轮廓，如果希望对路面进行面的渲染，则需要对其进行三角化。
除了三角化的功能外，还有像是判断给定点是否在某个多边形内部（可用于自定义区域的触摸点判断）等功能，都可以用于HMI程序的开发中。如果大家在开发HMI程序的过程中遇到跟计算几何相关的问题，不妨试一试CGAL这个库，也许会大大提升我们的开发效率哦。
