计算几何（四）

O(n^2)这种复杂度的算法还是相当慢的。多边形的三角形划分还有更高效的算法。
早在1978年就有人研究出了一种复杂度为O(n log n)的算法。
可能很多人会觉得，就像好多排序算法一样，这种对多边形进行三角形划分的算法，
是每次花O(log n)的时间找到一条对角线，然后把这个过程重复n次，
达到总体O(n log n)的时间复杂度。
实际上不是这样的。这个算法的运行过程是，
先用O(n log n)的算法把多边形划分为一些更简单的多边形，
对这些简单多边形进行三角形划分的步骤，时间复杂度为O(n)。

先定义什么是“单调多边形”。多边形的单调性，是针对某一条直线的。
先定义折线段的单调性。如果有直线L’，
使得垂直于它的每一条直线L和折线段C最多有一个交点，
也就是L和C的交集是空集或者一个点，
就说折线段C关于直线L’是严格单调的。
如果这样的直线L和折线段C的交集只有一个连通分量，
即它们的交集是空集、一个点或一条线段，
就说折线段C关于直线L’是单调的。

折线段C关于直线L’（严格）单调的几何意义是，
折线段C上的一个动点p沿折线单向前进的时候，
P在L’上的投影p’也是单向前进的，始终不会后退。

如果一个多边形P的边界可以被划分为两条折线段A和B，
并且A和B都关于直线L单调，就说多边形P是关于L单调的。
A和B的两个端点都是共享的。
有的多边形可能会关于多条直线单调，
有的多边形可能关于任何直线都不是单调的。

下边说说单调多边形的性质。
很多针对普通多边形的算法，在针对单调多边形的时候会变简单。
这是因为单调多边形有以下的重要性质：
单调多边形边界划分而成的、关于直线L单调的两条折线段上的顶点，
在直线L确定的方向上是排好序的。
比如我们确定单调性的参考直线为Y轴（直线x=0）,
那么多边形的所有定点可以在O(n)的时间复杂度内按y坐标排序：
用O(n)的时间找到多边形顶点里y最大和最小的两个定点；
这两个顶点将多边形的边界分割为两条关于直线x=0单调的折线段；
注意这两条折线段内的各个顶点已经是按照纵坐标排好序的；
然后再用O(n)的时间将两个排好序的顶点序列合并。
这样就在总体O(n)的时间内将多边形的所有定点按y坐标排好序了。

如果一个多边形在它的每个顶点附近都是单调的，那么它整体就是单调的。
从这一点出发，可以通过“切除”局部不单调的区域，
将一个不单调的多边形划分为几个小的单调多边形。

如果简单多边形有凹顶点v，和它相邻的两个顶点v-和v+，
若v-和v+的纵坐标都大于等于v的纵坐标，
或者v-和v+的纵坐标都小于等于v的纵坐标，
这样的凹顶点v就叫做多边形的一个interior cusp。
应当注意我们定义的凹顶点，其内角应该严格大于180度，
因此如果v-和v+的纵坐标都和v的纵坐标相等，v就不是凹顶点，
更不是interior cusp。interior cusp有一个重要性质：
如果一个多边形没有interior cusp，那它就是单调的。
但是满足上述条件的多边形并不一定是严格单调的。

单调多边形三角形划分的偶图不一定是一个简单的路径。
也并非连接两个单调折线段各顶点的所有对角线即构成一个三角形划分。
但单调多边形的三角形划分的确比一般多边形要简单。
如果已知一个单调多边形的单调方向，可以在O(n)的复杂度内完成三角形划分。
从而把多边形三角形划分问题的整体复杂度降低到O(n log n)。
算法细节不具体展开了。

现在已知的多边形三角形划分算法，时间复杂度最低的是O(n log*n)。
log*n是一个递归函数，
若n<=1，log*n=0;
若n>1，log*n=1+log*(log n)
即log*n的函数值m，是对整数n求m次对数使得最终结果小于1时的m值。
这个函数在n<2^65535时，取值不会大于5，因此基本上可以当成一个常量。

1998年有人发表了平均时间复杂度O(n)的算法。