清华大学-计算几何-多边形三角剖分

目标：将多边形剖分成三角形

1、画廊问题

问题描述：在画廊（如下图的多边形）中，如何设置哨兵可以监控整个画廊？

画廊，其中的点为哨兵

直观解：如果多边形是凸多边形或星形多边形，那么只须在中间的核设置一个即可。如果多边形不规则，那么最多n个点，即n多边形的每个顶点都设置一个哨兵，就可以将整个多边形覆盖。因此问题的解的上界为n.

然而在数学上有证明指出画廊问题是NP-Hard问题，这里不做多的赘述。

实际上，对于不规则多边形而言，最对只须n/3个点即可覆盖多边形（如下图）。

锯齿形，需要最多的哨兵。因为每三个顶点构成的三角形一定需要一个哨兵。

2、Fisk’s Proof

几个概念

扇形：一个有核点的星形多边形。每个扇形可以由一个点覆盖整个扇形。

内对角线：多边形顶点之间的内部连线

切线：某个点相切。任意一个边或切线都不是对角线

对角线的集合是连续的如果任意两条对角线不相交。

上：内对角线下：切线

三角剖分问题

多边形P的最大的连续对角线的集合称为P的三角剖分。

着色：任意一条边和内对角线连接的两个点颜色互异。

顶点着色

Fisk’s的证明指出：对于进行三角剖分后的多边形，只需3种颜色即可对它完成着色

证明：构造三角剖分图的对偶图。首先对第一个点所在的那个三角形使用三种颜色进行着色，然后从这个点移至下一个点时，我们知道这两个三角形是存在一条公共边，必有第三个顶点之间是不相连的，因此它们可以是同一种颜色。遍历这棵树，即可完成着色。
因为每个三角形的点颜色不一，对于一种颜色的点而言，它可以覆盖它所在的三角形，而多边形又是被剖分成一个个三角形，因此只要在同一种颜色的点上设置监控即可覆盖整个多边形，因此至多需要n/3个监控就可以覆盖整个多边形。

构造对偶图

对于这n/3还可以有进一步的优化：

由鸽巢原理知，对于三种颜色的点总共有n个，那么必存在一种颜色的点数是小于等于n/3的。我们只需要选取其中最小规模的那个颜色集合即可。

3、正交多边形

正交多边形至多需要n/4个点即可覆盖。

对于正交多边形，采用的是凸四边形剖分，如下：

可以根据每个凸四边形中都有两两的对角线，进行四色染色，因此至多需要n/4个点。

4、三角剖分（Triangulation）

本课程只考虑简单多边形（即相邻的边才有交点的多边形）以及中间带洞的简单多边形的三角剖分。

简单多边形

带洞的简单多边形

如下图所示不是简单多边形

非简单多边形，本课程不考虑

一些概念

耳朵：多边形的一个点，它与它相邻的两个点构成的三角形完全包含在多边形内，这个三角形称为该多边形的耳朵(ear)

嘴巴：如果多边形上一点与它相邻的两个点构成的三角形完全在多边形外，称为嘴巴(mouth)

三角剖分存在性

构造三角剖分的方法：不断地切去多边形的一个耳朵，直至它只剩下一个三角形，那么就完成了该多边形的三角剖分。

双耳定理：任意一个简单多边形一定有两个耳朵。（这个定理保证了我们在每次给多边形切去一个耳朵时一定还会有新的耳朵用于切分）

三角剖分算法

定义多边形的大小比较：（洞的数目，顶点数目）

初始化：首先找到一个凸点J（Lowest-then-Leftmost原则），然后找到与它相邻的两个点I,K并把I,K连接起来。

递归基：最终变成一个三角形（无洞）

递归假设：每次都将多边形分割成更小的简单多边形

递归：如果△IJK是一个耳朵，那么IK是一条内对角线，可切。如果IK不是内对角线，意味着中间有空洞。假设M是离线IK最远的那个点。

无论是哪种情况，沿着JM切开，我们得到的多边形总比原多边形要小。

三角剖分的性质

三角剖分不唯一

对于一个规模为n的简单多边形，它们的内对角线的数目为n-3条，构成三角剖分的三角形数目为n-2个。

对偶图：多边形中如果不带洞的，那么它的三角剖分图的对偶图是一棵树；如果原来带有洞，那么就必然有环路。

5、三角剖分：Monotone Polygon

这里只考虑不带洞的简单多边形

几个概念

单调多边形链：对于某个特定的方向，上面的顶点可以投影在该轴上有一定的次序。即这条单调链可以被视作是一个函数图像。

图中为一条单调多边形链

单调多边形：它可以分解为互补的两条链，并且这两条链沿着同一方向单调。方便起见，我们将方向取作纵向，并将两条链称为左侧链和右侧链，这两条链在最低点和最高点重合，从而构成多边形。

图中为一个单调多边形

多边形的单调性测试：判断一个多边形是否在某个方向上具有单调性。

剖分算法

整个算法分成两步：①对一个简单多边形分解成若干个单调多边形；②对每个单调多边形进行三角剖分。

下面对这两步进行分别的解释。

对单调多边形的三角剖分：扫描线算法（自顶而下）

初始化：顶点从高到低排序（假定了方向是纵向），因为已经是分成了两条有序链，那么只需要归并即可。（这里不考虑各种特殊情况）

事件点：每个顶点
数据结构：栈
每次处理的顶点：当前扫描线触及的顶点c，栈中存放的顶点t，栈中的次顶点s

算法进行时的每个步骤都满足的一组不变性，：
①、在栈中所存放的点在任何时候都是属于左或者右的同一侧。
②、这些顶点总是按照高度变化
③、在栈中存放的点任何三个定义的内角都是凹的
④、扫描点c要么和栈顶t相连要么和栈底botton相连。

算法进行时的可能性：
①、扫描点c与栈内所有点处于同侧，且它与t点和s点形成的角是凹角，这种情况下就是把c点压入栈中。

②、点c与栈中所有点同侧，但是c与t和s形成的角是凸角。此时把c和次栈顶相连，那么可以切除一个三角形。然后弹出栈顶s，持续判断此时的栈顶和次栈顶相连的角的情况，直到c与栈顶和次栈顶相连的角是凹角或者栈内的点数小于2。这个操作完成后将c点push进栈内。

③、点c与栈中所有点异侧。此时点c可以与每个栈中的点有一条内对角线，都可以切三角形。那么这时就不停的将c与栈顶次栈顶的点构成的三角形切除同时将栈顶的点pop出来，持续这个过程直到栈中只剩下一个元素。然后将栈底pop出来，并把之前碰到的第一个栈顶元素t push进去，最后将点c压入栈中。

一个实例

算法分析

正确性：我们每次切除的连线都是内对角线，都不会与之前的内对角线相交

复杂性：多边形的每一个顶点最多会参与两对的push-pop操作，线性时间。因此整个算法是线性时间。

6、Monotone Decomposition

问题描述：如何将简单多边形分解成若干个单调多边形？消除掉多边形内部的凹点。

两个概念

钟乳石点StalacTite和石笋StalagMite

分解原理：一个多边形之所以不是单调的，是因为存在这两种凹点。那么剖分的话就是将这些点消除掉。
算法：消除StalagMite（另一个类似）

算法描述：先把所有顶点按照高度排序，一旦发现有StalagMite，那么就将它之前准备好的某个顶点相连，从而把StalagMite消除。我们的目标就是要如何去维护更新这么一些能消除凹点的顶点，这些顶点又称作helper。当碰到StalagMite时，可以与helper连接，并且这条线是内对角线。因为对于一个StalagMite而言，一定会存在一个空的倒梯形如图所示，那么在StalagMite往上在梯形之内就会存在一个helper与之相连。因此，使用扫描线算法，当扫描线自上而下扫描时，我们是要预先存着可能会成为helper的点，然后在碰到StalagMite时从中找到与它相匹配的helper。