三角剖分

在几何中，三角剖分是指将平面对象细分为三角形，并且通过扩展将高维几何对象细分为单纯形。对于一个给定的点集，有很多种三角剖分，如：

三种三角剖分

OI 中的三角剖分主要指二维几何中的完美三角剖分（二维 Delaunay 三角剖分，简称 DT）。

Delaunay 三角剖分

定义

在数学和计算几何中，对于给定的平面中的离散点集，其 Delaunay 三角剖分 DT() 满足：

空圆性：DT() 是唯一的（任意四点不能共圆），在 DT() 中，任意三角形的外接圆范围内不会有其它点存在。
最大化最小角：在点集可能形成的三角剖分中，DT() 所形成的三角形的最小角最大。从这个意义上讲，DT() 是 最接近于规则化 的三角剖分。具体的说是在两个相邻的三角形构成凸四边形的对角线，在相互交换后，两个内角的最小角不再增大。

一个显示了外接圆的 Delaunay 三角剖分

性质

最接近：以最接近的三点形成三角形，且各线段（三角形的边）皆不相交。
唯一性：不论从区域何处开始构建，最终都将得到一致的结果（点集中任意四点不能共圆）。
最优性：任意两个相邻三角形构成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小角度不会变化。
最规则：如果将三角剖分中的每个三角形的最小角进行升序排列，则 Delaunay 三角剖分的排列得到的数值最大。
区域性：新增、删除、移动某一个顶点只会影响邻近的三角形。
具有凸边形的外壳：三角剖分最外层的边界形成一个凸多边形的外壳。

构造 DT 的分治算法

DT 有很多种构造算法，在的构造算法中，分治算法是最易于理解和实现的。

分治构造 DT 的第一步是将给定点集按照坐标升序排列，如下图是排好序的大小为的点集。

排好序的大小为 10 的点集

一旦点集有序，我们就可以不断地将其分成两个部分（分治），直到子点集大小不超过。然后这些子点集可以立刻剖分为一个三角形或线段。

分治为包含 2 或 3 个点的点集

然后在分治回溯的过程中，已经剖分好的左右子点集可以依次合并。合并后的剖分包含 LL-edge（左侧子点集的边）。RR-edge（右侧子点集的边），LR-edge（连接左右剖分产生的新的边），如图 LL-edge（灰色），RR-edge（红色），LR-edge（蓝色）。对于合并后的剖分，为了维持 DT 性质，我们可能需要删除部分 LL-edge 和 RR-edge，但我们在合并时不会增加 LL-edge 和 RR-edge。

edge