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）问题是计算几何中一个重要问题，它的应用很广泛。例如，在图 象处理中可以通过构造凸壳找到数字图象中的凹面；在模式识别中，可视模式的凸壳能够作