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 ifreturn 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