增点递推凸壳算法及其改进

2.2.1　增点递推凸壳算法及其改进

2002年，南京大学王杰臣对增点递推凸壳算法提出了改进。

一、增点递推算法

增点递推凸壳算法是典型的串行算法，是较为常用、效率较高的凸壳算法之一。由于它的上半凸壳或下半凸壳计算过程类似于常见二叉（或称二路、二块）分割，故其算法可采用递归或循环（例如：可用增点标志变量作为循环终止条件）来设计。

1．增点递推算法描述

（1）增点递推凸壳算法的基本原理

如图2.4所示，设点集A = { P₁，P₂，…，P_n}，找出其中X坐标最小的与最大的点并分别记为P_L 和P_R ，那么点集A 的最小凸壳可以看做是由两部分构成的，即从P_L 到P_R的上凸壳和从P_RP_L 到P_L的下凸壳。在计算上凸壳过程中，仅需考虑点集A上半部分的点，即向量P_LP_R左侧的点。用直线连接P_L、P_R，上凸壳必须包含距直线P_LP_R 最远的居于直线左侧、点集A 的顶点。若点集A的所有点都不居于直线P_LP_R的左侧，则上凸壳退化为唯一凸边P_LP_R。反之，在直线P_LP_R中插入位于其左侧且距离最远的点P_U，将直线P_LP_R剖分为两段，此时P_L P_UP_R成为新的上凸壳。仿此，分别在P_LP_U和P_UP_R范围内寻找位于其左侧距离最远的点，如果在P_LP_U 和P_UP_R范围内均找不到位于左侧的点，即由历次剖分中选中的点唯一确定上凸壳。如在任一范围（设为P_LP_U）内找到相应的点，则继续将P_LP_U一分为二，进行后继寻找。重复该过程直到所有剖分范围内不再找到满足条件的点，最终由各剖分点构成上凸壳。考虑到算法的对偶性，下凸壳也可类似地计算，不同的是“左侧最远”增点条件应相应地改变为“右侧最远”。

图2.4　上凸壳顶点搜索过程

（2）增点递推凸壳算法的高抽象度算法

第1步：找出点集A中X坐标最小、最大的点P_L、P_R。

第2步：分别建立A的上凸壳、下凸壳。

第3步：合并上、下凸壳为所求凸壳。

结束步：输出所求凸壳。

2．增点递推算法时间效率分析

从该算法的基本原理和实现步骤不难看出，影响算法效率的主要原因为：在上凸壳或下凸壳建立过程中，每增加一个新的顶点，相应地产生了2 条新的边，需要2次遍历整个点集以进一步判断这2条边之外是否存在新的顶点。设点集A的点总数为N，上、下凸壳顶点个数分别为M₁、M₂，其凸壳顶点（个）数为M = M₁+M₂−2，则需进行（2M₁−3）+（2M₂−3）=2（M−1）次点集遍历（M₁≥2，M₂≥2）。而每次遍历均需进行全部N个点的判定（包括点线关系判断、点线距离计算），点判定总次数为2（M−1）×N。当点集中的点数达500万、凸壳的顶点数为200时，点判定次数达到近20亿次。

对增点递推凸壳算法做的数据测试实验结果（如表2.1、表2.2所示），大体反映了执行时间与凸壳顶点数、点集的点总数之间的上述关系。

表2.1　处理时间与凸壳顶点数间的关系（其点总数均为10 万）

表2.2　处理时间与集合中点的数量间的关系（其凸壳顶点总数均为10）

由此可见，要提高增点递推凸壳算法的算法效率，可有两条途径：

（1）减少中间凸壳顶点个数；

（2）减少遍历点集时点的判定次数。

二、基于点集分组计算的增点递推凸壳算法

王杰臣提出的分组计算凸壳算法，可减少中间凸壳个数及其顶点个数。

1．分组计算凸壳算法描述

分组计算凸壳算法的算法思想为：

第1步：设二维点集中的点数为N，把K个点划分为一个组（即子集），以此划分出q个子点集（其中q＝N/K）。

第2步：分别对q个子集计算出其子凸壳，以得到其子凸壳集及其顶点集。

结束步：输出所求得的凸壳。

该“以各顶点子集为基础，建立二维点集的凸壳”算法的特点是：假设子凸壳集中顶点数最小的子凸壳其顶点数为M；各子凸壳的顶点数分别为M₁，M₂，…，M_q，各顶点集的平均顶点数为M′；各子集中的平均点数为K。那么，则建立各子集凸壳所需进行的点的判定次数为2（M_i−1）K，其中i=1，2，…，q；建立全部子集凸壳进行点判定的总次数为2（M′−1）N。故最后建立各凸壳顶点集的凸壳，其点判定次数为2（M−1）qM′，与上述增点递推算法的点判定次数比为：

λ=[2（M′−1）N+2（M−1）qM′]/[2（M−1）N]　　　（1）

实际上，λ可视为近似等于算法的执行时间比，因为凸壳顶点数一般可达10¹～10²量级，M′−1≈M′，M−1≈M。从而式（1）可变为：

λ≈M′/M+M′/K　　　　　　　　　（2）

为减少处理时间，需确定适当的K，M′值，以使λ极小。从式（2）可看出，K极大、M′极小时，λ达最小值（M为全集中的点数常量）。事实上，K和M′往往正相关：点数K较大的凸壳往往较复杂，使其顶点数M′增加；反之亦然。

2．分组计算的凸壳算法验证

上述分析结果表明，当分组子集内点的个数近似等于原全集的凸壳顶点数时，分组计算法具有最高的运行效率。为了验证上述结论，王杰臣利用一些随机点集进行了对比测试，其结果如表2.3所示。

表2.3表明：当凸壳顶点数超过1000时，分组算法执行时间随组内点数的变化规律与上述结论吻合较好；而当凸壳点数低于500时，执行时间的极低值表现出同步滞后特征。其主要原因是：分组子集的点数量较少时，划分子集个数较多，而在进行每个子集的凸壳生成过程中，需首先为该子集开辟凸壳存储空间和进行变量初始化，这需耗费一定机时，且分组越多耗费时间比例越高。除此之外，前面的分析过程是基于一些理想化假设条件进行的，与实际情况有一定出入。在表2.3的测试结果中，分组计算法可提高计算效率达5～25倍，凸壳越复杂，顶点数越多，分组计算法的效率提高越明显。在GIS应用中，最小凸壳顶点数一般不超过500（表2.3中顶点数≥500的点集均为程序定制结果）；据此，可确定各分组子集点数为500～1000。

有趣的是，王杰臣为简化算法，曾进行如下尝试，每完成一个子集的凸壳计算，就将所得凸壳顶点转入下一个子集参与计算，以避免最后的“凸壳归并”。但执行效率反而因此大大降低，因为该方法每处理完一个子集，其凸壳的复杂性在不断增加，凸壳顶点数逐步增加到全集最小凸壳的顶点数N，与利用点集分组法提高效率的原因（降低每个点集内的凸壳复杂性）相矛盾。

表2.3　分组子集的点数与处理时间对比表

三、动态剔点凸壳算法

王杰臣提出的动态剔点凸壳算法，可减少遍历点集时的点判定次数。

剔除判定条件较简单，二维点集中的点在增点递推算法中所形成的三角形内的判定条件是该点同时位于三角形三边的左侧（或右侧）。判定点位于线的哪一侧仅涉及较少的乘法和加减运算，与计算点线距离中的开平方运算相比，其额外时间开销比节约的时间少得多。此外，随着凸壳顶点数增加，新形成的三角形越来越小，三角形内包含的点越来越少，不值得为了剔除这很少的点来进行点集的遍历判断，这可采用已形成的凸壳顶点数或顶点层作为控制。表2.4所示为对上述算法进行测试的运行时间对比表。可以看出，采用动态剔除判定点方法，一般可进一步减少处理时间2/3左右。同时采用分组计算与动态剔除判定点的优化方法，可提高处理效率10～40倍。

表2.4　算法执行时间测试结果表