动态基线倾角最大化圈绕凸壳算法描述

3.2.1　动态基线倾角最大化圈绕凸壳算法描述

定义3.1　二维点集S={P_i(x_i,y_i)│1≤i≤m＜+∞,m≥3}中各点的位置分布区域，称为S分布域。

定义3.2　二维点集S={P_i(x_i,y_i)│1≤i≤m＜+∞,m≥3}中，其X轴、Y轴坐标值最大、最小的四个最外点分别记为P_（1）（x₁=min{x_i│1≤i≤m，3≤m＜+∞}，y₁），P_（2）（x₂，y₂=min{y_i│1≤i≤m，3≤m＜+∞}），P_（3）（x₃=max{x_i│1≤i≤m，3≤m＜+∞}，y₃），P_（4）（x₄，y₄=max{y_i│1≤i≤m，3≤m＜+∞}）；这四个最外点P_（1），P_（2），P_（3），P_（4），合称二维点集S的凸壳Q的初始极点，并记为Q_1，0，Q_2，0，Q_3，0，Q_4，0。直线Q_1，0Q_3，0与直线Q_2，0Q_4，0，称为凸壳Q的分划线，两分划线的交点Q₀称为凸壳Q的远心；这两条分划线所分划出的二维点集S分布域的四个小区域Ⅰ、Ⅱ、Ⅲ、Ⅳ，合称二维点集S的子分布域。凸壳Q的最新相邻两顶点所构成线段称为基线（如图3.2所示）。

图3.2　凸壳的初始极点、子分布域及其基线倾角最大化算法示意图

据此，作者提出动态基线倾角最大化凸壳新算法。其算法思想可构造性描述如下：

第0步：初始化处理。

（1）“构造布域S的初始点”处理：二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜+∞}中，其Y轴坐标值最小的点记为P_（1）。

（2）“分布域及其子分布域初始极小化”处理：在分布域S中，删除位于以分划线为对角线的四边形Q_1，0Q_2，0Q_3，0Q_4，0（注意：它可能退化为三角形Q_1，0Q_2，0Q_3，0）中的所有内点，并仍记为S。

第1步：标记子分布域Ⅰ为S₁。以Q_1，0为初始极点，以Q_1，0Q_2，0为初始基线，寻找凸壳Q在子分布域S₁中的各极点（即各顶点。显然，最紧邻两极点必顺次构成凸壳Q的一条边）。即

（1）“寻找下一新极点（即顶点）”处理：当S₁中尚有未处理点P_1，j∈S₁时，找出点P_1，j与当前子分布域S₁中的基线Q_1，kQ_2，0倾角最大（即满足∠Q_2，0Q_1，kP_i=max{∠Q_2，0Q_1，kP_1，j|P_1，j∈S₁}）的最大倾角点P_i（注：若有多个最大倾角点，则只取最远处的那个最大倾角点，即离当前最大倾角顶点Q_1，k最远的那个最大倾角点）；顺次标记极点P_i为新顶点Q_1，k+1，k≥0。

（2）“子分布域S₁极小化”处理：在S₁中，删除位于当前基线三角形Q_2，0Q_1，kQ_1，k+1中的所有内点，并仍记为S₁；以Q_2，0Q_1，k+1为求下一极点的新基线，并仍记为Q_2，0Q_1，k。回到本步（1）。

第2步：标记子分布域Ⅱ为S₁。以Q_2，0为初始极点，以Q_2，0Q_3，0为初始基线，寻找凸壳Q在子分布域S₁中的各极点。即

（1）当S₁中尚有未处理点P_2，j∈S₁时，找出与当前子分布域S₁中的基线Q_2，kQ_3，0倾角最大（即满足∠Q_3，0Q_2，kP_i=max {∠Q_3，0Q_2，kP_2，j|P_2，j∈S₁}）的最大倾角点P_i；顺次标记极点P_i为新顶点Q_2，k+1，k≥0。

（2）在S₁中，删除位于当前基线三角形Q_3，0Q_2，kQ_2，k+1中的所有内点，并仍记为S₁；以Q_3，0Q_2，k+1为求下一极点的新基线，并仍记为Q_3，0Q_2，k。回到本步（1）。

第3步：标记子分布域Ⅲ为S₁。以Q_3，0为初始极点，以Q_3，0Q_4，0为初始基线，寻找凸壳Q在子分布域S₁中的各极点。即

（1）当S₁中尚有未处理点P_3，j∈S₁时，找出与当前子分布域S₁中的基线Q_3，kQ_4，0倾角最大（即满足∠Q_4，0Q_3，kP_i=max{∠Q_4，0Q_3，kP_3，j|P_3，j∈S₁}）的最大倾角点P_i；顺次标记极点P_i为新极点Q_3，k+1，k≥0。

（2）在S₁中，删除位于当前基线三角形Q_4，0Q_3，kQ_3，k+1中的所有内点，并仍记为S₁；以Q_4，0Q_3，k+1为求下一极点的新基线，并仍记为Q_4，0Q_3，k。回到本步（1）。

第4步：标记子分布域Ⅳ为S₁。以Q_4，0为初始极点，以Q_4，0Q_1，0为初始基线，寻找凸壳Q在子分布域S₁中的各极点。即

（1）当S₁中尚有未处理点P_4，jS∈1时，找出与当前子分布域S₁中的基线Q_4，kQ_1，0倾角最大（即满足∠Q_1，0Q_4，kP_i=max{∠Q_1，0Q_4，kP_4，j|P_4，j∈S₁}）的最大倾角点P_i；顺次标记极点P_i为新顶点Q_4，k+1，k≥0。

（2）在S₁中，删除位于当前基线三角形Q_1，0Q_4，kQ_4，k+1中的所有内点，并仍记为S₁；以Q_1，0Q_4，k+1为求下一极点的新基线，并仍记为Q_1，0Q_4，k。回到本步（1）。

结束步：顺序把分布域中Ⅰ、Ⅱ、Ⅲ、Ⅳ所得各顶点，依次两两连接而得到的凸多边形Q，必定是所求二维有限点集S的凸壳Q。

显然，本文提出的动态基线最大倾角的凸壳新算法，不仅在时间、空间复杂度与效率上，均优于现行卷包裹凸壳算法、格雷厄姆凸壳算法、折半分治凸壳算法等传统凸壳算法，且很容易改造为并行化算法。因此，它将有效提高二维凸壳生成速度。