5计算几何 计算几何是计算机科学中的一个分支,是专门研究有关几何对象问题的。它在图像分析 模式识别、计算机图形学等中应用甚广。本章主要介绍几个基本计算几何问题的简单并行算 法和它们的MPI编程实现,包括包含问题、相交问题和凸壳问题等。 1.1包含问题 包含问题( nclusion problem)是计算几何中最基本的问题之一。简单的来说,包含问题就 是判断点与多边形的位置关系,即点在多边形内,点在多边形外,和点在多边形上。我们这 里讨论的仅是点与任意多边形之间的关系,不考虑与任意曲线封闭图形之间的关系 个能够画在平面图上而没有任何相交边的图形称为平面图( Planar Graph)。由一些相 邻的多边形(称为单图)所组成的图形称为平面细图( Planar Subvision),其中各多边形中 除了顶点外,无两边相交。给定一个平面细图和一个顶点p,确定哪个多边形包含了p,此 即所谓的包含问题。最简单的情况是判断点p是否在一个多边形Q中。 111包含问题及其串行算法 判断点在多边形中的算法的基本思想是先求点和边的交点个数,然后根据交点个数确定 点和边的关系。基本步骤是:过p点向x轴的负半轴方向做一条射线;②求此射线与多边 型Q诸边的交点;③判断:交点的个数若为奇数,则p位于Q内;否则p位于Q外。这种 测试,对于n边形可在O(m)步内完成。很清楚,这是最优的串行算法,因为读入n条边也 至少需要(n)步 但是需要注意几种特殊的边界情况:首先,过点P的射线与多边形顶点相交,则交点只 计数一次;其次,若点p在多边形边上,则也认为点P在多边形中;最后,如果射线与水平 边重叠且点p不在该边上,则交点不计数。 算法17.1单处理机上包含问题算法 输入:点p坐标(PxP);多边形Q的n条边EAE2,…,E的两个端点坐标集合S 输出:点和多边形的关系: true(p位于Q内); false(p位于Q外) Be (2)while i<n do if p is on Ei then return tru else ify=p,(xspx)intersects E; left q and q is not Ei low-end then count=count+1 end if end while (3) if((count mod 2)=1)then else
1. 5 计算几何 计算几何是计算机科学中的一个分支，是专门研究有关几何对象问题的。它在图像分析、 模式识别、计算机图形学等中应用甚广。本章主要介绍几个基本计算几何问题的简单并行算 法和它们的 MPI 编程实现，包括包含问题、相交问题和凸壳问题等。 1.1 包 含 问 题 包含问题(Inclusion Problem)是计算几何中最基本的问题之一。简单的来说，包含问题就 是判断点与多边形的位置关系，即点在多边形内，点在多边形外，和点在多边形上。我们这 里讨论的仅是点与任意多边形之间的关系，不考虑与任意曲线封闭图形之间的关系。 一个能够画在平面图上而没有任何相交边的图形称为平面图（Planar Graph）。由一些相 邻的多边形（称为单图）所组成的图形称为平面细图（Planar Subvision），其中各多边形中 除了顶点外，无两边相交。给定一个平面细图和一个顶点 p，确定哪个多边形包含了 p，此 即所谓的包含问题。最简单的情况是判断点 p 是否在一个多边形 Q 中。 1.1.1 包含问题及其串行算法 判断点在多边形中的算法的基本思想是先求点和边的交点个数，然后根据交点个数确定 点和边的关系。基本步骤是：①过 p 点向 x 轴的负半轴方向做一条射线；②求此射线与多边 型 Q 诸边的交点；③判断：交点的个数若为奇数，则 p 位于 Q 内；否则 p 位于 Q 外。这种 测试，对于 n 边形可在 O(n)步内完成。很清楚，这是最优的串行算法，因为读入 n 条边也 至少需要Ω(n)步。 但是需要注意几种特殊的边界情况：首先，过点 p 的射线与多边形顶点相交，则交点只 计数一次；其次，若点 p 在多边形边上，则也认为点 p 在多边形中；最后，如果射线与水平 边重叠且点 p 不在该边上，则交点不计数。 算法 17.1 单处理机上包含问题算法 输入：点 p 坐标(px,py)；多边形 Q 的 n 条边 E1,E2, ,…,En 的两个端点坐标集合 S 输出：点和多边形的关系：true(p 位于 Q 内)；false(p 位于 Q 外) Begin (1) count=0 (2) while i<n do if p is on Ei then return true else if y=py(x≤px) intersects Ei left q and q is not Ei low-end then count=count+1 end if end if end while (3) if ((count mod 2)=1) then return true else
return false end if 算法的总运行时间为n)=O(n)。 112包含问题并行算法 我们介绍两种简单方法来实现上面串行算法的并行化。一种方法是将串行算法中的步 骤2并行化。假设系统有p个处理器,多边形有n条边,将n条边平均分配到这p个处理器 中,每个处理器最多处理 P 条边。具体的处理方法为过P点向x的负半轴方向做一条射 线,判断:如果点是在边上则返回为∞;线与边无交点时返回0:如果有交点,那么就有2 种情况,如果交点是边的下顶点,则返回为0,否则,即交点在边上,则返回为1:把一个 处理器中的所有返回值加起来,然后将该值发送到主处理器 my rank=0),最后主处理器根 据点的个数来判断点与多边形的关系。 另一种方法同样也是将串行算法中的步骤2并行化。假设有p=2-1个处理器,a为 正整数。p个处理器的编号从根开始自上而下,自左而右逐级向下推进。每个处理器存储多 边形Q的一条边,边由其两个端点的迪卡尔坐标表示,点P的坐标为(xp,y)开始时,根 读进(x,y2),然后传送给树中的其余处理器。当P,接收到P的坐标时,他就确定:穿过 P的射线是否和Q的边e,相交;对于特殊的情况需要利用图形学的知识处理之。如果条件 满足,则P产生“1”输出;否则为“0”。将个处理器的输出相加,若和为奇数,则p位于 Q内;如果为偶数,则p位于Q外;如果和为∞,则输出p在多边形上。 算法172多处理机上包含问题算法 输入:点P坐标(DxP;多边形Q的n条边EAE2,…,En的两个端点坐标集合S 输出:点和多边形的位置关系:true(p位于Q内); false(p位于Q外) Begi (1)count=0 (2) for all p; where 1≤j≤ p par-do result =o end fo (3) for all P; where 1≤j≤ p par-do for i=l to if p is on Eixp+] then return result= ify=p,(xpx)intersects Eixp+; left q and q is not Eixp*i low-end then end if
return false end if End 算法的总运行时间为 t(n)=O(n)。 1.1.2 包含问题并行算法 我们介绍两种简单方法来实现上面串行算法的并行化。一种方法是将串行算法中的步 骤 2 并行化。假设系统有 p 个处理器，多边形有 n 条边，将 n 条边平均分配到这 p 个处理器 中，每个处理器最多处理 p n 条边。具体的处理方法为过 p 点向 x 的负半轴方向做一条射 线，判断：如果点是在边上则返回为 ；线与边无交点时返回 0；如果有交点，那么就有 2 种情况，如果交点是边的下顶点，则返回为 0，否则，即交点在边上，则返回为 1；把一个 处理器中的所有返回值加起来，然后将该值发送到主处理器(my_rank=0)，最后主处理器根 据点的个数来判断点与多边形的关系。 另一种方法同样也是将串行算法中的步骤 2 并行化。假设有 p=2α -1 个处理器， 为 正整数。p 个处理器的编号从根开始自上而下，自左而右逐级向下推进。每个处理器存储多 边形 Q 的一条边，边由其两个端点的迪卡尔坐标表示，点 p 的坐标为( p p x , y )。开始时，根 读进 ( , ) p p x y ，然后传送给树中的其余处理器。当 Pj 接收到 p 的坐标时，他就确定：穿过 p 的射线是否和 Q 的边 j e 相交；对于特殊的情况需要利用图形学的知识处理之。如果条件 满足，则 Pj 产生“1”输出；否则为“0”。将个处理器的输出相加，若和为奇数，则 p 位于 Q 内；如果为偶数，则 p 位于 Q 外；如果和为 ，则输出 p 在多边形上。 算法 17.2 多处理机上包含问题算法 输入：点 p 坐标(px,py)；多边形 Q 的 n 条边 E1,E2, ,…,En 的两个端点坐标集合 S 输出：点和多边形的位置关系：true(p 位于 Q 内)；false(p 位于 Q 外) Begin (1) count=0 (2) for all Pj where 1≤j≤p par-do resultj=0 end for (3) for all Pj where 1≤j≤p par-do for i=1 to p n do if p is on Ei×p+j then return resultj= else if y=py(x≤px) intersects Ei×p+j left q and q is not Ei×p+j low-end then resultj= resultj+1 end if end if end for
(4)for j=l to p par-do Pi sends result, to Po (5)forl to p do count= count+ result end for (6 if((count mod 2)=1)or(count=oo )then return true else return false end if 在有P个处理器的情况下,上述算法的时间复杂度为o MPI源程序请参见所附光盘。 12相交问题 在很多实际应用中,要求确定一组几何物体(目标)是否相交。例如,在模式分类中,必 须确定代表不同类别的空间中的不同区域是否具有共同的子区域:在集成电路设计中,重要 的是要避免导线的交叉和元件的重叠:在计算机图形学中,要求消去三维景象的二维表示中 的隐线和隐面等等。像如上的这些问题都可归结为物体的相交问题 Intersection Problem) 设有平面上的两个多边形(允许有边相交R和Q,如果多边形R的一条边和Q的一条边相 交,则称R和Q是相交的。所以两个多边形的相交问题可以转化为线段与多边形的相交问题。 三维空间的相交问题与二维平面上的相交问题并没有实质的区别,只是在判断边的相交时比 二维问题上判断边的相交要麻烦,因为三维空间上的点坐标是与3个值有关的 下面描述的算法都是针对二维平面上的多边形相交而言的。 121两多边形相交问题及其串行算法 最基本的相交问题是判断两条线段是否相交。而边与多边形相交就是判断一条边和多条 边中的某条边是否相交的算法。要是一个多边形的某条边与另一个多边形的一条边相交,则 就称两个多边形相交。这样两个多边形相交的问题就转化为多条边与一个多边形相交的问 题 判断线段是否相交的关键是求两条直线的交点,即判断此交点是否在线段上。这和包含 问题有些相似,需要判断点与边的关系。不同点是只须判断点是否在边上 算法17.3单处理机上的两多边形相交问题算法 输入:多边形R的n条边E,E3,…,En的两个端点坐标集合S,多边形Q的m条边 F1,F2,,Fm的两个端点坐标集合S2 输出:两个多边形是否相交:true(两多边形相交); false(两多边形不相交) for i=l to n do for j=l to m do if (Ei intersects F,) then
end for (4) for j=1 to p par-do Pj sends resultj to P0 end for (5) for j=1 to p do count= count+ resultj end for (6) if ((count mod 2)=1) or (count= ) then return true else return false end if End 在有 p 个处理器的情况下，上述算法的时间复杂度为 O( p n )。 MPI 源程序请参见所附光盘。 1.2 相交问题 在很多实际应用中，要求确定一组几何物体(目标)是否相交。例如，在模式分类中，必 须确定代表不同类别的空间中的不同区域是否具有共同的子区域；在集成电路设计中，重要 的是要避免导线的交叉和元件的重叠；在计算机图形学中，要求消去三维景象的二维表示中 的隐线和隐面等等。像如上的这些问题都可归结为物体的相交问题(Intersection Problem)。 设有平面上的两个多边形(允许有边相交)R和Q，如果多边形R的一条边和Q的一条边相 交，则称R和Q是相交的。所以两个多边形的相交问题可以转化为线段与多边形的相交问题。 三维空间的相交问题与二维平面上的相交问题并没有实质的区别，只是在判断边的相交时比 二维问题上判断边的相交要麻烦，因为三维空间上的点坐标是与3个值有关的。 下面描述的算法都是针对二维平面上的多边形相交而言的。 1.2.1 两多边形相交问题及其串行算法 最基本的相交问题是判断两条线段是否相交。而边与多边形相交就是判断一条边和多条 边中的某条边是否相交的算法。要是一个多边形的某条边与另一个多边形的一条边相交，则 就称两个多边形相交。这样两个多边形相交的问题就转化为多条边与一个多边形相交的问 题。 判断线段是否相交的关键是求两条直线的交点，即判断此交点是否在线段上。这和包含 问题有些相似，需要判断点与边的关系。不同点是只须判断点是否在边上。 算法 17.3 单处理机上的两多边形相交问题算法 输入：多边形 R 的 n 条边 E1,E2,,…,En 的两个端点坐标集合 S1，多边形 Q 的 m 条边 F1,F2,,…,Fm 的两个端点坐标集合 S2 输出：两个多边形是否相交：true(两多边形相交)；false(两多边形不相交) Begin for i=1 to n do for j=1 to m do if (Ei intersects Fj ) then
return true end for return false 显然上述算法所需时间为Omn)。 122相交问题的并行算法 下面我们给出两多边形相交问题的朴素并行算法:对于多边形R的每一条边,要确定 其是否与多边形Q相交;如果R的边中有一条边与Q相交,那么就可以断定多边形R与Q 是相交的。假设R有n条边,Q有m条边,总共有p个处理器P1,P2,…,Ppo对于R中的每 条边依次判断是否与Q相交。 算法174两多边形相交问题的并行算法 输入:多边形R的n条边El,E2,…,En的两个端点坐标集合S,多边形Q的m条边 F1,F2,,Fm的两个端点坐标集合S2 输出:两个多边形是否相交:true(两多边形相交): false(两多边形不相交) Be (1)for il to m do 将F广播到所有处理器上 end for 将E广播到所有处理器上 end for (3) for all Pk where 1≤k≤ p par-do for i= l to for j=I to m do if (Ei xpr intersects F,) then result=true end if end for (4)将各个处理器上 result返回到主处理器,如果其中有一个为真,则两多边形相交, 否则两多边形不相交 MPI源程序请参见章末附录。 13凸壳问题 凸壳( Convex hul)问题是计算几何中一个重要问题,它的应用很广泛。例如,在图 象处理中可以通过构造凸壳找到数字图象中的凹面:在模式识别中,可视模式的凸壳能够作
return true end if end for end for return false End 显然上述算法所需时间为 O(mn)。 1.2.2 相交问题的并行算法 下面我们给出两多边形相交问题的朴素并行算法：对于多边形 R 的每一条边，要确定 其是否与多边形 Q 相交；如果 R 的边中有一条边与 Q 相交，那么就可以断定多边形 R 与 Q 是相交的。假设 R 有 n 条边，Q 有 m 条边，总共有 p 个处理器 P1 ,P2 ,…,Pp。对于 R 中的每 条边依次判断是否与 Q 相交。 算法 17.4 两多边形相交问题的并行算法 输入：多边形 R 的 n 条边 E1,E2,,…,En 的两个端点坐标集合 S1，多边形 Q 的 m 条边 F1,F2,,…,Fm 的两个端点坐标集合 S2 输出：两个多边形是否相交：true(两多边形相交)；false(两多边形不相交) Begin (1) for i=1 to m do 将 Fi 广播到所有处理器上 end for (2) for j=1 to m do 将 Ej 广播到所有处理器上 end for (3) for all Pk where 1≤k≤p par-do for i=1 to p n do for j=1 to m do if (Ei×p+k intersects Fj ) then resultk=true end if end for end for end for (4) 将各个处理器上 resultk 返回到主处理器，如果其中有一个为真，则两多边形相交， 否则两多边形不相交 End MPI 源程序请参见章末附录。 1.3 凸壳问题 凸壳（Convex Hull）问题是计算几何中一个重要问题，它的应用很广泛。例如，在图 象处理中可以通过构造凸壳找到数字图象中的凹面；在模式识别中，可视模式的凸壳能够作
为描述模式外形的重要特征;在分类中,一组物体的凸壳就可勾画出这些物体的所属的类 在计算机图形学中,使用一组点的凸壳可以显示出点簇;在几何问题中,集合S中最远两 点就是凸壳的顶点,等等。 131凸壳问题及其串行算法 给定平面中的点的集合S={P1,P2…,Pn},所谓S之凸壳简记为CHS,就是包含S 所有点的最小的凸多边形。实际中,假定平面上的n个点,用n个钉在木板上的图钉表示, 用一条橡皮带缠绕着这些图钉,然后放松橡皮带,在撑紧橡皮带所构成的平面图形就是凸多 边形。 图1.1图示求凸壳的方法 参照图1.1,串行算法的基本思路如下:①识别极点( Extreme point):S中那些最大 X坐标(XMAX),最大Y坐标(YMAX),最小X坐标(XMIN),最小Y坐标(YMIN)的那些顶点称为 极点:②识别凸边( Hull edge):线段(P,P)是CH(s)的一条凸边,当且仅当S的其余 2个顶点均位于穿过P和p的(无限长的)直线的同侧。由此定义可知,P1和P一定是 CH(S)的顶点:③识别凸点( Hull point):令P和P是CH(S)上的两连续顶点。假定取P为 坐标原点,那么在所有S中的点,P和P相对于X轴所形成的正的或负的夹角是最小。这 些点称为凸点。 很明显,极点都是CH(S的顶点,任何位于由极点所围成的多边形内的点都不是CHS) 的顶点,那些在多边形外的点可以归入由XMAX、XMN、YMAX、YMN所围成的四边形 与由极点所围成的多边形所形成的四个三角区中。这样问题就归结成为求找这四个三角区中 顶点的凸边,再把这些凸边连接起来就可求得CH/S 算法175单处理机上求凸壳的串行算法 输入:n点集合S={Pp1,Pn} 输出:返回包含S的凸壳的顶点表列CH(S) B (1)识别极点,它们都是CHS的顶点 (2)将顶点归入有极点确定的四个三角区中,不在四个三角区中的顶点不需要处理 (3)计算顶点的极角,并排序 (31)依次对属于同一三角区域的点计算极角。然后将有最小极角点的序号作为自己
为描述模式外形的重要特征；在分类中，一组物体的凸壳就可勾画出这些物体的所属的类； 在计算机图形学中，使用一组点的凸壳可以显示出点簇；在几何问题中，集合 S 中最远两 点就是凸壳的顶点，等等。 1.3.1 凸壳问题及其串行算法 给定平面中的点的集合 { , ,..., } S = p1 p2 pn ，所谓 S 之凸壳简记为 CH(S)，就是包含 S 所有点的最小的凸多边形。实际中，假定平面上的 n 个点，用 n 个钉在木板上的图钉表示， 用一条橡皮带缠绕着这些图钉，然后放松橡皮带，在撑紧橡皮带所构成的平面图形就是凸多 边形。 YMAX YMIN XMAX XMIN 图 1.1 图示求凸壳的方法 参照图 1.1，串行算法的基本思路如下：①识别极点（Extreme Point）：S 中那些最大 X 坐标(XMAX)，最大 Y 坐标(YMAX)，最小 X 坐标(XMIN)，最小 Y 坐标(YMIN)的那些顶点称为 极点；②识别凸边(Hull Edge)：线段 ( , ) pi p j 是 CH(S)的一条凸边，当且仅当 S 的其余 n －2 个顶点均位于穿过 i p 和 j p 的(无限长的)直线的同侧。由此定义可知， i p 和 j p 一定是 CH(S)的顶点；③识别凸点(Hull Point)：令 i p 和 j p 是 CH(S)上的两连续顶点。假定取 i p 为 坐标原点，那么在所有 S 中的点， j p 和 i p 相对于 X 轴所形成的正的或负的夹角是最小。这 些点称为凸点。 很明显，极点都是 CH(S)的顶点，任何位于由极点所围成的多边形内的点都不是 CH(S) 的顶点，那些在多边形外的点可以归入由 XMAX、XMIN、YMAX、YMIN 所围成的四边形 与由极点所围成的多边形所形成的四个三角区中。这样问题就归结成为求找这四个三角区中 顶点的凸边，再把这些凸边连接起来就可求得 CH(S)。 算法 17.5 单处理机上求凸壳的串行算法 输入：n 点集合 { ,.., } S = p1 pn 输出：返回包含 S 的凸壳的顶点表列 CH(S) Begin (1) 识别极点，它们都是 CH(S)的顶点 (2) 将顶点归入有极点确定的四个三角区中，不在四个三角区中的顶点不需要处理 (3) 计算顶点的极角，并排序： (3.1)依次对属于同一三角区域的点计算极角。然后将有最小极角点的序号作为自己
的 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
[2]. AkI SG. Parallel Computational Geometry. Prentic-Hall, 199 3]. Atallah MJ. Goodrich MT. Efficient Parallel Solutions to Some Geometric Problems. J. of Parallel and Distributed Computing, 1986, 3: 492-507 [4].周培德著.计算几何-算法设计与分析.清华大学出版社,广西科学技术出版社,20005 附录包含问题并行算法的MP源程序 1.源程序 includingc #include #include f(x>x1)k&(yy1) double xtemp20ytemp[20] double x, result=o Int s, mys, 点在竖直边上,应该对 result赋一个比 int group size, my rank; 较的大的值,这里是100* if(x==x1)&&(-y1)*(y2y)>=0) /判断射线与线段是否有交点 int cal inter(int number, int i, double x, double y) double xl, y1, x2, y2, temp; 非竖直边,非水平边* if yll=y2) if(number+i*group si )*(x2x1y2-y1) 交点刚好在边上,且不为下顶 xI=temp[number+i*group size]: if(tempy1)) result x2=temp[(number+ 1+i group size)%n y2=-ytemp((number+ 1+i*group size)%n]: result=0 if(y1>y2) 点在边上,应该对 result赋一个 比较的大的值,这里是100* <2-temp resultion. 点在水平边上,应该对 result赋 一个比较的大的值,这里是 判断竖直边的情况 100*/
[2]. Akl S G. Parallel Computational Geometry. Prentic-Hall, 1992 [3]. Atallah M J. Goodrich M T. Efficient Parallel Solutions to Some Geometric Problems. J. of Parallel and Distributed Computing, 1986, 3: 492-507 [4]. 周培德 著. 计算几何-算法设计与分析. 清华大学出版社,广西科学技术出版社, 2000.5 附录 包含问题并行算法的 MPI 源程序 1. 源程序 including.c #include #include int n; double xtemp[20],ytemp[20]; double x,y; int s,mys; int group_size,my_rank; /*判断射线与线段是否有交点*/ int cal_inter(int number,int i,double x,double y) { double x1,y1,x2,y2,temp; int result; result=0; if(number+i*group_size>=n) return result; x1=xtemp[number+i*group_size]; y1=ytemp[number+i*group_size]; x2=xtemp[(number+1+i*group_size)%n]; y2=ytemp[(number+1+i*group_size)%n]; if(y1>y2) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; } /*判断竖直边的情况*/ if(x1==x2) { if((x>x1)&&(yy1)) result=1; else result=0; /*点在竖直边上，应该对 result 赋一个比 较的大的值，这里是 100*/ if((x==x1)&&((y-y1)*(y2-y)>=0)) result=100; } else { /*非竖直边，非水平边*/ if (y1!=y2) { temp=x2+(y-y2)*(x2-x1)/(y2-y1); /*交点刚好在边上，且不为下顶 点*/ if((tempy1)) result=1; else result=0; /*点在边上，应该对 result 赋一个 比较的大的值，这里是 100*/ if((temp==x)&&((y-y2)* (y1-y)>=0)) result=100; } else { /*点在水平边上，应该对 result 赋 一个比较的大的值，这里是 100*/
if(y=y1)k&&(xl-x)°(X-x2)>=0) MPI Bcast( &x, 1, MPI DOUBLE,0 result=100 MPI COMM WORLD MPI Bcast(&y, 1, MPI DOUBLE,O, MPI COMM WORLD) return result, MPl Bcast(temp, n, MPI DOUBLE,O, MPI COMM WORLD) MPI Bcast(temp, n, MPI DOUBLE, 0, main(int argc, char* argv) MPI COMM WORLD) I 1, MPI Barrier(MPI COMM WORLD) MPI Init( &argc, &argv); /每一个处理器处理 n/group size条边上的情 MPI Comm rank(MPI COMM WORLD, 况并求和,对应于算法172步骤(3)* for(i0 i<n/group size+1; i++) MPI Comm size(MPI COMM WORLd &group size), mys+=cal inter(my rank, i, x, y) 各处理器计数器初始化,对应于 算法17.2步骤(2)* MPI Barrier(MPI COMM WORLD) /把mys的值规约到s,对应于 /主处理器读入多边形顶点和要判断的点 算法172步骤(4)和(5) 的坐标 MPI Reduce( &mys, &s, 1, MPI INT, MPI SUM my rank==0) O, MPI COMM WORLD); printf("请输入点的个数") γ根据s值确定输出结果,对应于 算法172步骤(6)° printf"请输入各点的坐标n") if( my rank==0) for(F=0;<n;i++) printf("%d: , 1), printf("vertex p is in polygon); scanf("%lf", &temp: scanf("%lf", &temp]); if(s%2==1) printf("请输入要判断点的坐标n"), polygonin"); scanf("%f %lf, &x, &y ) printf("vertex p is out of MPI Barrier(MPI COMM WORLD /把多边形的顶点数、顶点坐标与要判别的点} 坐标播送给所有进程 MPI Bcast(&n, 1, MPI INTO MPI COMM WORLD)
if((y==y1)&&((x1-x)*(x-x2)>=0)) result=100; } } return result; } main(int argc,char* argv[]) { int i; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD, &my_rank); MPI_Comm_size(MPI_COMM_WORLD, &group_size); /*各处理器计数器初始化，对应于 算法 17.2 步骤(2)*/ mys=0; /*主处理器读入多边形顶点和要判断的点 的坐标*/ if(my_rank==0) { printf("请输入点的个数:"); scanf("%d",&n); printf("请输入各点的坐标\n"); for(i=0;i=100) printf("vertex p is in polygon\n"); else if(s%2==1) printf("vertex p is in polygon\n"); else printf("vertex p is out of polygon\n"); } MPI_Finalize(); }
2.运行实例 编译: mpicc including c- o including 运行:可以使用命令 mpirun- np SIZE including来运行该串匹配程序,其中SIZE是所使用 的处理器个数。本实例中使用了SIEE=4个处理器 mpirun-np 4 including 运行结果 请输入点的个数6 请输入各点的坐标 0:10 l:21 2:40 3:24 4:12 5:03 请输入要判断点的坐标 23 结果: vertex p is in polygon 说明:输入顶点的(xy)坐标时中间用空格隔开
2. 运行实例 编译：mpicc including.c –o including 运行：可以使用命令 mpirun –np SIZE including 来运行该串匹配程序，其中 SIZE 是所使用 的处理器个数。本实例中使用了 SIZE=4 个处理器。 mpirun –np 4 including 运行结果： 请输入点的个数:6 请输入各点的坐标 0：1 0 1：2 1 2：4 0 3：2 4 4：1 2 5：0 3 请输入要判断点的坐标 2 3 结果：vertex p is in polygon 说明：输入顶点的(x,y)坐标时中间用空格隔开