(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,) thenend 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