第十七章计算几何.doc

编译: –o queen
运行:mpirun –np 4 queen
运行结果:
Solution 1 :
0 * - - - - - - -
4 - - - - * - - -
7 - - - - - - - *
5 - - - - - * - -
2 - - * - - - - -
6 - - - - - - * -
1 - * - - - - - -
3 - - - * - - - -
Solution 2 :
0 * - - - - - - -
6 - - - - - - * -
3 - - - * - - - -
5 - - - - - * - -
7 - - - - - - - *
1 - * - - - - - -
4 - - - - * - - -
2 - - * - - - - -
Solution 3 :
0 * - - - - - - -
6 - - - - - - * -
4 - - - - * - - -
7 - - - - - - - *
1 - * - - - - - -
3 - - - * - - - -
5 - - - - - * - -
2 - - * - - - - -
……(略)
Solution 91 :
1 - * - - - - - -
6 - - - - - - * -
2 - - * - - - - -
5 - - - - - * - -
7 - - - - - - - *
4 - - - - * - - -
0 * - - - - - - -
3 - - - * - - - -
Solution 92 :
1 - * - - - - - -
6 - - - - - - * -
4 - - - - * - - -
7 - - - - - - - *
0 * - - - - - - -
3 - - - * - - - -
5 - - - - - * - -
2 - - * - - - - -
说明:若指定进程数为1,则使用串行算法sequential_eight_queens()求解。
页:2
第十七章计算几何
计算几何是计算机科学中的一个分支,是专门研究有关几何对象问题的。它在图像分析、模式识别、计算机图形学等中应用甚广。本章主要介绍几个基本计算几何问题的简单并行算法和它们的MPI编程实现,包括包含问题、相交问题和凸壳问题等。
包含问题
包含问题(Inclusion Problem)是计算几何中最基本的问题之一。简单的来说,包含问题就是判断点与多边形的位置关系,即点在多边形内,点在多边形外,和点在多边形上。我们这里讨论的仅是点与任意多边形之间的关系,不考虑与任意曲线封闭图形之间的关系。
一个能够画在平面图上而没有任何相交边的图形称为平面图(Planar Graph)。由一些相邻的多边形(称为单图)所组成的图形称为平面细图(Planar Subvision),其中各多边形中除了顶点外,无两边相交。给定一个平面细图和一个顶点p,确定哪个多边形包含了p,此即所谓的包含问题。最简单的情况是判断点p是否在一个多边形Q中。
包含问题及其串行算法
判断点在多边形中的算法的基本思想是先求点和边的交点个数,然后根据交点个数确定点和边的关系。基本步骤是:①过p点向x轴的负半轴方向做一条射线;②求此射线与多边型Q诸边的交点;③判断:交点的个数若为奇数,则p位于Q内;否则p位于Q外。这种测试,对于n边形可在O(n)步内完成。很清楚,这是最优的串行算法,因为读入n条边也至少需要Ω(n)步。
但是需要注意几种特殊的边界情况:首先,过点p的射线与多边形顶点相交,则交点只计数一次;其次,若点p在多边形边上,则也认为点p在多边形中;最后,如果射线与水平边重叠且点p不在该边上,则交点不计数。
单处理机上包含问题算法
输入:点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 ((co