《第5章二维几何01—基本算法.ppt》由会员分享,可在线阅读,更多相关《第5章二维几何01—基本算法.ppt(43页珍藏版)》请在三一文库上搜索。
1、2006年9月29日,上海交通大学计算机系 何援军,1,第5章 二维几何,之一基本几何算法,2,5.1 概述(1),由屏幕显示或绘图机绘制的图形都是二维的,通过计算机处理的三维或更多维的图形也都以二维状态表现出来。 已经讨论过一些处理二维(平面)图形的方法,主要是基本几何元素:点、直线、圆弧的建立和交切计算等问题。,3,5.1 概述(2),一般地,这些基本子程序包就构成了一个平面作图系统的基本内容。这样的系统从本质上说并不能称为二维图形处理系统,只涉及“线”的处理(“线”的描述和“线”的交切计算等)。 其基本立足点在于:通过对“线”的处理而达到描述(或者输出)图形的实际效果,很少从整体的观点去
2、考虑图形的概念。 考虑二维图形的描述、生成和图形的运算问题。即需要考虑图形的外部和内部,而不是仅仅关心图形轮廓的描述。,4,5.1 概述(3),在生成新的二维图形时,是以图形本身作为运算对象和结果的。 例如, 在造船中,人们需将一矩形钢板切割成一定的外形,开一些切口,而在内部则挖各种类型的孔以构成一些肋板、肘板等船体结构另件 在服装行业要将一块长方形的布料裁剪成各种衣片 在机械另件的计算机辅助设计中,有时要对一些标准零件作裁剪、分割或拼合处理以形成新的更复杂的零件和工件等 在套料时,可用图形的交集运算来判别两个零件有否碰撞 在三维物体的二维表示中,可以用图形的差集实现隐藏线的消除等等。,5,5
3、.1 概述(4),能够区别出图形内部和外部的描述图形的方法 判定一个点在图形的内部还是外部的方法 决定一条线在图形内部部份的算法 两个图形进行交、并、差等几何运算的算法 及图形显示中必不可少的图形裁剪算法等 这些都是二维图形处理中最根本和最基础的问题。,6,5.2向量和向量间交点,7,5.2 向量和向量间交点(1),设平面上有由P1(x1,y1)到P2(x2,y2)的向量P1P2和由Q1(u1,v1)到Q2(u2,v2)的向量Q1Q2,则两向量的交点满足方程组: 令 当0 时,两向量所在的直线有交点。,8,5.2 向量和向量间交点(2),两向量交点的参数是: 当且仅当0,1与0,1时,才能说两
4、向量有交点。,9,5.2 向量和向量间交点(3),P1P2向Q1Q2的旋向(交点相对于P1P2 特征值的符号)与的符号相同 Q1Q2向 P1P2的旋向与的符号相反,10,5.2 向量和向量间交点(4),/* int plvlv(xp1,yp1,xp2,yp2,xq1,yq1,xq2,yq2,sp,sq,kp,kq) This function is used to find an intersection point X between two VECTORs. INPUT: (xp1,yp1,xp2,yp2) float line SEGMENT P1P2 (xq1,yq1,xq2,yq2)
5、 float line SEGMENT Q1Q2 OUTPUT: *sp float parameter of on line SEGMENT P1P2 *sq float parameter of on line SEGMENT Q1Q2 *kp int attribution of on line SEGMENT P1P2 *kq int attribution of on line SEGMENT Q1Q2 返回值: 1 交点在两向量上(包括端点) 2002.4.8 By He -1 直线有交点,但交点不在向量上,即向量无有效交点 0 两直线无交点 *sp,*sq,*kp,*kq are
6、 not available */,11,5.2 向量和向量间交点(5), float dx,dy,qx,qy,ux,vy,Delta; dx=xp2-xp1; /计算 dy=yp2-yp1; qx=xq2-xq1; qy=yq2-yq1; Delta =dx*qy-dy*qx; if (fabs(Delta) Eps) /0 if (Delta) = 0.0) /特征值 *kp=1; else *kp= -1; *kq=- *kp ;,ux=xq1-xp1; /计算交点参数 vy=yq1-yp1; *sp=(qy*ux-qx*vy)/ Delta; *sq=(dy*ux-dx*vy)/ De
7、lta; if (*sp) -Eps) /直线无交点 ,int plvlv(float xp1,float yp1,float xp2,float yp2,float xq1,float yq1,float xq2,float yq2,float *sp,float *sq,int *kp,int *kq),12,5.3 求取平面上点列的凸包算法,G1【找内点】:找到点列的一个内点G,从内点作水平向右的一向量L; G2【排序】:连接内点和全部点列,根据这些连线与L的夹角按递增次序对点列排序,形成一个双向链接表; G3【求凸包上的起点】:求取点列中的任一个极点P0(x或y的最小/最大者);,Mi
8、n/Max,13,5.3 求取平面上点列的凸包算法,G4【求凸包上的一个顶点】:从点1出发依次考察连续的三个顶点,如果是向逆向转(图中实心圆点),则表的指针加1,否则删去三个顶点中的中间点(图中空心圆点),且指针减1;,顺向点,逆向点,G5【求取凸包】:按G4遍历点表,其结果即为点列的有向凸包。这样求得的凸包是一个循环点列,选取任一个起点均可作为凸包的起点。,14,5.4 包容性测试,决定平面上的一个点是在图形的内部还是在它的外部 符号判别法 角度判别法 Griffiths判别法 半射线交点计数判别法,15,5.4.1符号判别法(1),如果图形是凸n多边形(只含一个环)。建立形成多边形的环的走
9、向,保证边向量的左侧为多边形的内部 求取通过各边向量的直线的方程系数 (Ai , Bi , Ci) (i=1,2,n),16,5.4.1 符号判别法(2),设被测试点为T(Xt,Yt),计算 Di=Aixt+Biyt+Ci (i=1,2,n) 的值 一旦有一个Di0(或Di=0),则被测试点在多边形的外部(或在边界上),判断结束。 否则,所有的Di0 (i=1,2,n),表示被测试点在图形的内部。 此方法的计算工作量为O(n),17,5.4.1 符号判别法(3),在此判别法中,多边形为凸的条件不能少 例如,虽然有 A45xt +B45yt + C45 0 而T却在多边形的内部。,18,5.4.
10、2 角度判别法(1),令P=p1,p2,pn,p1是一个顶点为pi(xi,yi), i=1,2,n的封闭多角形,pt是一个测试点。 PtPi为连接pt和pi的诸向量,i表示向量PtPi到PtPi+1的夹角,19,5.4.2 角度判别法(2),若i = 0 Pt在P的外面; 若i = 2 Pt在P的里面。,20,5.4.2 角度判别法(3),这种角度的计算不需要很高的精度,其误差甚至可以达到也不失判别的正确性 但是必须计算两向量间的夹角而涉及到反三角函数的计算,计算工作量较大 计算量虽也是O(n),但要比符号判别法的工作增加几倍 其适用性能从凸多边形扩展到一般多边形,21,5.4.3 Griff
11、iths判别法(1),为了在角度判别法中避免求取反三角函数,Griffiths在1981年(CAD JANUARY 1981 NUMBER 1 VO1 13) 提出了一种近似的方法以加快运算速度。 其基本原理是: 矢量积PtPiPtPi+1与sini成正比,而数量积PtPiPtPi+1与cosi成正比,于是tgi或ctgi可由这两个积的结果导出。,22,5.4.3 Griffiths判别法(2),角度i可由下列近似的线性逼近公式求得: arctg x=/4x+C 式中,23,5.4.3 Griffiths判别法(3),当0X1时,使用线性逼近公式 arctg x=/4x+C 的最大误差是C,并
12、且在 X=0,X= ,和X=1处出现 从最坏的情况处看,即使每次都取得最大误差,那么只要多角形不大于88边形,所得的包容性测试还是准确的。 这个近似公式直观而简单,且避免了三角函数的计算,能够满足常规应用。,24,5.4.4半射线交点计数判别法,令R是一条以P为起点任何方向的半射线 当R和多角形的交点个数为奇数个时,点P在多角形的内部 当交点个数为偶数或为零时,点P在多角形的外部,25,5.4.4半射线交点计数判别法,用这种方法来判别的困难在于: 当所选择的半射线通过多角形的顶点,或者和多角形的边重合时,交点应如何记数的问题。,26,算法P:半射线交点计数包容性测试算法,P1【建立射线】由点P
13、t(Xt,Yt)向点(X,Yt)建立一射线向量。其中X是一个多角形顶点不可能达到的X大值,Yt意味着射线和X轴平行; P2【求交点】将此射线向量和多角形的各边向量求交。并记录交点几何参数和相对于射线和特征值,并将交点按其射线方向排队;,27,算法P:半射线交点计数包容性测试算法,P3【合并重点】判别相邻交点的几何参数,如为重点,则求其特征值的代数和,如代数和为零,则取消两个交点,否则取消其中一个交点; P4【合并相邻同特征交点】判别相邻两个交点的特征,如果相邻两个特征相同,则取消其中一个交点; P5【判别】计算交点个数,如为奇数,则点在多角形内部,否则在多角形外部。,28,重交点的特征值 (1
14、),考察相对于P1P2交点的特征值 标为“1”的两个交点特征值和为 +2 标为“2”的两个交点特征值和为 -2 标为“3”和“4”的两组交点特征值和为 0 等等,29,重交点的特征值 (2),分析 当SUM=0时,表示向量从一侧穿越环(未进入环),向量和环只有一个公共点(如交点3,4) 当SUM0时,表示所给向量经过对方环的一个顶点 穿入环(如交点2) 穿出环(如交点1) 实际上此时只起到一个交点的作用。,30,重交点的特征值 (3),重交点的特征值:如果交点是一个重点,则 把各交点的特征值的代数和的符号作为重交点的特征值的符号,当特征值代数和不为零时,特征值的绝对值仍取为1,取消其中1个交点
15、(如1为、2为) 代数和为零时,重交点的特征值取为零(取消重交点)。,2006年9月29日,上海交通大学计算机系 何援军,31,5.5直线段和直线边界图形公共部份的求取(1),32,5.5直线段和直线边界图形公共部份的求取(1),直线段和图形公共部份的求取在计算机图形处理中经常碰到,是区域填充算法的基础; 例如剖面线绘制的主要工作就是解决这个问题; 在隐藏线消除中,则是对画面上的线段作相反的判断,公共部份是被隐藏的,而非公共部份则是需要绘制的。,33,5.5直线段和直线边界图形公共部份的求取(2),问题的解决归结于先求取向量P1P2与组成图形的各环的边向量的交点 而由交点特征的几何意义知,向量
16、上一入点到相邻出点间的部份即在图形的内部。 特殊的情况是当交点出现重点时(图中实心点),即交点和环的顶点相重合的时候,将会破坏这种入点和出点的相邻性质。,34,算法C:直线与一个图形的公共部份的算法,C1【求交点并排序】求取线段(向量)与图形(环)的各边(向量)的交点,并对0,1,0,1的交点沿P1P2方向排序; C2【删除重交点】对交点参数相同的那些重交点累加其特征值SUM=IPC,若SUM=0,则取消此交点,否则删除其中一个交点,变重交点为一个交点,并以SUM的符号作为此交点的特征值;,35,算法C:直线与一个图形的公共部份的算法,C3【连续入、出点处理】取消连续排列的特征符号相同中的一个
17、交点,若连续两个“+”交点,则取消后面一个“+”交点,若连续两个“-”交点,则取消前面一个“-”交点; C4【重迭判别】若无交点,则线段与图形无公共部份,算法结束; C5【求取公共部份】依次选取线段上所有从负交点到正交点的部份,即为线段与图形的公共部份。,36,5.6算法G:多边形裁剪算法,G1【建立方向】对多边形的顶点按“左侧为内”几何方向排序; G2【求交点】对此直线(向量)和多边形的各边向量求交。并记录交点几何参数和相对于直线和特征值,并将交点按直线方向排序; G3【合并重点】判别相邻交点的几何参数,如为重点,则求其特征值的代数和,如代数和为零,则取消两个交点,否则取消其中一个交点;,3
18、7,5.6算法G:多边形裁剪算法,G4【合并相邻同特征交点】判别相邻两个交点的特征,若相邻两个特征相同,如均为“”,则取消前面的交点,如均为“”,则取消后面的交点; G5【输出可见线段】依次输出直线上从负特征交点到相邻的正特征交点间的线段。,38,5.7算法S:剖面线算法,S1【建立方程】根据图形描述(圆弧曲线XYR),对直线连接的,是根据二点式建立过二点的有向法线式系数,对圆弧连接的则根据附录子程序PPPR求取圆心位置。 S2【求取剖面线范围】对各图形顶点根据问题三求取斜率为K的截距;对圆弧段部份,根据问题四求取截距;并在所有截距中求取和。,39,5.7算法S:剖面线算法,S3【建立初始剖面
19、线】过点(0,+D),斜率为K建立直线AX+BY+C=0,直线的方向可以任意,但一旦选定,则不再变更,一般情况下保持前进方向的左侧为负。 S4【求取一条剖面线】求此无穷直线和所有图形的交点,交点包括几何参数和特征,其中圆弧的特征按问题一处理;若与圆弧段的交点为切点,则切点不作交点,并对交点按直线方向排序。,40,5.7算法S:剖面线算法,S5【重点处理】若有重点,则将重点特征值作代数和,若其代数和为0,则取消重点。 S6【合并相邻同特征交点】判别相邻两个交点的特征,若相邻两个特征相同,如均为“”,则取消前面的交点,如均为“”,则取消后面的交点。 S7【输出剖面线】依次输出从负特征交点到相邻的正特征交点间的线段。 S8【判别】剖面线+D,若超越范围,则结束,否则转S4。,41,总结,平面图形的描述:指针的作用 重点问题:几何计算的关键问题 交点特征:在处理重点问题中的作用,42,课外作业,1)设计并实现一个平面上任意点列的凸包算法 2)设计并实现一个判断平面上一点是否在一个任意多角形内部的算法,43,思考题,设计并实现一个对任意平面图形(边界含圆弧)进行(线形)图案填充的算法。 (先实现45度斜线图案,再试着变化图案)。,
链接地址:https://www.31doc.com/p-2909796.html