四群四域四向基线倾角与距离最大化圈绕并行凸壳新算法

4.4　四群四域四向基线倾角与距离最大化圈绕并行凸壳新算法

2007年，笔者依据同构化凸壳构造基本定理，在把本书第4章第4.3节算法改进为“在当前子分布域中，并行找出‘最大基线倾角’最大点的同时，还同步并行寻找‘当前子分布域基线距离’最大点”。据此，我们创造出基于四群四域四向“最大基线倾角与最大基线距离”的并行凸壳新算法。

定义4.8　记子凸壳Q_Si是定义4.6所论子分布域S_i的凸壳，Q_i，0、Q_i，k、Q_i，m均为是子凸壳Q_Si的顶点，1≤i≤5，k≥0，且为叙述简便可把Q_1，0、S₁分别另记为Q_5，0、S₅。若点D∈S_i，D_H是点D到基线Q_i，0Q_i，m的垂足；则称垂线DD_H为点D到基线Q_i，0Q_i，m的距离（如图4.6所示）。

图4.6　子分布域S_i的基线与基线距离示意图

显然，若点D∈S_i，能使点D到基线Q_i，0Q_i，m的距离DD_H=max｛XD_X∣X∈S_i｝，则点D（注：若有多个最大距离点，则只取离当前次新顶点Q_i，k最近、最远的那两个最大距离点，且两者均）必为子凸壳Q_Si的顶点。

据此，可构造出效率更高的基于工作站机群的四群四域四向基线倾角与距离最大化圈绕并行凸壳新算法。其主要算法思想，可简要概述如下（如图4.4～4.6所示）：

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

1．“寻找二维点集S的分布域（仍记为S）的X轴、Y轴坐标值最大、最小的4个最外点”的4群并行处理：

（1）设定（注：可由用户自行决定并输入）初始分布域S={P_k（x_k，y_k）│1≤k≤m≥3}中各点的X轴坐标取值的最大、最小可能值分别为X_max、X_min，Y轴坐标取值的最大、最小可能值分别为Y_max、Y_min。

（2）分别标记构成所论机群COW的4个子机群为COW_i（i=1，2，3，4）；标记子机群COW_i下属各处理机的总数为n_i；标记子机群COW_i下属各处理机为P_ij（1≤j≤n_i）。

（3）并行地使子机群COW_i下属各处理机P_i，j（i=1，2，3，4，1≤j≤n_i），各用初始分布域S的X轴坐标可能值初始值域[X_max，X_min]的初始带宽W_S（=（X_max−X_min）/（n₁+n₂+n₃+n₄）），对初始分布域S作带状划分出子分布域S_i，j，并各自保存所获得的初始子分布域S_i，j内各点；然后各对初始子分布域S_i，j：

①如果初始子分布域S_i，j非空，则使其处理机P_i，j在自己初始子分布域S_i，j内，并行找各自的X轴、Y轴坐标值最大、最小的4个最外点（x_i，j，max=max{x│（x，y）∈S_i，j}，y _右，i_，j）、（x i_，j_，min=min{x│（x，y）∈S_i，j}，y _左，i_，j）、（x _高，i_，j，y i_，j_，max=max{y│（x，y）∈S_i，j}）、（（x _低，i_，j，，y i_，j_，min=min{y│（x，y）∈S_i，j}）；

②从各处理机P_i，j所得的各初始子分布域S_i，j（1≤j≤n_i）的全部最右点集R_ight={（x_i，j，max，y _右，i，j）│1≤j≤n_i }、全部最左点集L_eft={（x _i，j，min，y _左，i，j）│1≤j≤n_i }、全部最高点集H_igh={（x _高，i，j，y _i，j，max）│1≤j≤n_i }、全部最低点集L_ow={（（x _低，i，j，y _i，j，min）│1≤j≤n_i ）中，并行找出各初始子分布域S_i的4个最外点：最右点（x_i，max=max{x│（x，y）∈R_ight}，y _右，i）、最左点（x _i，min= min{x│（x，y）∈L_eft}，y _左i）、最高点（x _高，i，y _i，max=max{y│（x，y）∈H_igh}、最低点（x _低，i，y _i，min=min{y│（x，y）∈L_ow}；

③从各子机群COW_i（1≤i≤4）的全部最外点集{（x_i，max，y _右，i）∣1≤i≤4 }、{（x _i，min，y _左i）│1≤i≤4 }、{（x _高，i，y _i，max）∣1≤i≤4 }、{（x _低，i，y _i，min）│1≤i≤4 }中，分别找出初始子分布域S的4个（注意：它可能退化为3个）最外点；作为并标记为二维点集S的凸壳Q的初始顶点Q_1，0（x _min，1，y _0，min，1）、Q_2，0（x_0，min，2，y _min，2）、Q_1，0（x _max，3，y _0，max，3）、Q_1，0（x_0，max，4，y _max，4）；其中，初始顶点Q_1，0（x _min，1，y _0，min，1）也可另记为Q_5，0（x _min，5，y _0，min，5），以便叙述简洁。

（4）各子机群COW_i（1≤i≤4）并行地从分布域S中删除其最外点四边形Q_1，0Q_2，0Q_3，0Q_4，0的所有点（注：它除4个顶点外，其余各点均为凸壳Q的内点），所剩分布域仍记为S。

2．“构造分布域S的4个子分布域S₁、S₂、S₃、S₄（注意：它可能退化为3个子分布域S₁、S₂、S₃）”的4群并行处理：

（1）各子机群COW_i（1≤i≤4）并行地对初始分布域S，按照实际值初始值域[x_max，3，x_min，1]的实际带宽W_S=（x_max，3−x_min，1）/（n₁+n₂+n₃+n₄），带状划分出子分布域S_i，j。

（2）并行地分别使子机群COW_i（1≤i≤4），以由初始顶点Q_i，0、Q_i+i0构成的各自初始分布域S_i的基线Q_i，0Q_i+i0为分界判据，把“点P（x，y）∈S，且与最外点四边形Q_1，0Q_2，0Q_3，0Q_4，0位于基线Q_i，0Q_i+i0不同侧”的所有点，保存为后续并行处理的二维点集S分布域的子分布域S_i（注意：S₁=S₅），并自然而然地删除位于外点四边形Q_1，0Q_2，0Q_3，0Q_4，0中的所有内点。

第1步：“子机群COW i（1≤i≤4）分别在子分布域S_i中生成子凸壳Q_i各顶点”的并行化处理。

第1-1步：子机群COW_i在子分布域S_i中，进行基线（倾角逆时针方向；下同，略）最大化与基线距离最大化的圈绕寻找子凸壳Q_i各倾角最大顶点与基线距离最大顶点的并行处理。

第1-1-1步：“子机群COW_i基线倾角最大化圈绕寻找子凸壳Q_i下一新顶点”的并行处理：

第1-1-1-1步：初始子分布域S_i仍标记为当前子分布域S_i；连接初始顶点Q_i，0、Q_i+1，0构成当前基线Q_i，0Q_i+1，0；置当前基线倾角最大新顶点的序号计数器r初值为0；置当前基线距离最大新顶点的序号计数器d初值为0。

第1-1-1-2步：并行地使子机群COW_i下属各处理机P_i，j（1≤j≤n_i），用带宽W_i=（max{x│（x，y）∈S_i}−min{x│（x，y）∈S_i}）/ n_i，把当前子分布域S_i带状划分为n_i个子分布域S_i，j（1≤j≤n₁）。

第1-1-1-3步：并行地使子机群COW_i下属各处理机P_ij各在自己的子分布域S_ij（1≤j≤n₁）的全部点中，均以Q_i，r为子凸壳Q_i的次新顶点，求出其对基线Q_i，rQ_i+1，0的基线倾角最大点R_i，j，0（注：若有多个最大倾角点，则只取距当前次新倾角顶点最远处的那个最大倾角点，即离当前最大倾角顶点Q_i，r最远的那个最大倾角点），并同时求出对基线Q_i，rQ_i+1，0的基线距离最大点D_i，j，0（注：若有多个最大距离点，则只取离当前次新顶点Q_i，k最近、最远的那两个最大距离点，且两者均）；在所得各组基线倾角最大点集{D_i，j，0│1≤j≤n₁）中，并行找出当前子分布域S_i的基线倾角最大点R，并标记为子凸壳Q_i的最新顶点Q_i，r+1，置序号计数器r为r+1；并行找出当前子分布域S_i的基线距离最大点，若只有一个当前基线距离最大点D、且不同于当前基线倾角最大点R，则标记D为子凸壳Q_i的另一最新顶点Q_i，d+1，置序号计数器d为d+1。

第1-1-2步：“删除由子凸壳Q_i的初始顶点Q_i，0、Q_i+1，0，当前基线倾角最大次新顶点Q_i，r−1、基线倾角最大最新顶点Q_i，r，与当前基线距离最大新顶点Q_i，D1、Q_i，D2（注：Q_i，D1、Q_i，D2分别为最近端、最远端当前最大距离点）所构成的多边形Q_i，0Q_i，r Q_i，D1 Q_i，D2Q_i+1，0的所有点”的子分布域S_i极小化并行处理：

第1-1-2-1步：并行地使子机群COW_i下属各处理机P_ij各自生成自己的多边形Q_i，0Q_i，r Q_i，D1Q_i，D2Q_i+1，0，并记为Δi。

第1-1-2-2步：并行地使子机群COW_i下属各处理机P_i，j（1≤j≤n_i），用带宽W_i=（max{x│（x，y）∈Δi}−min{x│（x，y）∈Δi}）/ n_i，把当前Δi带状划分为n_i个子分布域Δi_，j（1≤j≤n₁）。

第1-1-2-3步：并行地使子机群COW_i下属各处理机P_i，j（1≤j≤n₁），各自删除在自己的子区域Δ_i，j（1≤j≤n₁）中的全部点。

第1-1-2-4步：把删除Δi中全部点后的原子分布域S_i，仍标记为当前子分布域S_i；若当前子分布域S_i非空（即还有未找出的凸壳顶点），则把子凸壳Q_i的初始顶点Q_i+1，0、最新顶点Q_i，r记为新的基线Q_i，rQ_i+1，0，回到第1-1-1-2步，否则转而执行第1-1-3步。

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

第3步：形成凸壳。

结束步：顺序把各子分布域S₁、S₂、S₃、S₄中所得各顶点依次两两连接而得到的凸多边形Q，必定是所求二维有限点集S的凸壳Q。

不难看出，与四群四域四向基线倾角最大化圈绕并行凸壳算法相比，一方面因本方法还可并行地求得基线距离最大点，故各机群不仅可更快、更多地找出凸壳顶点；而另一方面因本方法还能时间更早、面积更大地删除多边形中内点，故可更多、更快地缩小凸壳顶点的当前分布域，从而大大减少本新算法的计算时间。同时，它一样易于推广到基于机群的m群、n域、p向（m＆gt;2，n＆gt;2，p＆gt;2）的并行凸壳新算法研究，以进一步改进和提高其算法效率。