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 else1. 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