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

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

定义3.5　二维点集S={P_k（x_k，y_k）│1≤k≤m，3≤m＜+∞}中：

（1）Y轴座标值最小点P₁（x₁，y₁=min{y_k│1≤k≤m，3≤m＜+∞}）（注：若有多个最小点，则只取最左一个最小点）、最大点Q₁（x₁，y₁=max{y_k│1≤k≤m，3≤m＜+∞}）（注：若有多个最大点，则只取最左一个最大点），分别称为二维点集S的凸壳Q的最低顶点、最高顶点。线段P₁Q₁把初始二维点集S分为两个初始子区域——左域S_左、右域S_右；称P₁为右域凸壳逆（即逆时针）正向圈绕的初始顶点，称Q₁为左域逆负向圈绕的初始顶点。这里，把S划分为S_左、S_右的方法，可定义为：

首先，删除线段P₁Q₁的所有内点（即：线段P₁Q₁的除其两端点P₁、Q₁外的各点）。

其次，记点R（x，y）为二维点集S中任一点；然后：

若凸壳Q的初始顶点P₁、Q₁的X轴坐标值相同，且为x₀；则使S_左={R（x，y）│x＆gt;x₀，R∈S}，S_右={R（x_，y）│x＜x₀，R∈S }。

若凸壳Q的初始顶点P₁、Q₁的X轴坐标值不同；则以P₁为端点且平行于X轴正方向的射线P₁L_正1为始边，P₁到点R的射线P₁R为终边而形成夹角∠RP₁L_正1，并使S_左={R（x，y）│∠RP₁ L_正1＆gt;∠Q₁P₁L_正1，R_k∈S}，S_有={R_k（x_k，y_k）│∠RP₁L_正1＜∠Q₁P₁ L_正1，R_k∈S}。

（2）在右域S_右中：以凸壳Q的任一逆正向顶点P_i（1≤i≤n≤m＜+∞，n≥3，m≥3）为端点且平行于X轴正方向的射线P_i L_正i，称为逆正向顶点P_i的正向水平射线。以“逆正向顶点P_i的正向水平线L_正i为始边，P_i到S_右中任一点R的射线为终边”的夹角∠RP_iL_正i（0≤∠RP_iL_正i＜2π），称为点R对逆正向顶点P_i的逆正向水平倾角。

（3）在左域S_左中：以凸壳Q的任一逆负向顶点Q_j（1≤j≤n≤m＜+∞，n≥3，m≥3）为端点且平行于X轴负方向的射线Q_j L_负j，称为逆负向顶点P_j的负向水平射线。以“逆负向顶点P_j的负向水平线L_负j为始边，P_j到左域S_左中任一点R的射线为终边”的夹角∠RQ_jL_负j（0≤∠RQ_jL_负j＜2π），称为点R对逆负向顶点Q_j的逆负向水平倾角。

双域单向水平倾角最小化圈绕凸壳新算法示例，如图3.6所示。

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

第0步：“初始顶点生成与初始分布域的左、右子域划分”处理。

图3.6　双域单向圈绕凸壳算法示意图

（1）在初始分布域S中，分别找出Y轴座标值最小（即最低）、最大（即最高）的初始极点P_最低、P_最高（注意：只各取一个，若有多个最低点，则只取最左的最低点；若有多个最高点，则只取最左的最高点），并分别作为凸壳最低、最高初始顶点P₁、Q₁。

（2）用线段P₁Q₁，按定义3.5“i”的方法，把初始分布域S划分为两个初始子域——左域S_左、右域S_右。

（3）使凸壳当前“逆正向、逆负向顶点组”的初始组序号k，取其初值1。

第1步：当子分布域S_右、S_左非空时，分别在右域S_右、左域S_左作逆向圈绕寻找凸壳当前逆向最新顶点（即凸壳的下一组逆正向、逆负向最新顶点，而该组最新顶点具有特性“初始组必为一个，最后组方可一个，其余组总为一对”）处理。

（1）当右域S_右非空时，作右域逆向圈绕寻找当前最小逆正向水平倾角最小点（即凸壳当前逆正向最新顶点P_i+1）处理。

① “构造当前逆正向次新顶点的正向水平射线”处理：过凸壳当前逆正向次新顶点P_i，作P_i的平行X轴正方向的正向水平射线P_iL_正i。

② 在分布域S_右中，逆向圈绕地找出对当前逆正向次新顶点P_i的正向水平射线P_iL_正（_i作始边）的逆正向水平倾角最小点P_i+1，使它满足∠P_i+1P_iL_正i = min{∠RP_iL_正i | R∈S_右}）（注：若有多个逆正向水平倾角最小点，则只取最末端那个逆正向水平倾角最小点，即离当前次新逆正向顶点P_i最远的那个逆正向水平倾角最小点P_i+1）。

③ 把当前所得逆正向水平倾角最小点P_i+1，按逆向生成顺序，依次保存、标记为凸壳逆正向最新顶点P_a（满足：1＜a≤[n/2]+1；若最后一组最新顶点为不同顶点时，则max{a}+max{b}−1=n，否则max{a}+max{b}−2=n）。

（2）当左域S_左非空时，作左域S_左逆向圈绕寻找当前最小逆负向水平倾角点（即凸壳当前逆正向最新顶点Q_j+1）处理。

①“构造当前逆负向次新顶点的负向水平射线”处理：过凸壳当前逆负向次新顶点Q_j，作Q_j的平行X轴负方向的负向水平射线Q_jL_负j。

②在分布域S_左中，逆向圈绕地找出对当前逆负向次新顶点Q_j的负向水平射线Q_jL_负j（作始边）的水平倾角最小点Q_j+1，使它满足Q∠_j+1Q_jL_负j = min{∠RQ_jL_负j | RS∈_左}（注：若有多个逆负向水平倾角最小点，则只取最末端那个逆负向水平倾角最小点，即离当前次新逆负向顶点Q_j最远的那个逆负向水平倾角最小点Q_j+1）。

③把当前所得逆负向水平倾角最小点Q_j+1，按逆向生成顺序，依次保存、标记为凸壳逆负向最新顶点Q_b（满足：1＜b≤[n/2]+1；若最后一组最新顶点为不同顶点时，则max{a}+max{b}−1=n，否则max{a}+max{b}−2=n）。

第2步：“分布域极小化处理”（即当对前已得各顶点所构成的当前子凸壳内点删除）：

如果在对应右域、左域所找到的当前右域逆正向最新顶点P_a、左域逆负向最新顶点Q_b是不同顶点：

（1）在当前右域S_右中，删除与初始逆正向顶点P₁位于“由初始逆正向顶点P₁和当前右域逆正向最新顶点P_a所构成射线”同一侧（即射线P₁P_a沿顺时针方向旋转所遇到的）的全部点；并把所剩右域仍记为S_右。

（2）在当前左域S_左中，删除与初始逆负向顶点Q₁位于“由初始逆负向顶点Q₁、当前左域逆负向最新顶点Q_b所构成射线”同一侧（即射线Q₁Q_b沿顺时针方向旋转所遇到的）的全部点；并把所剩右域仍记为S_右。

（3）回到第1步，继续作双域单向圈绕寻找。

否则（即当前右域逆正向最新顶点P_a，同时又是当前左域逆负向最新顶点Q_b），已表明此时所求凸壳的各顶点均已找出，故无需再作当前子凸壳内点（无论其有无）的删除处理，并中止其双域单向圈绕。

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

因为对给二维定点集中大量无效内点的重复处理，是影响凸壳算法效率提高的主要障碍，故无效内点的大（区）域化，则必然是加剧阻碍凸壳算法效率提高的首要原因，而无效内点的小域化，则必定为加速提升凸壳算法效率的重要途径之一。

由此观之，双域单向水平倾角圈绕凸壳新算法的主要优势是无效内点的小域化，从根本上消除了诸如卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法、单域双向水平倾角最小化圈绕凸壳算法等所共有的无效内点原区域的“单域化”缺点，即通过把无效内点原区域的“最大化（即单域化）”改进为“小域化（即二域化）”，从而较大程度地提高了凸壳Q生成速度。同时，它也容易推广和移植为凸壳的并行新算法。