对论文Triangulation by Ear Clipping 的理解
不涉及带孔洞的多边形及多边形迭代
问就是功能不需要
声明：在本学习笔记的写作过程中，没有一只猫猫受到实际伤害。
（包括赛博猫猫在内）
引入
计算机图形学的多边形分解问题
简单多边形定义
定义一个简单多边形为由从
到
的
个点组成的有序序列。两相邻顶点之间以边
相连，且起点和终点之间以边
相连。简单多边形的每个顶点有且仅有两条边，简单多边形的任意两条边仅在顶点处相交。简单多边形和复杂多边形的对比如图所示
左侧多边形为简单多边形。中间的多边形的顶点1有两条以上边，不为简单多边形。右侧多边形中连接顶点1和顶点4的边与其他边在非顶点处相交，该多边形不为简单多边形。
在一个简单多边形中，当遍历边缘时，多边形内部的有限区域总处于遍历方向同一侧。假设以逆时针方向遍历例图中的简单多边形边缘，则多边形内部区域始终处于遍历方向左侧。
多边形三角化算法
将简单多边形分解为多个三角形的过程叫做多边形三角化。对具有个顶点的任意多边形进行三角化分解都会得到
个三角形。在诸多算法中复杂度为)
的ear clipping算法算是最简单又好用的一个，其他复杂度更低的算法也存在，不过会比ear clipping更难实现。
Ear Clipping算法
下文用猫耳朵指代ear 用咔耳朵算法指代ear clipping）
我觉得论文作者也会赞同的 除了猫奴还有谁会看到三角形就想到尖尖耳朵呢）
定义
猫猫耳朵
多边形的一只猫猫耳朵是由三个相邻顶点
构成的三角形，其中
是三角形凸出的顶点，在该顶点处三角形的内角角度小于
。作一条连接点
的辅助线，该线段完全位于多边形内部。这只猫猫耳朵只含有构成耳朵的三个顶点，不包含多边形的其他顶点。在计算机几何学术语里把连接点的辅助线叫做多边形的一条对角线，把顶点叫做耳朵尖（猫猫的耳朵根根和耳朵尖尖，懂得都懂）。一个三角形就是一只猫猫耳朵，三角形的任意一个顶点都可以是耳朵尖尖。
有四条边及以上的多边形拥有至少两只不重叠的耳朵，这就提供给我们一个递归实现多边形三角化的思路。若在含有
个顶点的多边形内确定并移除一个三角形，移除后的多边形具有
个顶点。重复该过程，即是复杂度为)
的三角化算法。
咔耳朵算法
好消息：咔耳朵算法的复杂度可以降到
坏消息：难的步骤要来了
step1
首先，将多边形以双链表形式存储，以便快速咔掉耳朵尖尖。这个步骤的复杂度是)
。
step2
其次，对顶点进行迭代，分出各个不重叠的猫猫耳朵。对于每个顶点
和该顶点对应的三角形
，测试多边形的其他顶点是否位于该三角形中。该索引对取模，所以
且
。如果三角形内不包含多边形的其他顶点 ，我们就喜提了一只猫猫耳朵！如果三角形内至少含有多边形的一个顶点，它就不是猫猫耳朵。在三角形包容测试中效率更高的三角化方法是只考虑反射点。反射点指由两条边构成的角度大于的内部角的顶点。多边形的数据结构包含四个同时共用一个存储数组的双链表，而非动态分配和释放内存的标准列表数据结构。使用循环链表存储多边形的所有顶点，线性表存储凸顶点，另一个线性表存储反射点，另一个循环链表存储耳朵尖尖。
step3
当完成对存储反射点和耳朵尖尖的数据列表初始化后，就可以一只接一只地咔掉猫猫耳朵了！若是已经被咔掉的猫猫耳朵，那么与其相邻的顶点
和顶点
的边的参数随之变化。若一相邻顶点是凸出点，则其仍是凸出点。若一相邻顶点是耳朵，在移除后它可能就不再是耳朵了。若为反射点，则可能变为凸出点或耳朵。在移除后，若存在一凸出的相邻顶点，则必须通过遍历反射点和测试三角形内是否包含点来验证该相邻顶点是否为耳朵。整个过程的复杂度是
算法示例
以第一张图的简单多边形为例
凸出顶点的初始列表为
反射顶点的初始列表为
耳朵尖尖的初始列表为
（再复习一遍，耳朵尖尖=这个点是凸出点+和这个点相邻的两个点的连线完全在多边形内部）
① 把耳朵尖尖
对应的猫猫耳朵咔掉，那么三角化咔出来的第一个三角形就是
。
与
相邻的顶点
初始时是反射点，咔掉
后仍是反射点。与相邻的顶点
初始时是耳朵尖尖，咔掉后仍是耳朵尖尖。可知反射点列表
维持原状，但耳朵尖尖列表变为
。
② 然后把顶点
对应的耳朵咔掉，可得三角化后的又一个三角形
。
与相邻的顶点初始时是反射点，咔掉后仍是反射点。与相邻的顶点
初始时是反射点，咔掉
后变成了凸出点，经过测试后确定为耳朵尖尖，故从反射点列表中移除，反射点列表变为
。但耳朵尖尖列表变为。
如此重复直到将多边形全部三角化，得到三角形
