第五章---图形运算.ppt

第五章图形运算,第一节线段的交点计算,两条线段求交,设有两线段AB和CD,其端点坐标分别为(xa,ya),(xb,yb)和(xc,yc),(xd,yd),它们所在直线的参数方程分别为：,若两线段相交,则交点的参数值,应满足:,即,因此,若行列式,表示两线段AB和CD重合或平行。一般做为它们不相交来处理。如果0,则可求出交点对应的两个参数值:,需要注意,只有,时两线段才真正相交。否则,交点在两线段或其中某一条线段的延长线上,这时仍然认为是两线段不相交。,两线段AB和CD交点的算法,1.计算行列式(xb-xa)(yc-yd)-(xc-xd)(yb-ya)若=0,则两线段重合或平行,可算做无交点,算法结束;2.计算交点参数(xc-xa)(yc-yd)-(xc-xd)(yc-ya)/若1,则无交点,算法结束;(xb-xa)(yc-ya)-(xc-xa)(yb-ya)/若1,则无交点,算法结束;,3.计算交点xxa+(xb-xa),yya+(yb-ya),输出交点(x,y)后算法结束;,多条线段求交,寻找这样的算法,其计算工作量要大体上与交点个数成正比,即只对有可能相交的两线段计算交点,对不可能相交的线段不计算交点,使算法有更好的效率。,我们称平面内两条线段在横坐标x处是可比较的,如果存在一条通过x的垂直线,此线与两条线段都相交。我们规定一个在x处的上面关系为：在x处,线段S1在S2的上面,记为S1xS2,如果在x处可比较,且S1与垂直线的交点位于S2与垂直线的交点的上面。,其中，S2S4,S1S2,S2S4,S1S4,规定的次序关系对垂直的线段不适合两线段相交的必要条件,即若两线段相交,则必然存在某个x,使它们在规定的次序关系x下是相邻的。算法从左向右扫描,在扫描过程维持正确的线段间上述次序关系。这种次序关系只能有三种可能的变化方式:1遇见某条线段S的左端点,此时S应加入次序关系。2遇见某线段S的右端点,此时S应从次序关系中删除。3遇到某两条线段S1和S2的交点,这时在次序关系中S1和S2交换位置。,算法实施需要两个基本的数据结构:扫描线状态表和事件点进度表扫描线状态表L中存放按所规定次序关系x排序的线段的序列。此表初始应为空,在平面扫描过程中当关系x改变时变化。事件点指扫描进行中可能使所规定次序关系x发生变化的点,存放于事件点进度表E中,该表初始时应是排序的要求交点的各线段端点的坐标。在平面扫描过程中求出的交点,应及时地插入到事件点进度表中。,扫描线状态表应能支持以下四个操作:(1)INSERT(S,L),把线段S插入到扫描线状态表L中,注意应插入到适当位置以保持正确的次序关系。(2)DELETE(S,L),从L中删除线段S。(3)ABOVE(S,L),返回次序关系中S上面紧接着的线段的编号。(4)BELOW(S,L),返回次序关系中S下面紧接着的线段的编号。,事件点进度表E应能支持以下三个操作:(1)MIN(E),取出表E中的最小元素。(2)INSERT(x,E),把横坐标为x的一个点插入到表E中,插入要使E中事件点存放保持递增次序。(3)MEMBER(x,E),判定横坐标为x的点是否在事件点进度表E中。,算法:,1.事件点进度表E初始化将输入待求交点的n条线段的2n个端点按x,y字典式排序后存放于表E中;2.准备收集交点A;A是一集合,初为空,准备存入找到的交点;3.平面扫描若表E不为空,则进行(3.1)(3.3)循环。直到表E为空时算法结束。3.1取出当前事件点PMIN(E)；3.2当前事件点处理考查当前事件点P,分三种情况:(1)若P是边S的左端点,则做：INSERT(S,L);,S1=ABOVE(S,L);S2=BELOW(S,L);若S和S1相交,则求出的交点送入集和A中;若S和S2相交,则求出的交点送入集和A中;(2)若P是边S的右端点,则做：S1=ABOVE(S,L);S2=BELOW(S,L);若S1和S2相交于点P的右边,则求出的交点送入集和A中；DELETE(S,L)；(3)若P是边S1和S2的交点,且在P的左边S1=ABOVE(S2),则做,S3=ABOVE(S1,L);S4=BELOW(S2,L);若S3和S2相交，则求出的交点送入集合A中；若S4和S1相交，则求出的交点送入集合A中；在L中交换S1和S2的位置；3.3处理找到的交点若集合A不为空，做下面循环，直至A为空：取出集合A中一个交点，其横坐标是x；若MEMBER(x,E)为FALSE,则输出此交点，并做INSERT(x,E);,设有三条线段S1，S2，S3,它们的坐标如下(1,1),(5,3,),(2,3),(4,1),(6,4),(8,2).要计算所有交点。,算法初始形成的事件点进度表E，可有形式(1,1),S1左端点)，(2,3),S2左端点)，(4,1),S2右端点)，(5,3),S1右端点)，(6,4),S3左端点)，(8,8),S3右端点),第二节多边形表面的交线计算,设两个要求交线的多边形表面都是凸多边形表面,分别由它们的顶点坐标逆时针方向的序列确定,即约定按顶点序列前行时内部在左侧。根据顶点坐标求出两个多边形表面分别所在平面的方程,再根据平面方程计算交线,最后,还要确定出交线同时在两个多边形表面内部的部分,求平面方程采用多个顶点位置坐标来计算平面方程可以减少由于不共面而引起的偏差。设要求出通过若干顶点的平面方程Ax+By+Cz+D=0,即要定出系数A,B,C,D,可采用如下做法平面方程Ax+By+Cz+D=0的系数A,B,C与该平面上多边形分别在x=0,y=0,z=0三个坐标平面上投影的面积成比例,多边形在z=0平面上投影的面积S可如下求出:式中若i=n则j=1,否则j=i+1。类似地可计算多边形表面在x=0和y=0平面上投影的面积,从而确定A,B,然后D可通过代入平面上一点坐标数值来求出。,于是有S=(y1+y2)(x1-x2)十(y2+y3)(x2-x3）+(y3+y1)(x3-x1),若给出空间若干点的坐标(x1,y1,z1),(x2,y2,z2),.(xn,yn,zn),注意这里没有要求这些点共面或围成了凸多边形,都可以求出通过或接近这些点的一个平面方程Ax+By+Cz+D=0:,D=-Ax1-By1-Cz1,式中若i=n,则j=1,否则j=i+1,平面方程的求交,A1x+B1y+C1z+D1=0A2x+B2y+C2z+D2=0,两平面重合或平行,一般算没有交点,分别对每个多边形表面各边相应的线段,计算它与另一个多边形表面所在平面的交点。注意这里是求线段与平面的交点,即交点在线段延长线上时算不相交。假定两个多边形表面都是凸的,故共可以交出四个交点。,线段与平面的交点计算,空间线段两个端点的坐标(x1,y1,z1)和x2,y2,z2)给出,平面方程Ax+By+Cz+D=0。,代入平面方程,得:A(x1+(x2-x1)t)+B(y1+(y2-y1)t)+C(z1+(z2-zl)t)+D=0整理得到:A(x2-x1)+B(y2-y1)+C(z2-zl)t=-(Ax1+By1+Cz1+D)于是知道,若A(x2-x1)+B(y2-y1)+C(z2-z1)=0则所给线段在平面上或与平面平行,没有唯一确定的交点。否则,交点对应的参数t可以求出:,第三节平面中的凸壳算法,凸壳包含一个平面点集的最小凸区域凸区域指要求区域内任意两点的连线仍在该区域内。设S是平面上n个点的集合,则S的凸壳是一个凸多边形,它包含所有n点且面积最小。事实上求点集S的凸壳就是要在S中选出壳上的点并排出围成凸多边形的次序。,Graham扫描算法处理的思路是设想有一内点O并且不妨设想O就是坐标原点,这时点集S中所有各点相对轴OX有一个倾角。所有各点按倾角递增排序后,如果某一点不是壳上顶点,则它必然在两个壳顶点与点O形成的三角形内部。Graham扫描的实质是围绕已经按倾角排序的各顶点进行一次扫描,在扫描过程中消去在凸壳内部的点,留下以希望次序排列的壳顶点。,由于是按倾角递增排序,可知若连续三个顶点P1,P2,P3是一个“右转”，则P2是一个应去掉的内点。,对给出的三点P1,P2,P3,设它们的坐标是(x1,y1),(x2,y2),(x3,y3),这时要判断三点在P2处形成一个右转还是左转,可以计算下面的行列式,其中给出的是带有正负号的三角形P1P2P3面积的2倍,因此若0,则P1,P2,P3是左转;0,则是右转;=0,则三点共线。,实现此算法可选点集S中x坐标最小的点为内点O,设想过O有一条向右的射线,对其余各点,相对该射线计算倾角然后再排序。,Graham扫描算法1.倾角排序选出输入点集S中x坐标最小的点,若这样的点不唯一则再由其中选出y坐标最小的点,设为O。设想有一条从O向右的射线OX,对点集中其余每一点P,计算倾角POX,再按倾角排序,得点序列Q1=O,Q2,Q3,Qn;2.准备扫描vQ1;,3.扫描若NEXT(v)Q1,则循环执行下面操作,至NEXT(v)=Q1时止,此时点序列中剩下排成凸多边形的壳上顶点,算法结束。若三个相继的点v,NEXT(v),NEXT(NEXT(v)形成一个左转,则vNEXT(v);否则,先删除NEXT(v),再做vPRED(v);NEXT(v)和PRED(v)是两个函数,其值分别为算法操作的点序列中v的下一点和前一点。这里取下一点和前一点时认为点序列是首尾相接的,即若v是点序列中第一点,则PRED()是点序列中最后一点;若v是最后一点,NEXT(v)是第一点。,P3,P2,P1,P0,P0P1P2左转，P1P2P3右转，P0P1P3右转。,倾角计算记P点坐标为(Xp,Yp),O点坐标(X0,Y0),这个角度数可如下简单地计算:,B=yp-y。若B0则角度数=1-A,否则角度数=3+A。这里A是向量OP与OX向上单位向量的内积,因此是倾角的余弦数值。B用以判断该倾角是否大于180度。,Jarvis行进算法想法是若相继两点是一条凸壳多边形的边,则对于过该边的直线,所有点集中的凸壳中的顶点在该直线同侧。因此若找到pq是壳上一边,则以q为端点的下一条壳边qr可以如下求出：计算点集中其余各点相对q点发出沿向量pq向的射线的倾角,若倾角最小者对应的点是r,则qr是下一条壳边寻找开始行进的第一条壳边,可以选出点集中按x,y坐标字典式次序的最低点,该点必定是一个壳顶点。可从该点引一条竖直向下的射线,在此做一个行进步就找到了第一条壳边。,Jarvis算法,1.准备v0点集S中按x,y字典次序最小的点;d竖直向下的一个方向向量;点v0送入收集凸壳顶点的队列Q中;S1S-v0;uv02.一步行进v1Wrapping(u,d,S1);3.准备下次若v1v0,则做:v1接入队Q后部;S1=S-u,v1;d从u到v1的一个方向向量;,uv1返步2。4.结束壳顶点已经全部存入队Q中,算法结束.其中第2步引入函数Wrapping来实现一步行进。此函数的工作是,对S1中所有各点,相对自u发出方向为d的射线,计算所成倾角。在所有倾角中取最小,若有多个则选与u距离最远的那个,它对应的点为函数的返回值。因此在步2求得的v1是一个行进步找到的下个壳顶点。Jarvis若点集S中只有较少数点在壳上,则算法效率很高。若点集S中绝大多数点都在壳上,算法的效率一般来说就不如Graham扫描了。,第四节包含与重叠,简单多边形的包含算法平面上的简单多边形是不相邻的边不能相交的多边形,设它用顶点坐标的逆时针序列（x0,y0）,(x1,y1),(xn-1,yn-1)确定,即沿顶点序列前行时内部在左侧。对平面上坐标为(xp,yp)的任意一点P,包含性检验问题是判断它是否在所给出简单多边形的内部。,一个简便的判断方法是由P做竖直向下的射线,计算此射线与多边形各边交点的个数。,当由点P竖直向下的射线恰好通过多边形的顶点或某一边时,交点计数可采取简单的左闭右开法来处理,即:当多边形一边的两个顶点的x坐标都小于或等于点P的x坐标时,相应交点不计算在内。,简单多边形包含性检验的算法,1.准备xnx0,yny0,m-1,i0;2.排除必不相交情形若下列条件有一个成立,则到4。2.1xpxi并且xpxi+1:2.2xpxi并且xpxi+1;2.3ypyi并且ypyi+1;3.计算交点y=yi+(xp-xi)(yi+1-yi)/(xi+1-xi),分二种情形:(1)若y=yp,则点P在多边形边界上,算法结束;(2)若yyp,则m(-1)m;4.结束判断ii+1,若in,则返回到2,否则算法结束,此时若m=-1则点P在多边形外部,m=1则在内部。,凸多边形的包含算法沿逆时针行进，凸多边形内部均在其各边所在直线的左侧,因此只要对询问点P,逐个检查它是否在凸多边形每一边所在直线的左侧就可.,判断坐标为(xp,yp)的点P是在直线的位置设直线的端点为(x1,y1)和(x2,y2),直线方向是由(x1,y1)到(x2,y2)的方向。直线的方程记为Ax+By+C=0,则有:A=y2-y1,B=x1-x2,C=x2y1-x1y2计算D:D=Axp+Byp+C若D0,则点在直线右侧;若D=0,则点在直线上。,再进一步,引人“折半查找”思想,写出下面更有效率的算法。设算法的输入是一个凸多边形的顶点序列Po,P1,Pn-1,询问点P,可有包含性检验算法如下:,1.准备i1,jn-1;2.查找是否结束若j-i=1则到4,否则继续;3.折半查找k(i+j)/2,检查询问点相对直线PoPk的位置关系,分三种情况:3.1在直线上,若点在线段PoPk上或内部,则点在原凸多边形内部,若点在线段PoPk延长线上,则在原凸多边形外;输出回答后算法结束;3.2在左侧,ik返回步23.3在右侧,jk返回步24.最后检查检查询问点P对P0PiPj的包含性,若在内则也在原凸多边形内部,若在外则也在原凸多边形外部,输出回答后算法结束.,凸多边形重叠计算两个凸多边形的重叠问题,这也就是对两个凸多边形求相交部分的问题。现在约定凸多边形指它的边界和内部,凸多边形仍用顶点坐标的逆时针方向序列确定。设给出的两个凸多边形P和Q的顶点序列分别是P1,P2,PL和Q1,Q2,Qm。为说明简便,假设P的边界上不包含Q的项点,Q的边界也不包含P的顶点。,有两个问题需要解决,一个是如何有次序地求出各边的所有交点,一个是如何排列求出交点和原凸多边形的顶点,形成交得凸多边形的顶点序列。为了有次序地求出交点,可以在两个多边形边上交替地前进,原则是在哪个多边形的边上可能有交点就等待,在另一个多边形的边上前进。初始从对边P0P1与Q0Q1的求交开始,注意所有求交是线段的求交。这里规定了P0=PL,Q0=Qm。,区分前四种情形还是后四种情形求矢量积Pi-1PiQj-1Qj的z分量,若该分量大于等于0,是前四种情形,小于0是后四种情形。,AdvanceSPi-1PiQj-1Qj的z分量;分二种情况处理,然后算法就结束;1.若S0,则做若Pi在Qj-1Qj左并且Qj在Pi-1Pi左(b),或者Pi在Qj-1Qj右并且Qj在pi-1Pi左(d),则i前进1,否则j前进1;2.若S0,则做若Pi在Qj-1Qj右并且Qj在Pi-lPi左(e),或者Pi在Qj-1Qj右并且Qj在Pi-1Pi右(g),则i前进1,否则j前进1;算法中i前进1,指若il,则前进1是i+1;若i=L,则前进1是1。这因为多边形P是首尾相接的。类似地j前进1,j3，则做2.12.2,否则转到步3:2.1Q1点序列中Q0的下一个顶点;Q2点序列中Q1的下一个顶点;2.2若Test(Q0,Q1,Q2)为真,则做:输出Q0Q1Q2;,从点序列中删除顶点Ql;nn-1;返回步2开头;否则做Q0Q1,返回步2.1;3.最后输出输出点序列中剩下三点为最后一个三角形,然后算法结束。函数Test是对Q0Q1Q2进行检查，分两步实现,第一步检查Q0,Q1,Q2是否是一个在Ql的左转,若不然,是右转,则Q0Q2在多边形外部而可以回答假而结束。第二步可对原多边形中除去Q0,Q1,Q2这三点之外的其它点，对每一点都考查它对三角形的包含性,若有一点被包含则就可以回答假而结束,只有其它点都在三角形外部时才能回答真而结束。,最小权三角剖分或最小三角剖分如果一个三角剖分中选取的对角线的总长度最小。任意的凸多边形最小三角剖分,事实3在n边形(n3)的任意一种三角剖分中,每一对相邻顶点中至少有一个顶点是某条对角线的端点。因为若相邻顶点Vi,Vi+1都不是某条对角线的端点,则区域(Vi-1,Vi,Vi+1,Vi+2)中没有对角线,因而也就没有被三角剖分。事实4如果ViVj是三角剖分的一条对角线,则一定存在某顶点Vk,使得ViVk和VkVj是多边形的边或对角线。因为若不然,一定存在以ViVj为边界的某个区域没有被三角剖分。,顶点序列V0,V1-,Vn-1确定的凸n边形的最小三角剖分挑选两个相邻顶点比方选V0和V1,由事实3知道在最小三角剖分中,必有另一顶点Vk,或者使V1Vk是对角线,或者使V0VK是对角线。对有n个顶点的多边形，Vk的选取方法有n-3种。对于每个可能的Vk用对角线V0Vk(或V1Vk)把原多边形剖分成两个较小的多边形,这样原问题就被分成为两个子问题。往下需要寻找分成的两个较小凸多边形的最小三角剖分。（递归）,选择剖分方法,使得每次剖分后所得的子问题只涉及一条原多边形的对角线。由事实4知在最小剖分中的对角线一定与另外一点构成三角形。,现在一般地说明所要使用的剖分方法。引入记号Sis,表示一个子多边形Vi,Vi+1,Vi+s-1的最小三角剖分问题。子多边形由Vi开始的S个顶点按顺时针向排列围成。每个子问题Sis中都仅涉及原多边形一条对角线。为了解Sis,必须考虑如下三种情况:1.选择顶点Vi+S-2,这时构成一个三角形ViVi+S-2Vi+S-1,得到一个子问题Si,S-12.选择顶点Vi+1,这时构成一个三角形ViVi+1Vi+S-1,得到一个子问题Si+1,S-1。3.对2kS-3,选择Vi+k这时构成一个三角形ViVi+kVi+S-1,得到两个子问题Si,k+1和Si+k,S-k。,实际上可以把三种情况概括为一句话,即对1kS-2,把Sis分解成两个子问题Si,k+1和Si+k,S-k。容易验证k=1和k=S-2时,各自有一个子问题不成其为问题,但这不影响一般的讨论。,CiS记子问题SiS的解CiS的公式如下:CiS=minCi,k+1+Ci+k,S-k+D(ViVi+k)+D(Vi+kVi+S-1)1kS-2,如果VpVq是对角线,则D(VpVq)是它的长度;若VpVq是原多边形的边,则D(VpVq)=0;如果S4,则CiS=0。这因为CiS是最小三角剖分中引人对角线的总长度,原多边形的边不是对角线,当S4时也不必引入对角线。,对前面说明的凸七边形,要