hanyeah

多边形

多边形（polygon）是闭合的折线。每一个点Pi叫做多边形的顶点（vertex），每一条线段叫做多边形的边。

如果不相邻的边不相交，则多边形是简单多边形。

如果对于多边形内的任一两点，连接着这两点的线段也在多边形内，则多边形是凸多边形（convex）。

非凸多边形被称为凹多边形（concave）。

多边形分解

顶点的可见性

其中一个关键的概念是顶点之间的可见性。

两个顶点Vi和Vj被称为是互相可见的，如果连接它们的开放线段严格地位于多边形内。也就是说，从一个顶点到另一个顶点之间必须有一个清晰的视线，没有任何的多边形部分会遮挡视线，甚至没有一个顶点会阻挡视线。

当两个顶点是互相可见时，连接它们的线段叫做多边形的对角线（diagonal）。

如果两条共用一个顶点的边之间的夹角（从多边形内测量）小于弧度π，那么这个顶点就被称为凸顶点。这个夹角称为位于顶点上的内角。

如果共用一个顶点的两条边位于同一条直线上，这个顶点就叫做共线顶点。

如果位于一个顶点上的内角大于弧度π，那么这个顶点称为优角。

顶点Vi-1和Vi+1之间的可见性。

如果Vi是一个优角顶点，那么Vi-1和Vi+1一定不是互相可见的。

如果Vi是一个凸顶点，并且不存在其他的多边形顶点位于三角形（Vi-1，Vi，Vi+1）上，那么Vi-1和Vi+1就是互相可见的。算法复杂度是O(n²)，n是顶点个数。

事实上，只需要检测三角形对于优角顶点的包含性就足够了。算法的事件复杂度是O(n*r)，n是顶点个数，r是优角个数。

 耳，耳尖

如果（Vi-1，Vi+1）是多边形的一条对角线（注：书上写的是Vi-1，Vi+2，应该是写错了），顶点Vi-1，Vi，Vi+1就构成多边形的一个**耳**，而Vi叫做耳尖（ear tip）。

任意两个顶点之间的可见性。

检测（Vi，Vj）(|i-j|≥2)是不是对角线的方法非常简单。这种方法的基本思想是，遍历多边形的所有边，并检测是否存在任何与线段（Vi，Vj）相交的边。不需要检测与指定的线段相邻的边（需要处理相邻的边与指定线段共线的情况）。

如果多边形有一条边与指定的线段相交，那么线段就不是一条对角线。

如果所有的边（与线段相邻的边除外）与线段都不想交，那么存在两种情况，一种是这条线是一条对角线，另一种是这条线位于多边形之外。只需要检测线段的一个端点（比如Vi）的局部表现就够了，只要线段包含于Vi±1-Vi的圆锥之内，这条线段就是一条对角线。

三角剖分（多边形分解为三角形）

设有一个具有顶点Vi（0≤i＜n）的简单多边形。这个多边形的三角剖分（triangulation）就是对这个多边形进行三角形分解。每一个三角形的顶点都是原多边形的顶点。如果分解形成的两个三角形相交，那么它们只能相交于顶点或边，而不能相交于内点。

这种处理所形成的的三角形的边必须位于多边形之内，因此这些边必须是对角线。

根据定义，所有用于三角剖分的对角线都必须是不相交的。

多边形的任何三角剖分都必须使用n-3条对角线，并包含n-2个三角形。

通过耳裁剪来实现三角剖分。

因为多边形的三角剖分与多边形的对角线相关，因此可以使用分治算法来构建三角剖分。

其思想是，找到一条对角线，沿对角线将多边形分解为两个子多边形，并对每一个子多边形进行递归处理。算法时间复杂度是O(n³)。

使用耳裁剪法，不需要搜索所有的对角线，只需要找到一个耳就够了，将对应的三角形加入列表中，从多边形中删除这个耳，并对减少的多边形进行递归处理。算法时间复杂度是O(n³)。

可以对耳裁剪法进行修改，使其成为时间复杂度为O(n²)的算法。其思想是，首先扫描一遍多边形，并跟踪记录哪些顶点是耳尖。删除一个耳，比如删除耳尖位于顶点Vi的耳，这样，顶点Vi-1和Vi+1是否是耳尖将发生改变，其它顶点是否是耳尖并不会改变（注：这里是按作者的理解写的，和书上写的不一致，中文版翻译的不好，英文原版写的是earness）。因此，每一次删除耳仅需要两次更新，以确定Vi-1和Vi+1是否是剩余的多边形的耳尖。

还有效率更高的三角剖分方法，实现起来比较复杂，这里不再深入讨论了。

效果

凸分解（凹多边形分解为凸多边形）

多边形的三角剖分是将多边形分解为凸子多边形的特殊情况，对于顶点数为n的多边形，分解得到的子多边形数为n-2。更一般的问题是将多边形分解为凸子多边形，并且使这样的子多边形数量最少。 为了获得最小数量的子多边形，最优的凸分解可能要求制定额外的点和线段，我们提到的凸分解在构建过程中仅使用对角线。

效果

一种次优但快速的凸分解

Hertel和Mehlhorn（1983）提出了一种快速而简单的次优凸分解算法。

给定一个与对角线相关的凸分解，一条对角线与顶点V有关，如果删除这条对角线将得到一个不凸的多边形（在V点非凸），那么这条对角线叫做这个顶点的基本对角线。否则，这条对角线叫做这个顶点的非基本对角线。显然，一条连接两个凸顶点的对角线是非基本对角线（注：书上写的是“顶点”而非“凸顶点”，翻译错误，英文原文用的是“convex vertices”）。如果一条对角线是顶点V的基本对角线，那么这个顶点V必须是优角顶点。然而，一个优角顶点可以是一条非基本对角线的一个端点。(注：“一条对角线是顶点V的基本对角线”是“这个顶点是优角的顶点”的充分不必要条件)。

这个算法很简单。首先三角剖分多边形，然后删除所有的非基本对角线，一次删除一条。算法的时间复杂度由三角剖分的时间复杂度决定。

一种优化凸分解 

 Keil和Snoeyink在1998年提出了一种优化凸分解算法。这种算法仅适用对角线，并且其渐进运行时间是O(nr²)级的，其中n是多边形的顶点数，r是多边形的优角顶点数。这种算法是基于动态规划（Bellman 1987）的。 算法比较复杂，不再深入讨论了，有兴趣可以阅读参考文献2。

 参考文献： 

 【1】 周长发. 计算机图形学几何工具算法详解. 电子工业出版社 2005.1 

 【2】 Philip J.Schneider David H.Eberly. Geometric Tools for Computer Graphics.