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

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

2007年，笔者依据同构化凸壳构造基本定理，把本书第3章第3.2节提出的基线倾角最大化圈绕串行凸壳算法思想加以改进，再与本章第4.2节提出的凸壳并行化算法思想相结合，就催生出四群四域四向基线倾角最大化圈绕并行凸壳新算法。

定义4.6　二维点集S={P_i（x_i，y_i）│1≤i≤m≥3}中，其X轴、Y轴坐标值最大、最小的4个最外点（注：其退化情形，仅有3个最外点；不失一般性，可只考虑非退化最外点情形），均是S的凸壳Q的最左、最低、最右、最高顶点，沿顺时针方向顺次记为Q_1，0（x₁=min{x_i│1≤i≤m≥3}，y₁），Q_2，0（x₂，y₂=min {y_i│1≤i≤m≥3}），Q_3，0（x₃=max{x_i│1≤i≤m≥3}，y₃），Q_4，0（x₄，y₄₌max{y_i│1≤i≤m≥3}），合称凸壳Q的初始顶点。这四个最外点Q_1，0、Q_2，0、Q_3，0、Q_4，0所决定的四边形，称为最外点四边形（注：除其4个顶点外，其内各点均为凸壳Q的内点）。除去最外点四边形中各内点后，最外点四边形把二维点集S分布域分成的四个小区域，顺次记为二维点集S的子分布域S₁、S₂、S₃、S₄（如图4.4所示）。

图4.4　凸壳的初始顶点、子分布域示意图

定义4.7　记子凸壳Q_Si是定义4.6所论子分布域S_i的凸壳，Q_i，0、Q_i+1，0均为子凸壳Q_Si的顶点，点Q_i，k∈S_i，1≤i≤5，k≥0，且为叙述简便，可把Q_1，0、S₁分别另记为Q_5，0、S₅。若点R∈S_i，则称线段Q_i，0Q_i，k是子凸壳Q_Si的一条基线，称夹角∠Q_i，0Q_i，kR为点R对基线Q_i，0Q_i，k的基线倾角（如图4.5所示）。

显然，若点R∈S_i，能使基线倾角∠Q_i，0Q_i，kR=max｛∠Q_i，0 Q_i，kX∣X∈S_i｝，则点R（注：若有多个最大倾角点，则只取离当前最大倾角顶点Q_i，r最远的那个最大倾角点）必为子凸壳Q_Si的一个顶点。

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

图4.5　子分布域S_i的基线与基线倾角示意图

第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_1，0、Q_2，0构成当前基线Q_1，0Q_2，0；置当前新顶点的序号计数器r初值为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的次新顶点，求出其基线倾角最大化圈绕的基线倾角最大点R_i，j，0（注：若有多个最大倾角点，则只取最远处的那个最大倾角点，即离当前最大倾角顶点Q_i，r最远的那个最大倾角点）；在所得各组基线倾角最大点集{R_i，j，0│1≤j≤n₁）中，找出当前子分布域S_i的基线倾角最大点R，并标记为子凸壳Q_i的最新顶点Q_i，r+1；置序号计数器r为r+1。

第1-1-2步：“删除由子凸壳Q_i的初始顶点Q_i，0，当前次新顶点Q_i，r−1、最新顶点Q_i，r所构成三角形Q_i，0Q_i，r−1Q_i，r的所有点”的子分布域S_i极小化并行处理：

第1-1-2-1步：并行地使子机群COW_i下属各处理机P_ij各自生成“子凸壳Q_i的初始顶点Q_i，0，当前次新顶点Q_i，r−1、最新顶点Q_i，r”所构成的三角形Q_i，0Q_i，r−1Q_i，r，并记为Δ_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，0、最新顶点Q_i，r记为新的基线Q_i，0Q_i，r，回到第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）的并行凸壳新算法研究，而且可进一步改进和提高其算法效率。