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不在该边上,则交点不计数。 算法171单处理机上包含问题算法 输入:点p坐标(PxP);多边形Q的n条边EAE2,…,En的两个端点坐标集合S 输出:点和多边形的关系: true(p位于Q内);fale(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条边EE2,…,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 for (3) for all P; where I≤j≤ppar-do for i=l to if p is on Eixp+] then return result= if y=p,(xpx)intersects Eixp* left q and q is not Eixp+ 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,…,Em的两个端点坐标集合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,…Pp对于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 fo 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={P,P2,Pn},所谓S之凸壳简记为CH/S,就是包含S 所有点的最小的凸多边形。实际中,假定平面上的n个点,用n个钉在木板上的图钉表示, 用一条橡皮带缠绕着这些图钉,然后放松橡皮带,在撑紧橡皮带所构成的平面图形就是凸多 边形。 图1.1图示求凸壳的方法 参照图1.1,串行算法的基本思路如下:①识别极点( Extreme point):S中那些最大 X坐标(XMAX),最大Y坐标(YMAX),最小X坐标(XMIN),最小Y坐标(YMIN)的那些顶点称为 极点:②识别凸边(ul1Edge):线段(P,P)是H(S)的一条凸边,当且仅当S的其余 2个顶点均位于穿过p和P的(无限长的)直线的同侧。由此定义可知,P和P一定是 CH(S)的顶点:③识别凸点( Hull point):令P,和P,是CH(S)上的两连续顶点。假定取P,为 坐标原点,那么在所有S中的点,P和P相对于X轴所形成的正的或负的夹角是最小。这 些点称为凸点。 很明显,极点都是CHS的顶点,任何位于由极点所围成的多边形内的点都不是CH/S 的顶点,那些在多边形外的点可以归入由XMAX、XMN、YMAX、YMN所围成的四边形 与由极点所围成的多边形所形成的四个三角区中。这样问题就归结成为求找这四个三角区中 顶点的凸边,再把这些凸边连接起来就可求得CH/S 算法175单处理机上求凸壳的串行算法 输入:n点集合S={P2,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)依次对属于同一三角区域的点计算极角。然后将有最小极角点的序号作为自己