计算几何---多边形三角剖分算法研究与实现（2）：

单调多边形三角剖分

         对于单调多边形的三角剖分可以在线性时间内完成，承接上一节将多边形划分为若干个单调多边形，现在需要对每个单调多边形进行三角化操作，最终完成对原多边形的三角剖分。

1.     相关概念

     单调多边形的左右链：首先找出单调多边形的Y坐标最高和最低的顶点，沿原多边形边界，在此两点左边的标识为左链，在右边的标识为右链。单独沿左链或右链，从最高顶点走向最低顶点的过程中，始终都是向下（或水平）运动，也就是说在某条链上，顶点的Y坐标是单调递减的。这也可以看作是单调多边形的一大特征。

     最高点和最低点的左右链属性该如何设定，因为单调多边形的三角剖分算法需要遍历每一个顶点，后面将详细讲述三角化算法。总之，明确最高点和最低点的左右链属性在编程中是非常重要的。但是现在很多书籍或文献在此问题上比较模糊，没有明确的规定。当然从几何理论角度来看，最高点和最低点属于左链或是右链都行，单独作为一个属性标识也可以。但是从编程角度来看，算法需要明确性，因为本文算法对现有算法做了改进，明确提出了关于最高点和最低点左右链属性设定的解决方法。

2.     算法

单调多边形的三角剖分算法和上一节多边形的单调划分算法有些类似，都需要首先对多边形顶点按照Y坐标大小降序排列，得到一个有序的链表（或者优先级队列）。从最高点到最低点遍历单调多边形的每一个顶点，根据其左右链属性执行相应的操作。同时，还需要一个链表作为辅助的数据结构。

算法描述：

输入:单调多边形M，顶点逆时针编号

输出:M的三家剖分和对角线D

算法:

S1、以顶点Y坐标降序排序，若有顶点Y坐标相同则以X坐标小的优先，得到链表L。同时确定顶点的左右链属性，最高点和最低点可以不做设置。     

S2、初始化一个链表K，将L中前两个顶点依次加入到K中，令v1指向K中第一个元素，v2指向K中最后一个元素。

S3、依次遍历L中剩余的元素e

         将e加入到K中

         If (e是L中最后一个元素，即最低点)

                   If (K中元素个数大于3)

                            将e的左右链属性设置为与v2相反

         If (e与v2不共链)

                   e与K中除第一个和最后一个顶点外的其他顶点连对角线（如果e为最后一个元素，则倒数第二个顶点也除外）

                   从头部依次删除K中的元素，直至只剩余两个

                   设置v1指向K的第一个元素，v2指向K的最后一个元素

         else  (e与v2共链) 

                   令v15指向K中倒数第三个顶点

                            If (∠v15-v2-e三点的夹角为锐角)

                                     连接对角线v15和e

                                     删除v2所指顶点

                                     重新令v2指向K中最后一个元素

                            else

                                     令v2指向K中最后一个元素

S4、完成对单调多边形M的三角剖分

 如图：

算法说明：

1. 单调多边形的三角化算法在讨论降序排列的顶点时，主要是根据高度相邻的两个顶点之间的左右链关系。分共链和不共链两种情况分别进行对应的操作。
2. 访问到最低点时是算法的关键一步，也是目前很多资料模糊一过的地方。在此的处理方式是：首先判断此时辅助链表K中的元素数目是否大于3（因为一开始就把当前元素加入到了K中，故此时K中的最后一个元素就是最低点），若小于或等于3，说明当前情况下最后剩下的也是个三角形，单调多边形已经三角剖分完毕。若大于3，说明还需要添加最低点与其它顶点之间的对角线做最后的剖分工作，此时将最低点的左右链标识设置为与倒数第二低的点（即K中倒数第二个元素）相反，使其按照不共链的方式处理。因为最低点与倒数第二低的点本身就通过多边形的边连接，所以在做不共链处理时也要特别注意。这样最终完整地完成对单调多边形的剖分。

3. 问题延伸及讨论

3.1 一个算法问题

         在实际的编程过程中，遇到一个很好玩的问题，估计也可能是常见的经典算法问题吧。我只是简单的想了想，还没查阅资料深入研究。在这里总结出来和大家一起探讨下。

         问题：一个数组a[100]（数组中的元素可以为自定义类型，有键值可以进行比较的），求一个数组order[100]，order[0]中存放的是a[100]中最大的元素在原数组中的位置序号，order[1]存放a[100]第二大的元素在原数组中的位置序号。。。依次类推，order[100]存放的是a[100]排序后的索引。要求编程实现，算法尽量简洁优雅。

         问题变种：已知一个数组a[100]，求数组中第k大的数在数组a[100]中的位置。k=1时也就是最大值，这个比较简单遍历一遍就行，但是当k不为1时，能否找到一种更简洁的算法？

         问题的大致的描述既是如此，相信大家一看就能明白。我在解决这个问题用的是最笨的方法，给原数组中的元素编号为在数组中的位置序号，然后在一个辅助数组上排序，然后再得到所要的索引数组。虽然实现了结果，但是自己也感觉实在太丑陋。这个问题感觉在数据库操作时，用SQL语句实现类似的东西。不知大家对此有什么好的想法，还请赐教。

3.2 并行程序设计

         以上是多边形剖分算法，看起来简单，但是实现起来还是有点小复杂。算法的时间复杂度已经是O(n log n)，不过算法还有一个好处就是，可以以并行的方式实现。算法分为两个步骤：第一步，多边形单调划分只能用单线程，其生成的单调多边形可看作是彼此独立的；第二步，单调多边形三角化则可以采用多线程的方式处理。只可惜小弟我目前才疏学浅，等过段时间研究下多线程编程再重新实现下。

计算几何---多边形三角剖分算法研究与实现（1）：多边形单调划分

程序源代码下载地址：http://download.csdn.net/source/3169759

参考文献：

[1] Mark de Berg 等著, 邓俊辉 译, 计算几何:算法与应用(第三版), 清华大学出版社,2009

[2] 周培德. 计算几何[M] .北京:清华大学出版社, 2000.

[3] 毕林,王李管,陈建宏,冯兴隆. 快速多边形区域三角化算法与实现[J]. 计算机应用研究 , 2008,25(10):3030-3033

[4] 薛伟莲,王志强. Visual C++实现单调多边形三角剖分[J]. 大连海事大学学报, 2002, 28(2) :106-108