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

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

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

（1）其Y轴坐标值最小点P_下1（x_下1，y_下1=min{y_下i│1≤i≤m≥3}）（注：若有多个最小点，则只取最左一个最小点），称为二维点集S的凸壳Q的初始下左顶点Q_下左1、初始下右顶点Q_下右1，合称Q_下1；其Y轴坐标值最大点P_上1（x_上1，y_上1=max{y_上i│1≤i≤m≥3}）（注：若有多个最大点，则只取最左一个最大点），称为二维点集S的凸壳Q的初始上左顶点Q_上左1、初始上右顶点Q_上右1，合称Q_上1；，并称线段Q_下1Q_上1为二维点集S的凸壳的纵向直径（即纵向最大弦）。

线段Q_下1Q_上1把二维点集（即初始分布域）S分为两个初始子区域—— 左域S_左、右域S_右；称Q_右下1为右域凸壳逆（即逆时针）正向圈绕的初始顶点，Q_右上1为右域凸壳顺（即顺时针）负向圈绕的初始顶点；称Q_左下1为左域凸壳逆正向圈绕的初始顶点，Q_左上1为右域凸壳顺负向圈绕的初始顶点。这里，把S划分为S_左、S_右的方法，可定义为——

首先，删除线段Q_下1Q_上1的所有内点（即：线段Q_下1Q_上1的除其两端点Q_下1、Q_上1外的各点）。

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

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

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

（2）在右域S_右中：

以凸壳Q的任一右下逆正向（简称右下，意指：始于右域下方、沿逆时针方向、同X轴正方向）顶点Q_右下（_i1≤i≤n≤m＜+∞，n≥3，m≥3）为端点且平行于X轴正方向的射线Q_右下iL_右下i，称为右下顶点Q_右下i的右下水平射线；以“右下顶点Q_右下i的右下水平射线Q_右下iL_右下i为始边，Q_右下i到S_右中任一点R的射线为终边”的夹角∠RQ_右下iL_右下i（0≤∠RQ_右下iL_右下i＜2π），称为点R对右下顶点Q_右下i的右下水平倾角。

以凸壳Q的任一右上顺正向（简称右上，意指：始于右域上方、沿顺时针方向、同X轴正方向）顶点Q_右上（_i1≤i≤n≤m＜+∞，n≥3，m≥3）为端点且平行于X轴正方向的射线Q_右上iL_右正i，称为右上顶点Q_右上i的右上水平射线；以“右上顶点Q_右上i的右上水平射线Q_右上iL_右上i为始边，Q_右上i到S_右中任一点R的射线为终边”的夹角∠RQ_右上iL_右上i（0≤∠RQ_右上iL_右上i＜2π），称为点R对右上顶点Q_右上i的右上水平倾角。

（3）在左域S_左中：

以凸壳Q的任一左下顺负向（简称左下，意指：始于左域下方、沿顺时针方向、同X轴负方向）顶点Q_左下（_i1≤i≤n≤m＜+∞，n≥3，m≥3）为端点且平行于X轴负方向的射线Q_左下iL_左下i，称为左下顶点Q_左下i的左下水平射线；以“左下顶点Q_左下i的左下水平射线Q_左下iL_左下i为始边，Q_左下i到S_左中任一点R的射线为终边”的夹角∠RQ_左下iL_左下i（0≤∠RQ_左下iL_左下i＜2π），称为点R对左下顶点Q_左下i的左下水平倾角。

以凸壳Q的任一左上逆负向（简称左上，意指：始于左域上方、沿逆时针方向、同X轴负方向）顶点Q_左上（_i1≤i≤n≤m＜+∞，n≥3，m≥3）为端点且平行于X轴负方向的射线Q_左上iL_左负i，称为左上顶点Q_左上i的左上水平射线；以“左上顶点Q_左上i的左上水平射线Q_左上iL_左上i为始边，Q_左上i到S_左中任一点R的射线为终边”的夹角∠RQ_左上iL_左上i（0≤∠RQ_左上iL_左上i＜2π），称为点R对左上顶点Q_左上i的左上水平倾角（其示例如图3.7所示）。

图3.7　双域四向圈绕凸壳算法示意图

据此，作者提出的双域四向水平倾角最值化圈绕凸壳算法，可描述如下：

第0步：“凸壳初始最低、最高顶点”的生成处理。

（1）找出二维点集（即初始分布域）S中的Y轴座标值最小的一个初始最小点（注：若有多个最小点，则只取最左一个最小点），作为二维点集S的凸壳Q的初始最低顶点Q_下1，且作二维点集S的右域S_右、左域S_左的子凸壳的初始最低顶点Q_右下1、Q_左下1。

（2）找出二维点集（即初始分布域）S中的Y轴坐标值最大的一个初始最大点（注：若有多个最大点，则只取最左一个最大点），作为二维点集S的凸壳的初始最高顶点Q_上1，且作二维点集S的右域S_右、左域S_左的子凸壳的初始最高顶点Q_右上1、Q_左上1。

（3）把线段Q_下1Q_上1标记为二维点集S的凸壳的纵向直径（即纵向最大弦）。

第1步：“初始分布域的双域化”划分处理。

（1）删除线段Q_下1Q_上1的所有内点（即：线段Q_下1Q_上1的除其两端点Q_下1、Q_上1外的各点）。

（2）记点R（x，y）为初始二维点集S中任一点；然后，按照下列两种情况之一处理：

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

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

第2步：“双域四向水平倾角最小化圈绕寻找右域子凸壳顶点”的寻求处理。

第2-1步：“右域双向水平倾角最小化圈绕寻找凸壳顶点”的找寻处理。

（1）当右域S_右非空时，进行双向“圈绕寻找右域子凸壳的下一对（注：仅最后一次可能退化为一个）新顶点”处理：

①“构造当前右下、右上次新顶点的右下、右上水平射线”处理：在右域S_右中，分别过右域子凸壳的当前右下、右上次新顶点Q_右下i、Q_右上i（1≤i≤[n/2]+1），分别作平行于X轴正方向的同向右下、右上顶点射线Q_右下iL_右下i、Q_右上iL_右上i（1≤i≤[n/2]+1）；

②找出对右域子凸壳的当前右下次新顶点Q_右下i（1≤i≤[n/2]+1≤m＜+∞，n≥3，m≥3）的右下水平射线Q_右下iL_右下i（为始边的）的右下水平倾角最小点P（即以射线Q_右下iP为终边，且满足∠P Q_右下i L_右下i = min{∠R Q_右下i L_右下i| R∈S_右}；注意：若有多个右下最小水平倾角点，则只取最后一个右下最小水平倾角点，即离当前次右下新顶点Q_右下i最远的那个右下最小水平倾角点），并顺次保存为最新右下顶点Q_右下i+1；

③找出对右域子凸壳Q的当前右上次新顶点Q_右上i（1≤i≤[n/2]+1≤m＜+∞，n≥3，m≥3）的右上水平射线Q_右上iL_右上i（为始边的）的右上水平倾角最小点P（即以射线Q_右上iP为终边，且满足∠P Q_右上i L_右上i = min{∠R Q_右上i L_右上i| R∈S_右}；注意：若有多个右上最小水平倾角点，则只取最后一个右上最小水平倾角点，即离当前次右上新顶点Q_右上i最远的那个右上最小水平倾角点），并顺次保存为最新右上顶点Q_右上i+1。

（2）“右域S_右的极小化”处理（其实质是：对右域S_右的当前已得各顶点所构成的右域子凸壳内点删除处理）：

如果所找到的右域S_右的子凸壳的当前右下、右上最新顶点Q_右下i、Q_右上i，是不同顶点（注意：此时，最新顶点Q_右下i、Q_右上i可构成右域子凸壳的当前最新弦Q_右下iQ_右上i，而其当前次新顶点Q_右下i−1、Q_右上i−1可构成右域子凸壳的当前次新弦Q_右下i−1Q_右上i−1）

则：①在当前右域S_右中，删除“由右域子凸壳的当前最新弦Q_右下iQ_右上i与次新弦Q_右下i−1Q_右上i−1所构成四边形（注意：仅最后一次可能退化为三角形，而此时已无需内点删除了）”内全部点；②把右域S_右所剩区域各点，仍记为S_右；③仅当右域S_右非空，才回到第2-1步，继续作右域双向圈绕寻找右域子凸壳顶点的处理；

否则（注意：此时，最新顶点Q_右下i、Q_右上i已退化为同一顶点）：这表明此时所求右域子凸壳的各顶点均已找出，故无需再作当前右域子凸壳内点删除处理，并可立即中止其右域双向圈绕找寻右域子凸壳顶点处理。

第2-2步：“左域双向水平倾角最小化圈绕寻找左域子凸壳顶点”的找寻处理。

（1）当左域S_左非空时，进行双向“圈绕寻找左域子凸壳的下一对（注：仅最后一次可能退化为一个）新顶点”处理：

①“构造当前左下、左上次新顶点的左下、左上水平射线”处理：在左域S_左中，分别过左域子凸壳的当前左下、左上次新顶点Q_左下i、Q_左上i（1≤i≤[n/2]+1），分别作平行于X轴负方向的同向左下、左上顶点射线Q_左下iL_左下i、Q_左上iL_左上i（1≤i≤[n/2]+1）；

②找出对凸壳Q的当前左下次新顶点Q_左下i（1≤i≤[n/2]+1≤m＜+∞，n≥3，m≥3）的左下水平射线Q_左下iL_左下i（为始边的）的左下水平倾角最小点P（即以射线Q_左下iP为终边，且满足∠P Q_左下i L_左下i = min{∠R Q_左下i L_左下i| R∈S_左}；注意：若有多个左下最小水平倾角点，则只取最后一个左下最小水平倾角点，即离当前次左下新顶点Q_左下i最远的那个左下最小水平倾角点），并顺次保存为最新左下顶点Q_左下i+1；

③找出对凸壳Q的当前左上次新顶点Q_左上i（1≤i≤[n/2]+1≤m＜+∞，n≥3，m≥3）的左上水平射线Q_左上iL_左上i（为始边的）的左上水平倾角最小点P（即以射线Q_左上iP为终边，且满足∠P Q_左上i L_左上i = min{∠R Q_左上i L_左上i| R∈S_左}；注意：若有多个左上最小水平倾角点，则只取最后一个左上最小水平倾角点，即离当前次左上新顶点Q_左上i最远的那个左上最小水平倾角点），并顺次保存为最新左上顶点Q_左上i+1。

（2）“左域S_左的极小化”处理（其实质是：对当前左域S_左的已得各顶点所构成的左域子凸壳内点删除处理）：

如果所找到的左域S_左的子凸壳的当前左下、左上最新顶点Q_左下i、Q_左上i，是不同顶点（注意：此时，最新顶点Q_左下i、Q_左上i可构成左域子凸壳的当前最新弦Q_左下iQ_左上i，而其当前次新顶点Q_左下i−1、Q_左上i−1可构成左域子凸壳的当前次新弦Q_左下i-1Q_左上i−1）

则：①在当前左域S_左中，删除“由左域子凸壳的当前最新弦Q_左下iQ_左上i与次新弦Q_左下i−1Q_左上i−1所构成四边形（注意：仅最后一次可能退化为三角形，而此时已无需内点删除了）”内全部点；②把左域S_左所剩区域各点，仍记为S_左；③仅当左域S_左非空，才回到第2-1步，继续作左域双向圈绕寻找左域子凸壳顶点的处理；

否则（注意：此时，最新顶点Q_左下i、Q_左上i已退化为同一顶点）：这表明此时所求左域子凸壳的各顶点均已找出，故无需再作当前左域子凸壳内点删除处理，并可立即中止其左域双向圈绕找寻左域子凸壳顶点处理。

最后步：把所得左域子凸壳各个顶点，顺次连接于右域子凸壳顶点序列之后，便可得所求二维有限点集S的凸壳Q。

显然，双域四向水平倾角圈绕凸壳新算法的主要优势是：一方面，它既保持双域单向水平倾角圈绕凸壳新算法的分布域“小域化（即：使原分布域实现双子分布域化）”优势，又整合了单域双向水平倾角圈绕凸壳新算法的无效内点删除“快捷化”优点，故能进一步提高凸壳生成速度。另一方面，它很容易推广和移植为凸壳的串行新算法和并行新算法。