双群双域四向水平倾角最小化圈绕并行凸壳新算法

4.2　双群双域四向水平倾角最小化圈绕并行凸壳新算法

显然，本书第3章第3.6节所提出的双域四向水平倾角最小化圈绕串行凸壳算法，其左域、右域子凸壳的串行计算，完全可交由两个机群各自的并行计算来实现。

图4.3　凸壳的初始极点、子分布域示意图

定义4.3　二维点集S={P_i（x_i，y_i）│1≤i≤m≥3}中各点的位置分布区域，称为S分布域。

定义4.4　二维点集S={P_i（x_i，y_i）│1≤i≤m≥3}中，其Y轴坐标值最大、最小的两个最外点分别记为P_（1）（x₁，y₁=min{y_i（1≤i≤m≥3）}），P_（2）（x₂，y₂=max{y_i（1≤i≤m≥3）}）；这两个最外点P_（1）、P_（2），合称S的凸壳Q的初始极点，并记为Q_上0、Q_下0（意即：Q_上0同为子分布域S_右、S_左的右上端的初始极点；同理，Q_下0亦然）。连接Q_上0、Q_下0这两个点所得的直线，称为点集S分布域的分界基线（简称S基线）；S基线将二维点集S分布域分为两个小区域S_左、S_右，称这两个小区域为二维点集S的子分布域（其示例如图4.3所示）。

定义4.5　不失一般性，二维点集S={P_i（x_i，y_i）│1≤i≤m≥3}的凸壳Q的初始顶点Q_上0、Q_下0，还可分别记为Q_右上，0、Q_右下，0或者Q_左上，0、Q_左下，0。在S的子分布域S_右中，分别过S_右的子凸壳Q_右的当前新顶点Q_右下，j、Q_右上，j（0≤j≤m_右），所做平行X轴正方向的同向顶点射线Q_右下，jL_右下，j和Q_右上，jL_右上，j，称为顶点Q_右下，j、Q_右上，j的正向射线。正向射线Q_右下，jL_右下，j、Q_右上，j L_右上，j分别按逆时针方向（简称A向）、顺时针方向（简称B向）绕行到点P_j（x_j，y_j）∈S_右所成夹角∠P_iQ_右下，jL_右下，j、∠P_iQ_右上，j L_右上，j，分别称为点P_j（x_j，y_j）对正向射线Q_右下，jL_右下，j的A向水平倾角、正向射线Q_右上，jL_右上，j的B向水平倾角。同理，在S的子分布域S_左中，可定义点P_r（x_r，y_r）∈S_左对正向射线Q_左上,k L_左上，k（0≤k≤m_左）的A向水平倾角∠P_rQ_右上，kL_右上，k、正向射线Q_左下，kL_左下，k（0≤k≤m_左）的B向水平倾角∠P_rQ_左下，kL_左下，k。

据此，作者在2007年进一步提出了基于机群的双群（即其机群分为两个子机群）、双域（即其数据分布域分为两个子分布域）、四向（即其分布域凸壳顶点的寻找方向，各域自分为顺时针、逆时针两个寻找方向）水平倾角最小化圈绕并行凸壳新算法。其主要算法思想可简要概述如下：

第0步：并行初始化处理。

（1）“寻找分布域S的Y轴坐标值最大、最小的最外点”的双群并行处理：

① 标记构成所论机群COW的两个子机群为COW_右、COW_左；分别标记子机群COW_右、COW_左下属各处理机的总数为n_右、n_左；分别标记子机群COW_右、COW_左下属各处理机为P_右j（1≤j≤n_右）、P_左k（1≤k≤n_左）；设定初始分布域S={P_i（x_i，y_i）│1≤i≤m≥3}中各点的X轴坐标取值的最大、最小可能值分别为x_max、x_min。

② 并行地使子机群COW_右下属各处理机P_右j（1≤j≤n_右），对“把初始分布域S按初始带宽W_S宽（=（x_max−x_min）/（n_右+ n_左））作带状划分所得的”各自初始子分布域S_右初j（1≤j≤n_右）内各点，如果初始子分布域S_右初j非空，则找出S_右初j内各点的Y轴坐标值最大、最小的两个最外点；再从所得各初始子分布域S_右初j（1≤j≤n_右）的全部最外点中，找出各S_右初j的并集构成的右初始分布域S_右初的Y轴坐标值最大、最小的两个最外点。

③ 并行地使子机群COW_左下属各处理机P_左k（1≤k≤n_左），对“把初始分布域S按初始带宽W_S宽作带状划分所得的”各自初始子分布域S_左初k（n_右+1≤k≤n_左+n_右）内各点，如果初始子分布域S_左初k非空，则找出S_左初k内各点的Y轴坐标值最大、最小的两个最外点；再在所得各初始子分布域S_左初k（n_右+1≤k≤n_左+n_右）的全部最外点中，找出各S_左初k的并集构成的左初始分布域S_左初的Y轴坐标值最大、最小的两个最外点。

④ 使子机群COW_右、COW_左联合在右、左初始分布域S_右初、S_左初的Y轴坐标值最大、最小的4个最外点中，并行地找出初始分布域S的Y轴坐标值最大、最小的两个最外点，并分别记为P_（1）（x₁，y₁=max{y_i（1≤i≤m≥3）}），P_（2）（x₂，y₂=min{y_i（1≤i≤m≥3）}）；该最外点P_（1）、P_（2）即为S的凸壳Q的初始极点（或顶点），并记为Q_上0、Q_下0。

（2）“构造分布域S的两个（即左、右）子分布域”的双群并行处理：

① 并行地分别使子机群COW_右、COW_左连接初始顶点Q_上0、Q_下0，生成初始分布域S的分界基线，以分划出供后续并行处理的二维点集S分布域的两个子分布域S_右、S_左。

② 并行地分别使子机群COW_右、COW_左，各自只挑选和保留子分布域S_右、S_左内各点数据；分别求出（“分别用处理机的总数n右、n左，对子分布域S右、S左中全部点各自进行按带状划分”所需的）子域S_右j（1≤j≤n_右）、S_左j（1≤j≤n_左）的带宽W_右宽=（max{x_i│x_i∈S_右}−min{x_i│x_i∈S_右} ）/ n_右、W_左宽=（max{x_i│x_i∈S_左}−min{x_i│x_i∈S_左} ）/ n_左。

第1步：“子机群COW_右、COW_左分别在子分布域S_右、S_左中生成子凸壳Q_右、Q_左各顶点”的并行化处理。

第1-1步：子机群COW_右在子分布域S_右中，进行双向水平倾角最小化圈绕寻找子凸壳Q_右各顶点的并行处理。

第1-1-1步：“子机群COW_右双向圈绕寻找子凸壳Q_右下一对新顶点”的并行处理：

第1-1-1-1步：初始子分布域S_右仍标记为当前子分布域S_右；标记初始顶点Q_上0、Q_下0为当前新顶点对Q_右上，0、Q_右下，0；置（当前新顶点对的序号计数器）r初值为0。

第1-1-1-2步：并行地使子机群COW_右下属各处理机P_右j（1≤j≤n_右），用带宽W_右宽把当前子分布域S带状划分为n_右个子分布域S_右j（1≤j≤n_右）。

第1-1-1-3步：并行地使子机群COW_右下属各处理机P_右j各在自己的子分布域S_右j（1≤j≤n_右）的全部点中，均以Q_右上，r、Q_右下，r为当前新顶点，求出其双向圈绕水平倾角最小化的A向、B向最小点P_右jA、P_右jB；在所得各组A向、B向最小点P_右jA、P_右jB（1≤j≤n_右）中，找出当前子分布域S_右的A向、B向最小点P_右A、P_右B；置r为r+1，并使P_右A、P_右B作为子凸壳Q_右的下一对新顶点Q_右上，r、Q_右下，r。

第1-1-2步：删除由“所得凸壳当前次新顶点对Q_{右上，r−1}、Q_{右下，r−1}、最新顶点对Q_右上，r、Q_右下，r（Q_右上，r、Q_右下，r可能合而为一）所构成子凸壳Q_{右上，r−1}Q_{右下，r−1}Q_右下，r Q_右上，r的内点”的分布域极小化并行处理：

第1-1-2-1步：如果最新顶点对Q_右上，r、Q_右下，r不合二为同一点，则：并行地使子机群COW_右下属各处理机P_右j（1≤j≤n_右），用带宽W_右宽=（max{x_i│x_i为子凸壳Q_{右上，r−1}Q_{右下，r−1}Q_右下，rQ_右上，r内的点}−min{x_i│x_i为子凸壳Q_{右上，r−1}Q_{右下，r−1}Q_右下，r Q_右上，r内的点}）/ n_右），把子凸壳Q_{右上，r−1}Q_{右下，r−1}Q_右下，r Q_右上，r所在区域QQ_右带状划分为n_右个等宽子区域QQ_右j（1≤j≤n_右）；

否则转而执行第1-1-3步。

第1-1-2-2步：并行地使子机群COW_右下属各处理机P_右j（1≤j≤n_右），各自删除在自己的子区域QQ_右j（1≤j≤n_右）中的全部点。

第1-1-2-3步：把删除QQ_右中全部点后的原子分布域S_右，仍标记为当前子分布域S_右；若当前子分布域S_右非空（即还有未找出的凸壳顶点），则回到第1-1-1-2步，否则转而执行第1-1-3步。

第1-1-3步：子凸壳Q_右的全部顶点标记处理：顺次标记已求得的子凸壳Q_右全部顶点。

第1-2步：与上述第1-1步的处理方法同理，子机群COW_左在子分布域S_左中进行双向水平倾角最小化圈绕寻找子凸壳Q_左各顶点的并行化处理。

第1-2-1步：“子机群COW_右双向圈绕寻找子凸壳Q_左下一对新顶点”的并行处理：

第1-2-2步：删除由“所得凸壳当前次新顶点对Q_{左上，r−1}、Q_{左下，r−1}、最新顶点对Q_左下，r、Q_左上，r（Q_左下，r、Q_左上，r可能合而为一）所构成子凸壳Q_{左上，r−1}Q_{左下，r−1}Q_左下，r Q_左上，r的内点”的分布域极小化并行处理：

第1-2-3步：子凸壳Q_左的全部顶点标记处理：顺次标记已求得的子凸壳Q_左全部顶点。

（注：因与上述第1-1步及其第1-1-1步、第1-1-2步、第1-1-3步的处理原理、方法、步骤、操作等极其类同，故除第1-1步中的“右、左、A向、B向”需对应改为第1-2步中的“左、右、B向、A向”外，第1-2步及其第1-2-1步、第1-2-2步、第1-2-3步的其他处理与操作均可从略）。

第2步：“将子机群COW_右、COW_左所得子凸壳Q_右、Q_左各顶点”组合为所求凸壳Q的全部顶点处理。即顺序把上述已得子凸壳Q_右、Q_左各顶点，依次两两连接而最后所得凸多边形Q，必定是所求二维点集S的凸壳Q。

显然，基于机群的双群、双域、四向水平倾角最小化圈绕并行凸壳新算法，其正确性是无容置疑的。它不仅在时间、空间复杂度与效率上均优于现行的串行卷包裹凸壳算法、格雷厄姆凸壳算法、折半分治凸壳算法、双域四向水平倾角最小化圈绕凸壳算法等凸壳串行算法；而且，便于推广到基于机群的m群、n域、p向（m＆gt;2，n＆gt;2，p＆gt;2）的并行凸壳新算法研究，以进一步改进和提高二维凸壳生成速度。