计算几何课件_第1页
计算几何课件_第2页
计算几何课件_第3页
计算几何课件_第4页
计算几何课件_第5页
已阅读5页,还剩4页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

5计算几何

计算几何是计算机科学中的一个分支,是专门研究有关几何对象问题的。它在图像分析、

模式识别、计算机图形学等中应用甚广。本章主要介绍几个基本计算几何问题的简单并行算

法和它们的MPI编程实现,包括包含问题、相交问题和凸壳问题等。

1.1包含问题

包含问题(InclusionProblem)是计算几何中最基本的问题之一。简单的来说,包含问题就

是判断点与多边形的位置关系,即点在多边形内,点在多边形外,和点在多边形上。我们这

里讨论的仅是点与任意多边形之间的关系,不考虑与任意曲线封闭图形之间的关系。

•个能够画在平面图上而没有任何相交边的图形称为平面图(PlanarGraph)。由一些相

邻的多边形(称为单图)所组成的图形称为平面细图(PlanarSubvision),其中各多边形中

除了顶点外,无两边相交。给定一个平面细图和一个顶点p,确定哪个多边形包含了p,此

即所谓的包含问题。最简单的情况是判断点p是否在一个多边形。中。

1.1.1包含问题及其串行算法

判断点在多边形中的算法的基本思想是先求点和边的交点个数,然后根据交点个数确定

点和边的关系。基本步骤是:①过p点向x轴的负半轴方向做一条射线;②求此射线与多边

型0诸边的交点;③判断:交点的个数若为奇数,则p位于。内;否则p位于。外。这种

测试,对于“边形可在。5)步内完成。很清楚,这是最优的串行算法,因为读入n条边也

至少需要。(")步。

但是需要注意几种特殊的边界情况:首先,过点p的射线与多边形顶点相交,则交点只

计数一次;其次,若点p在多边形边上,则也认为点p在多边形中;最后,如果射线与水平

边重叠且点p不在该边上,则交点不计数。

算法17.1单处理机上包含问题算法

输入:点P坐标多边形0的〃条边E/.Ea,E”的两个端点坐标集合S

输出:点和多边形的关系:true(p位于。内);false(p位于。外)

Begin

(1)count=0

(2)whilei<ndo

ifpisonEjthen

returntrue

elseify=py(x〈px)intersectsEjleftqandqisnotE;low-endthen

count=count+1

endif

endif

endwhile

(3)if((countmod2)=1)then

returntrue

else

returnfalse

endif

End

算法的总运行时间为Z(n)=0(n)o

1.1.2包含问题并行算法

我们介绍两种简单方法来实现上面串行算法的并行化。一种方法是将串行算法中的步

骤2并行化。假设系统有p个处理器,多边形有n条边,将n条边平均分配到这p个处理器

中,每个处理器最多处理[%]条边。具体的处理方法为过p点向x的负半轴方向做一条射

线,判断:如果点是在边上则返回为8;线与边无交点时返回0;如果有交点,那么就有2

种情况,如果交点是边的下顶点,则返回为0,否则,即交点在边上,则返回为1;把一个

处理器中的所有返回值加起来,然后将该值发送到主处理器(my_rank=0),最后主处理器根

据点的个数来判断点与多边形的关系。

另一种方法同样也是将串行算法中的步骤2并行化。假设有p=2°-l个处理器,a为

正整数。p个处理器的编号从根开始自上而下,自左而右逐级向下推进。每个处理器存储多

边形。的一条边,边由其两个端点的迪卡尔坐标表示,点p的坐标为开始时,根

读进(X,,,匕然后传送给树中的其余处理器。当与接收到p的坐标时,他就确定:穿过

P的射线是否和。的边町相交;对于特殊的情况需要利用图形学的知识处理之。如果条件

满足,则与产生“1”输出;否则为“0”。将个处理器的输出相加,若和为奇数,则p位于

Q内;如果为偶数,则p位于Q外;如果和为oo,则输出p在多边形上。

算法17.2多处理机上包含问题算法

输入:点p坐标9,凸);多边形。的〃条边邑,,…,&的两个端点坐标集合S

输出:点和多边形的位置关系:true。位于Q内);false(/;位于Q外)

Begin

(1)count=0

(2)forallP-where1WjWppar-do

resultj=O

endfor

(3)forallP.where1Wj〈ppar-do

fori=ltodo

ifpisonEjxp+jthen

returnresultj=oo

else

ify=Py(xWpx)intersectsEjxp+jleftqandqisnotEjxp+jlow-endthen

resultj=resultj+1

endif

endif

endfor

endfor

(4)forj=ltoppar-doPi

sendsresult)toPo

endfor

(5)forj=ltopdo

count=count+result)

endfor

(6)if((countmod2)=1)or(count=oo)then

returntrue

elsereturnfalse

endif

End

在有p个处理器的情况下,上述算法的时间复杂度为。([%])。

MPI源程序请参见所附光盘。

1.2相交问题

在很多实际应用中,要求确定一组几何物体(目标)是否相交。例如,在模式分类中,必

须确定代表不同类别的空间中的不同区域是否具有共同的子区域;在集成电路设计中,重要

的是要避免导线的交叉和元件的重叠;在计算机图形学中,要求消去三维景象的二维表示中

的隐线和隐面等等。像如上的这些问题都可归结为物体的相交问题(IntersectionProblem)o

设有平面上的两个多边形(允许有边相交)及和。,如果多边形R的一条边和。的一条边相

交,则称7?和。是相交的。所以两个多边形的相交问题可以转化为线段与多边形的相交问题。

三维空间的相交问题与二维平面上的相交问题并没有实质的区别,只是在判断边的相交时比

二维问题上判断边的相交要麻烦,因为三维空间上的点坐标是与3个值有关的。

下面描述的算法都是针对二维平面上的多边形相交而言的。

1.2.1两多边形相交问题及其串行算法

最基本的相交问题是判断两条线段是否相交。而边与多边形相交就是判断一条边和多条

边中的某条边是否相交的算法。要是一个多边形的某条边与另一个多边形的一条边相交,则

就称两个多边形相交。这样两个多边形相交的问题就转化为多条边与一个多边形相交的问

题。

判断线段是否相交的关键是求两条直线的交点,即判断此交点是否在线段上。这和包含

问题有些相似,需要判断点与边的关系。不同点是只须判断点是否在边上。

算法17.3单处理机上的两多边形相交问题算法

输入:多边形R的N条边即4,…,扁的两个端点坐标集合S,多边形。的机条边

FhF2„...,Fm的两个端点坐标集合S2

输出:两个多边形是否相交:true(两多边形相交):false(两多边形不相交)

Begin

fori=ltondo

forj=ltomdo

if(EiintersectsF>)then

returntrue

endif

endfor

endfor

returnfalse

End

显然上述算法所需时间为O(mn)。

1.2.2相交问题的并行算法

下面我们给出两多边形相交问题的朴素并行算法:对于多边形R的每一条边,要确定

其是否与多边形。相交;如果夫的边中有一条边与。相交,那么就可以断定多边形R与。

是相交的。假设R有"条边,。有w条边,总共有p个处理器Pi,Pz,…,Pp。对于R中的每

条边依次判断是否与。相交。

算法17.4两多边形相交问题的并行算法

输入:多边形尺的〃条边©,邑,,.…扁的两个端点坐标集合S”多边形。的机条边

F,,F2“…,Fm的两个端点坐标集合S2

输出:两个多边形是否相交:true(两多边形相交);false(两多边形不相交)

Begin

(1)fori=ltomdo

将E,广播到所有处理器上

endfor

(2)forj=ltomdo

将可广播到所有处理器上

endfor

(3)forallPkwhere1WkWppar-do

fori=ltodo

forj=ltomdo

if(Eixp^intersectsF>)then

resultk=true

endif

endfor

endfor

endfor

(4)将各个处理器上resultk返回到主处理器,如果其中有一个为真,则两多边形相交,

否则两多边形不相交

End

MPI源程序请参见章末附录。

1.3凸壳问题

凸壳(ConvexHull)问题是计算几何中一个重要问题,它的应用很广泛。例如,在图

象处理中可以通过构造凸壳找到数字图象中的凹面;在模式识别中,可视模式的凸壳能够作

为描述模式外形的重要特征;在分类中,一组物体的凸壳就可勾画出这些物体的所属的类;

在计算机图形学中,使用一组点的凸壳可以显示出点簇;在几何问题中,集合S中最远两

点就是凸壳的顶点,等等。

1.3.1凸壳问题及其串行算法

给定平面中的点的集合5={0”02,“”夕“},所谓S之凸壳简记为就是包含S

所有点的最小的凸多边形。实际中,假定平面上的n个点,用n个钉在木板上的图钉表示,

用一条橡皮带缠绕着这些图钉,然后放松橡皮带,在撑紧橡皮带所构成的平面图形就是凸多

边形。

图错误!文档中没有指定样式的文字。17.1图示求凸壳的方法

参照图错误!文档中没有指定样式的文字。17.1,串行算法的基本思路如下:①识别

极点(ExtremePoint):S中那些最大X坐标(XMAX),最大Y坐标(YMAX),最小X坐标(XMIN),

最小Y坐标(YMIN)的那些顶点称为极点;②识别凸边(HullEdge):线段(p,,pQ是CH(S)

的一条凸边,当且仅当S的其余n-2个顶点均位于穿过Pj和的(无限长的)直线的同侧。

由此定义可知,p,和p,一定是CH(S)的顶点;③识别凸点(HullPoint):令p,和p,是CH(S)

上的两连续顶点。假定取p,为坐标原点,那么在所有S中的点,Pj和p,相对于X轴所形

成的正的或负的夹角是最小。这些点称为凸点。

很明显,极点都是C7"型的顶点,任何位于由极点所围成的多边形内的点都不是C"⑸

的顶点,那些在多边形外的点可以归入由XMAX、XMIN、YMAX、YMIN所围成的四边形

与由极点所围成的多边形所形成的四个三角区中。这样问题就归结成为求找这四个三角区中

顶点的凸边,再把这些凸边连接起来就可求得C”

算法17.5单处理机上求凸壳的串行算法

输入:n点集合S={p”“,?”}

输出:返回包含S的凸壳的顶点表列CH(S)

Begin

(1)识别极点,它们都是的顶点

(2)将顶点归入有极点确定的四个三角区中,不在四个三角区中的顶点不需要处理

(3)计算顶点的极角,并排序:

(3.1)依次对属于同一三角区域的点计算极角。然后将有最小极角点的序号作为自己

的Nextindex值

(3.2)然后处理器按照点的Nextindex索引输出点

End

13.2凸壳问题并行算法

假定n个处理器排成网孔形状,处于第i行和第/列的处理器用户(力)表示。点i的坐标

用(巧,匕)表示。首先来介绍两个基本概念和术语:①拓扑结构的转化:给定的n个处理器,

可以认为其是直线拓扑结构。现在将一维拓扑结构改变为2维的,则P(i,j)的i=l,2,3,4,而

j=l,2,-,n/4o②行主处理器:行主处理器是一个人为设定的处理器,纯粹是为了处理上的方

便。在本算法中取p(i,l)为行主处理器。

算法17.6凸壳问题并行算法

输入:n点集合S=p“}

输出:返回凸壳顶点表列CH(S)

Begin

(1)计算极点:

(1.1)第1行的行主处理器向第2,3,4行的行主处理器发送顶点坐标

(1.2)第1、2、3、4行的行主处理器分别计算XMAX、YMIN、YMAX、XMIN;

并把它们的坐标分别存储在4个行主处理器P(l,l)、P(2,l)、P(3,l)、P(4,l)中

(L3)确定极点后,将四条由极点组成的边存储到每一行的行主处理器上

(2)确定S中的顶点是否在四个三角区中:

(2.1)四个行主处理器同时判断顶点是否处于自身所在的区域,其中属于自己区域内

的点,存储到行主处理器中本行要处理的顶点表列

(2.2)将行主处理器上的表列传递到本行中其余的处理器上

(3)计算顶点的极角,并排序输出:

(3.1)每一行上的第i个处理器计算表列中第j个点极角,其中j是mod行处理器数

等于i的数。然后将有最小极角点的序号作为自己的Nextindex值

(3.2)处理器将计算的Nextindex值传递到每行中的主处理器

(3.3)然后每个行主处理器按照从极点开始按Nextindex索引依次输出所得到的极点

上的点

End

MPI源程序请参见所附光盘。

1.4小结

本章主要介绍了计算几何中包含问题、相交问题和凸壳等三个基本问题的并行算法及其

MPI编程及其实现。这些算法可参见文献川。读者如欲进一步学习可参考文献⑵、[3]和[4]。

参考文献

[1].陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,2002.11

[2].AkiSGParallelComputationalGeometry.Prentic-Hall,1992

[3].Atal1ahMJ.GoodrichMT.EfficientParallelSolutionstoSomeGeometricProblems.J.of

ParallelandDistributedComputing,1986,3:492-507

[4].周培德著•计算几何-算法设计与分析.清华大学出版社,广西科学技术出版社,2000.5

附录包含问题并行算法的MPI源程序

1.源程序including.c

#include<mpi.h>if((x>x1)&&(y<=y2)&&(y>y1))

#include<stdio.h>result=l;

else

intn;result=0;

doublextemp[20],ytemp[20];/*点在竖直边上,应该对result赋个比

doublex,y;较的大的值,这里是100*/

ints,mys;if((x==xl)&&((y-yl)*(y2-y)>=0))

intgroup_size,my_rank;result=100;

}

/*判断射线与线段是否有交点*/else

intcal_intcr(intnumber,inti,doublex,doubley){

(/*非竖直边,非水平边*/

doublexl,yl,x2,y2,temp;if(yi!=y2)

intresult;(

result=0;temp=x2+(y-y2)*(x2-xl)/(y2-y1);

/*交点刚好在边上,且不为下顶

if(numbcr+i*group_size>=n)点*/

returnresult;if((tcmp<x)&&(y<=y2)&&(y>y1))

result=l;

xl=xtemp[number+i*group_size];else

y1=ytemp[number+i*group_size];result=0;

x2=xtemp[(number+l+i*group_size)%n];

y2=ytcmp[(numbcr+l+i*group_sizc)%n];/*点在边上,应该对result赋一个

比较的大的值,这里是100*/

if(yi>y2)if((temp==x)&&((y-y2)*

{(yl-y)>=0))

temp=x1;result=100;

xl=x2;}

x2=temp;else

temp=yl;(

yl=y2;/*点在水平边上,应该对result赋

y2=temp;•个比较的大的值,这里是

)100*/

if((y=y1)&&((Xl-x)*(x-x2)>=0))

/*判断竖直边的情况*/result=100;

if(xl==x2)}

returnresult;MPI_Bcast(xtcmp,n,MPI_DOUBLE,0,

)MPI_COMM_WORLD);

MPI_Bcast(ytcmp,n,MPI_DOUBLE,0,

main(intargc,char*argv[])MPI_COMM_WORLD);

(

inti;MPl_Barrier(MPl_COMM_WORLD);

MPI_Init(&argc,&argv);/*每一个处理器处理n/group_size条边上的情

MPI_Comm_rank(MPI_COMM_WORLD,况并求和,对应于算法17.2步骤(3)*/

&my_rank);fbr(i=O;i<n/group_size+1;i-H-)

MPI_Comm_size(MPI_COMM_WORLD,{

&group_size);mys+=cal_inter(my_rank,i,x,y);

}

/*各处理器计数器初始化,对应于

算法17.2步骤(2)*/MPI_Barrier(MPI_COMM_WORLD);

mys=O;

/*把mys的值规约到s,对应于

/*主处理器读入多边形顶点和要判断的点算法17.2步骤(4)和(5)*/

的坐标*/MPI_Rcducc(&mys,&s,1,MPI_INT,MPI_SUM,

if(my_rank==O)0,MPI_COMM_WORLD);

{

printfC请输入点的个数/*根据s值确定输出结果,对应于

scanff%d”,&n);算法17.2步骤(6)*/

printff请输入各点的坐标\n");if(my

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论