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

3.4.1　单域双向水平倾角最值化圈绕凸壳算法描述

事实上，只要能对卷包裹凸壳算法施行“用足其缠绕潜能，克服其近似缺点，消除其低效弱点”的同构化改进与创新，就一定会产生效率更高的凸壳新算法（例如：单域双向最小水平倾角圈绕凸壳新算法）。

定义3.4　二维点集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_逆0 、Q_顺0。以凸壳Q第i个逆向顶点Q_逆i为端点（0≤i＜[n/2]+1≤m＜+∞，n≥3），且平行于X轴正方向的同向射线Q_逆iL_逆i+1，称为第i个逆向顶点Q_逆i的逆向顶点水平射线；以凸壳Q第i个顺向顶点Q_顺i为端点，且平行于X轴负方向的同向射线Q_顺iL_顺i+1，称为第i个顺向顶点Q_顺i的顺向顶点水平射线。第i个（0≤i＜[n/2]≤m−1＜+∞，n≥3）逆向顶点Q_逆i的逆向顶点水平射线Q_逆iL_逆i+1，绕其端点Q_逆i，按逆时针方向转行到二维点集S中任一点R处所成夹角∠RQ_逆iL_逆i+1，称为点R对逆向顶点水平射线Q_逆iL_逆i+1的逆向水平倾角（0≤∠RQ_逆iL_逆i+1≤2π）；第i个顺向顶点Q_顺i的顺向顶点水平射线Q_顺iL_顺i+1，绕其端点Q_顺i，按顺时针方向转行到二维点集S中任一点R处所成夹角∠RQ_顺I L_顺i+1，称为点R对顺向顶点水平射线Q_顺iL_顺i的顺向水平倾角（0≤∠RQ_顺iL_顺i+1≤2π）（其示例如图3.5所示）。

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

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

第0步：“初始顶点生成”处理。在二维点集分布域S中，找出Y轴座标值最小的一个最低点（注：若有多个最低点，则只取最左一个最低点），作为二维点集S的初始顶点（即最低顶点）Q₀，同时兼作逆时针方向圈绕、顺时针方向圈绕初始顶点Q逆0 、Q顺0，并标记为当前最新顶点。

（1）“构造初始顶点的逆向、顺向水平射线”处理：各过分布域S的凸壳Q的逆向、顺向初始顶点Q逆0 、Q顺0，分别作平行于X轴正向、负向的同向水平射线Q逆0L逆1、Q顺0L顺1，各作为初始顶点Q逆0、Q顺0的逆向、顺向水平射线。

（2）“寻找初始顶点的逆向、顺向最小水平倾角点”处理：在分布域S中，逆时针圈绕地找出对初始顶点Q逆0的逆向水平射线Q逆0L逆1的逆向水平倾角最小点P（即满足PQ∠逆0L逆1 = min{RQ∠逆0L逆1 | RS}∈。注意：若有多个最小水平倾角点，则只取最后一个最小逆向水平倾角点，即离当前次新顶点Q逆0最远的那个最小水平倾角点P），并顺次保存和标记为逆向最新顶点Q逆1；同时，顺时针圈绕地找出对初始顶点Q顺0的顺向水平射线Q顺0L顺1的顺向水平倾角最小点P（即满足PQ∠顺0L顺1 = min{R∠Q顺0L顺1 | RS}∈。注意：若有多个最小水平倾角点，则只取最后一个最小顺向水平倾角点，即离当前次新顶点Q顺0最远的那个最小水平倾角点P），并顺次保存和标记为顺向最新顶点Q顺1。

（3）“分布域极小化”处理：在分布域S中，删除位于三个点Q顺1、Q₁、Q逆1这 三个点所构成三角形区域内部的所有点，并将删除后所剩分布域S仍记为S。

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

（1）“构造当前次新顶点的逆向、顺向水平射线”处理：过凸壳Q的当前次新顶点Q逆k 、Q顺k（1≤k≤[n/2]），各过凸壳Q的当前次新逆向、顺向顶点Q逆k 、Q顺k，分别作平行于X轴正向、负向的同向水平射线Q逆kL逆k+1、Q顺kL顺k+1，各作为当前次新顶点Q逆k、Q顺k的逆向、顺向水平射线。

（2）“寻找当前次新顶点的逆向、顺向最小水平倾角点”处理：在分布域S中，逆时针圈绕地找出对当前逆向次新顶点Q逆k的逆向水平射线Q逆kL逆k+1的逆向水平倾角最小点P（即满足P∠Q逆kL逆k+1 = min{RQ∠逆kL逆k+1 | RS}∈。注意：若有多个最小水平倾角点，则只取最后一个最小逆向水平倾角点，即离当前次新顶点Q逆k最远的那个最小水平倾角点P），并顺次保存和标记为逆向最新顶点Q逆k+1；同时，顺时针圈绕地找出对当前顺向次新顶点Q顺k的顺向水平射线Q顺kL顺k+1的顺向水平倾角最小点P（即满足PQ∠顺kL顺k+1 = min{RQ∠顺kL顺k+1 | RS}∈。注意：若有多个最小水平倾角点，则只取最后一个最小顺向水平倾角点，即离当前次新顶点Q顺k最远的那个最小水平倾角点P），并顺次保存和标记为顺向最新顶点Q顺k+1。

第2步：“分布域极小化”处理。在当前分布域S中，删除由逆向、顺向次新顶点Q逆k、Q顺k，逆向、顺向最新顶点Q顺k+1、Q逆k 这四个点所围成四边形（注意：它仅最后一次可能退化为三角形）区域所覆盖的全部点；并将删除后所剩分布域S仍记为S。回到第1步，继续作单域双向圈绕寻找。

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

不难看出，单域双向水平倾角圈绕1次，必产生凸壳的两个逆向、顺向最新顶点（注意：仅最后一次可能退化为1个新顶点，而此时已无需删除内点了），而这两个最新顶点与其紧邻的前两个次新顶点一起，可构成一个四边形子凸壳内点。显然不难证明，该四边形子凸壳中的内点，与单域单向水平倾角圈绕两次所得的两个三角形子凸壳中的内点相比，前者的内点个数一般远比后两者的内点总数更多。因此，单域双向水平倾角圈绕凸壳新算法，一般能比单域单向水平倾角圈绕凸壳新算法更快地删除内点，较早地避免过多内点的重复处理，从而可进一步提高凸壳Q生成速度。