单域单向水平倾角最小化圈绕凸壳算法的描述

3.3.1　单域单向水平倾角最小化圈绕凸壳算法的描述

定义3.3　二维点集S={P_i（x_i，y_i）│1≤i≤m＜+∞，m≥0}中，其Y轴座标值最小点（注：若有多个最小点，则只取最左一个最小水平倾角点）P₁（x₁=min{x_i│1≤i≤m≥3}，y₁），称为二维点集S的凸壳Q的最低点或初始顶点Q₁。以凸壳Q任一顶点Q_j为端点且平行于X轴正方向的同向射线Q_jL_j（1≤j≤n≤m＜+∞，n≥3），称为顶点Q_j的顶点水平射线；其中Q₁L₁，称为初始顶点Q₁的初始水平射线。顶点Q_j的顶点水平射线Q_jL_j，以端点Q_j为圆心，按逆时针方向转行到二维点集S中任一点P_i处所成夹角P∠iQ_jL_j，称为点P_i对水平射线Q_jL_j的水平倾角（0≤P∠_iQ_jL_j≤2π）（示例如图3.4所示）。

据此，作者提出的单域单向水平倾角最小化圈绕凸壳算法。其算法思想可构造性述如下：

第0步：“初始顶点生成”处理。如图3.4所示，在分布域S中，找出Y轴座标值最小（注：若有多个最小点，则只取最左一个最小点）的一个初始极点（即最低点）P₁，作为凸壳初始顶点（即最低顶点）Q₀，并标记为新顶点Q₁。

第1步：“圈绕寻找下一新顶点”处理。当单一分布域S中尚有未处理点时：

（1）“构造当前次新顶点的水平射线”处理：过凸壳当前次新顶点Q₁，作Q₁的平行X轴正方向的同向顶点水平射线Q₁L₁。

（2）“寻找最小水平倾角点”处理：在S中，单向圈绕地找出对当前次新顶点Q₁（即：上一次的最新顶点Q_j，1≤j≤n−1）的水平射线Q₁L₁的水平倾角最小点P_i（即满足∠P_i Q_jL_j = min{∠P_kQ_jL_j | P_k∈S}）。（注：若有多个最小水平倾角点，则只取最后一个最小水平倾角点，即离当前次新顶点Q₁最远的那个最小水平倾角点P_i）。

图3.4　单域单向水平倾角凸壳算法示意图

（3）“标记当前最新顶点”处理：把当前所得水平倾角最小点P_i，先顺次保存为最新顶点Q_k（1≤k≤n）；再把所得最新顶点Q_k，仍标记作下一次的次新顶点Q₁。

第2步：“分布域极小化”处理。在当前分布域S中，删除由初始顶点Q₀、次新顶点Q_k−1、最新顶点Q_k构成三角形所覆盖的各点；并仍记为S。回到第1步，继续作单域单向圈绕寻找。

结束步：顺序把所得各顶点依次两两连接而得到的凸多边形Q必定是所求二维有限点集S的凸壳Q。

不难看出：本凸壳新算法，一方面经极小化处理后的新分布域S中，其无效内点个数一般都会快速减少（而不是像卷包裹凸壳算法那样“其无效内点总数永远都是固定不变”），故已可大幅提高凸壳Q的生成速度；另一方面，对当前次新顶点Q₁的水平倾角最小点P_i，都是只作一轮“从当前分布域S中寻找新顶点的精确处理”（而不是像卷包裹凸壳算法那样“每转动转角Δ一次，就要作一轮‘从初始分布域S中寻找新顶点的近似处理’，更何况通常还需转动转角Δ多次”），故更可进一步提高凸壳Q生成速度。