折半分治凸壳算法

2.1.3　折半分治凸壳算法

基于分治技术与递归方法的折半分治凸壳算法，其算法效率高于卷包裹凸壳算法、格雷汉姆凸壳算法，且总运行时间为t（m）=O（m log m）。

一、折半分治凸壳算法描述

如图2.3所示，折半分治凸壳算法的算法思想可简述如下：

图2.3　凸壳Q的“Q_上1、Q_上2的上公切线，Q_下1、Q_下2的下公切线”示意图

第0步：使初始二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜∞}的点P_j（x_j ，y_j ），满足x_j ≤x_{j +1}，其中1≤j≤m−1，3≤m＜+∞。并以初始点集S的最左点P_左、最右点P_右为端点的线段作上下分界线，把S分为上下两个子点集S_上、S_下（例如图2.3中，当m=11时，X轴座标值最小、最大点P₁、P₁₁，分别为初始点集S的最左点P_左、最右点P_右，且除这两点P₁、P₁₁外，还把点集S分为上子点集S_上={P₂，P₄，P₆，P₈，P₉}，下子点集S_下={P₃，P₅，P₇，P₁₀}）。

第1步：调用递归子算法UH（S_上），以生成上凸壳Q_上。

（1）如果当前m≤3，则当前点集S_上中各点就是S_上对应凸壳的各顶点，并返回调用点；否则，执行（2）。

（2）按点数近似等量分治原则，把当前点集S_上折半划分为两个“中间工作子点集”S_上1、S_上2。

（3）以S_上1为新S_上，递归调用上凸壳生成递归算法UH（S_上），并生成S_上1的凸壳_上1。

（4）以S_上2为新S_上，递归调用上凸壳生成递归算法UH（S_上），并生成S_上2的凸壳_上2。

（5）构造凸壳_上1和凸壳_上2的上公切线（例如图2.3所示的上虚线Q₈Q₇），把凸壳_上1、凸壳_上2合并为上凸壳Q_上。

第2步：调用递归算法UH（S_下），以生成下凸壳。

（1）如果当前m≤3，则当前点集S_下中各点就是S_下对应凸壳的各顶点，并返回调用点；否则，执行（2）。

（2）按点数近似等量分治原则，把当前点集S_下折半划分为两工作子点集S_下1、S_下2。

（3）以S_下1为新S_下，递归调用下凸壳生成递归算法UH（S_下），并生成S_下1的凸壳_下1。

（4）以S_下2为新S_下，递归调用下凸壳生成递归算法UH（S_下），并生成S_下2的凸壳_下2。

（5）构造凸壳_下1和凸壳_下2的下公切线（例如图2.3所示下虚线Q₂Q₃），把凸壳_下1、凸壳_下2合并为下凸壳Q_下。

第3步：把上凸壳Q_上与下凸壳Q_下合而为一，并生成凸壳Q

（例如图2.3所示凸多边形Q₁Q₂Q₃Q₄Q₅Q₆Q₇Q₈）。

结束步：输出所求凸壳Q的各顶点Q_i，1≤i≤n。

二、折半分治凸壳算法的特点与缺点

首先，折半分治凸壳算法是无误差的精确算法。

其次，它存在两个主要缺点：

（1）由于采用递归，故其算法效率不高。

（2）子凸壳无效边越多，则其效率越低。例如：仅就上凸壳生成处理而言，在“以上公切线Q_iQ_i+1为一腰、上下分界线为另一腰，而点Q_i、Q_i+1的Y向坐标线为上、下底”所构成梯形（实际上，完全可扩大到：在“以上公切线Q_iQ_i+1为一边，而以分界线P_左P_右为其对边；Q_i+1P_左为另一边，而以Q_iP_右为其对边”所构成凸四边形P_左P_右Q_i+1Q_i）内，若所包含的S_上1、S_上2各自的点越多，则该算法所作的子凸壳的无效边就越多，因而会更降低其算法效率（如图2.3：细线所示非凸壳Q边的各无效边及其冗余处理，就颇为不少）。