顶点凹凸化凸壳改进算法

2.2.2　顶点凹凸化凸壳改进算法

2005年，岳昊对格雷汉姆凸壳算法提出了顶点凹凸化改进。

一、顶点凹凸化凸壳算法描述

如图2.5所示，顶点凹凸化凸壳算法的算法思想可概述如下：

第1步：在二维点集S中找出y坐标最小的点，并把它记为为P₁，将二维点集中的其他各点与P₁点用线段连接起来，计算这些线段与水平直线的夹角。然后按照夹角大小进行非递增分类（若有两个点或多个点P_i与P_j（i≠j）夹角相等，且线段P₁ P_i ＆gt;P₁ P_j，则删去P_j），得到一个顶点序列，将这个顶点序列可以记为P₁，P₂，P₃，…，P_n，依次连接这些点，便可以得到一个多边形。其中：P₁是凸壳边界BCH（S）的起点，P₁、P_n也必是凸壳的顶点。

图2.5　顶点凹凸化凸壳算法示意图

第2步：判定点P_i的凹凸性，i=3，4，…，n−1。

第3步：在顶点序列P₁，P₂，P₃，…，P_n中，对其所有的凹顶点序列q₁，q₂，q₃，…，q_m的每个凹顶点序列两端的凸顶点q₁、q_m连接，删去q₁、q_m之间的凹顶点，并将q₁、q_m记为新顶点，然后重新判定q₁、q_m的凸凹性。

第4步：如果新顶点中仍然有凹顶点，则重复操作第3步、第4步，直到新顶点中没有凹顶点为止。

结束步：输出最后所得最终凸壳的顶点序列P₁，P₂，P₃，…，

P_n。

二、顶点凹凸化凸壳算法分析

定理2.1　该算法操作（1）所产生的顶点P₁、P₂、P₃、…、P_n依次连接所形成的多边形p为简单多边形。

证明：如图2.5所示，由该算法操作（1）的描述可知，由P₁出发的n−1条射线P₁P₂、P₁P₃、…、P₁P_n把平面分为n−1个域，多边形P的边P₂P₃、P₃P₄、…、P_n−1P_n位于前（n−2）个域中。故多边形P的边P₁P₁、P₂P₃、P₃P₄、…、P_n−1P_n、P_nP₁两两互不相交，可得，多边形P必为简单多边形。

定理2.2 给定任意一个简单多边形P，一个凸多边形P′，设P′的顶点均为P的顶点，且P′包含P的所有顶点，则P′是P的顶点集S的凸壳边界。

证明：假设P不是P′的凸壳边界，则可设P的凸壳边界为BCH（S），由于P的顶点集包含P′的顶点集S′，而BCH（S）=P′，故是包含S的最小凸多边形，P=BCH（S），P′为P的顶点集S的凸壳边界。

证明：设在未执行（3）时凸顶点数为c，凹顶点数为'c。

情况1：若cc'≥即：

情况2：若cc'≤即：

由以上两种情况可知定理成立。

定理2.4 该算法操作（3）、（4）循环中，每次所产生的多边形是简单多边形，且均包含原点集S。

证明：

由该算法操作（3）可知，删去凹顶点之后需要重新判定凹凸性的顶点和原来的凸顶点依然是有序排列的。由定理2.1的证明方法可知每次产生的是简单多边形；每个顶点p是按照线段pp₁与过p₁的水平线的夹角有序排列的，故凹顶点序列两端凸顶点与p₁形成的三角形域包含这个凹顶点序列中的所有凹顶点，故操作（3）、（4）在循环中所产生的简单多边形包含原点集S。

如图2.6所示，凹顶点序列为P₂，P₃，P₄，P₅，而三角形域P₂P₃P₁包含P₃P₄。

图2.6　定理2.4 的示意图

定理2.5　该算法是正确的，并且其时间复杂度为o（n log n）。

证明：

（1）由定理2.1、定理2.4可知，算法结束时间所产生的是包含点集的简单多边形。该简单多边形无凹点，故为一凸多边形。由定理2.2可知，该凸多边形即为给定点集S的凸壳边界。因此，该算法正确。

（2）该算法操作（1）的时间复杂度为o（n log n）。操作（2）可用线性时间完成；据定理2.3，操作（3）、（4）所循环产生要重新判定凹凸性的顶点个数至多为

故判定凸凹性需要o（n+log n）时间。多边形原有凹点及新产生的凹点总数小于o（2n+log n）个；若设处理每个凹顶点耗费一个单位时间，则处理凹顶点需要o（2n+log n）时间。因此，操作（3）、（4）的循环处理所需时间耗费为：

o（nlog n）+o（n）+ o（n+log n）+ o（2n+log n）= o（nlog n）