的 Nextindex值 (32)然后处理器按照点的 Nextindex索引输出点 132凸壳问题并行算法 假定n个处理器排成网孔形状,处于第i行和第j列的处理器用P()表示。点i的坐标 用(x1,y)表示。首先来介绍两个基本概念和术语:①拓扑结构的转化:给定的n个处理器 可以认为其是直线拓扑结构。现在将一维拓扑结构改变为2维的,则P(ij)的F1,2,34,而 j=1,2,…n4。②行主处理器:行主处理器是一个人为设定的处理器,纯粹是为了处理上的方 便。在本算法中取p(i1)为行主处理器。 算法17.6凸壳问题并行算法 输入:n点集合S={P12x…Pn 输出:返回凸壳顶点表列CH(S) Be (1)计算极点 (1.1)第1行的行主处理器向第2,3,4行的行主处理器发送顶点坐标 (1.2)第1、2、3、4行的行主处理器分别计算XMAX、YMN、YMAX、XMN: 并把它们的坐标分别存储在4个行主处理器P(1,1)、P(2,1)、P(3,1)、P(4,1)中 (1.3)确定极点后,将四条由极点组成的边存储到每一行的行主处理器上 (2)确定S中的顶点是否在四个三角区中: (2.)四个行主处理器同时判断顶点是否处于自身所在的区域,其中属于自己区域内 的点,存储到行主处理器中本行要处理的顶点表列 (2.2)将行主处理器上的表列传递到本行中其余的处理器上 (3)计算顶点的极角,并排序输出 (3.1)每一行上的第i个处理器计算表列中第j个点极角,其中j是mod行处理器数 等于i的数。然后将有最小极角点的序号作为自己的 Nextindex值 (3,2)处理器将计算的 Nextindex值传递到每行中的主处理器 (3.3)然后每个行主处理器按照从极点开始按 Nextindex索引依次输出所得到的极点 上的点 MPI源程序请参见所附光盘。 14小结 本章主要介绍了计算几何中包含问题、相交问题和凸壳等三个基本问题的并行算法及其 MPI编程及其实现。这些算法可参见文献[]l读者如欲进一步学习可参考文献[2、[3]秈4] 参考文献 [1]陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,2002.11的 Nextindex 值 (3.2)然后处理器按照点的 Nextindex 索引输出点 End 1.3.2 凸壳问题并行算法 假定 n 个处理器排成网孔形状，处于第 i 行和第 j 列的处理器用 P(i,j)表示。点 i 的坐标 用 ( , ) i i x y 表示。首先来介绍两个基本概念和术语：①拓扑结构的转化：给定的 n 个处理器， 可以认为其是直线拓扑结构。现在将一维拓扑结构改变为 2 维的，则 P(i,j)的 i=1,2,3,4，而 j=1,2,…,n/4。②行主处理器：行主处理器是一个人为设定的处理器，纯粹是为了处理上的方 便。在本算法中取 p(i,1)为行主处理器。 算法 17.6 凸壳问题并行算法 输入：n 点集合 { ,..., } S = p1 pn 输出：返回凸壳顶点表列 CH(S) Begin (1) 计算极点： (1.1)第 1 行的行主处理器向第 2,3,4 行的行主处理器发送顶点坐标 (1.2)第 1、2、3、4 行的行主处理器分别计算 XMAX、 YMIN、 YMAX、 XMIN； 并把它们的坐标分别存储在 4 个行主处理器 P(1,1)、P(2,1)、P(3,1)、P(4,1)中 (1.3)确定极点后，将四条由极点组成的边存储到每一行的行主处理器上 (2) 确定 S 中的顶点是否在四个三角区中： (2.1)四个行主处理器同时判断顶点是否处于自身所在的区域，其中属于自己区域内 的点，存储到行主处理器中本行要处理的顶点表列 (2.2)将行主处理器上的表列传递到本行中其余的处理器上 (3) 计算顶点的极角，并排序输出： (3.1)每一行上的第 i 个处理器计算表列中第 j 个点极角，其中 j 是 mod 行处理器数 等于 i 的数。然后将有最小极角点的序号作为自己的 Nextindex 值 (3.2)处理器将计算的 Nextindex 值传递到每行中的主处理器 (3.3)然后每个行主处理器按照从极点开始按 Nextindex 索引依次输出所得到的极点 上的点 End MPI 源程序请参见所附光盘。 1.4 小结 本章主要介绍了计算几何中包含问题、相交问题和凸壳等三个基本问题的并行算法及其 MPI 编程及其实现。这些算法可参见文献[1]。读者如欲进一步学习可参考文献[2]、[3]和[4]。 参考文献 [1]. 陈国良 编著. 并行算法的设计与分析（修订版）. 高等教育出版社, 2002.11