二维几何01-基本算法.ppt

2006年9月29日,上海交通大学计算机系何援军,1,第5章二维几何,之一基本几何算法,2,5.1概述（1）,由屏幕显示或绘图机绘制的图形都是二维的，通过计算机处理的三维或更多维的图形也都以二维状态表现出来。已经讨论过一些处理二维(平面)图形的方法，主要是基本几何元素：点、直线、圆弧的建立和交切计算等问题。,3,5.1概述（2）,一般地，这些基本子程序包就构成了一个平面作图系统的基本内容。这样的系统从本质上说并不能称为二维图形处理系统，只涉及“线”的处理(“线”的描述和“线”的交切计算等)。其基本立足点在于：通过对“线”的处理而达到描述(或者输出)图形的实际效果，很少从整体的观点去考虑图形的概念。考虑二维图形的描述、生成和图形的运算问题。即需要考虑图形的外部和内部，而不是仅仅关心图形轮廓的描述。,4,5.1概述（3）,在生成新的二维图形时，是以图形本身作为运算对象和结果的。例如，在造船中，人们需将一矩形钢板切割成一定的外形，开一些切口，而在内部则挖各种类型的孔以构成一些肋板、肘板等船体结构另件在服装行业要将一块长方形的布料裁剪成各种衣片在机械另件的计算机辅助设计中，有时要对一些标准零件作裁剪、分割或拼合处理以形成新的更复杂的零件和工件等在套料时，可用图形的交集运算来判别两个零件有否碰撞在三维物体的二维表示中，可以用图形的差集实现隐藏线的消除等等。,5,5.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时，才能说两向量有交点。,9,5.2向量和向量间交点（3）,P1P2向Q1Q2的旋向（交点相对于P1P2特征值的符号）与的符号相同Q1Q2向P1P2的旋向与的符号相反,10,5.2向量和向量间交点（4）,/*intplvlv(xp1,yp1,xp2,yp2,xq1,yq1,xq2,yq2,sp,sq,kp,kq)ThisfunctionisusedtofindanintersectionpointXbetweentwoVECTORs.INPUT:(xp1,yp1,xp2,yp2)floatlineSEGMENTP1P2(xq1,yq1,xq2,yq2)floatlineSEGMENTQ1Q2OUTPUT:*spfloatparameterofonlineSEGMENTP1P2*sqfloatparameterofonlineSEGMENTQ1Q2*kpintattributionofonlineSEGMENTP1P2*kqintattributionofonlineSEGMENTQ1Q2返回值:1交点在两向量上（包括端点）2002.4.8ByHe-1直线有交点，但交点不在向量上，即向量无有效交点0两直线无交点*sp,*sq,*kp,*kqarenotavailable*/,11,5.2向量和向量间交点（5）,floatdx,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)/0if(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)/Delta;if(*sp)-Eps)/直线无交点,intplvlv(floatxp1,floatyp1,floatxp2,floatyp2,floatxq1,floatyq1,floatxq2,floatyq2,float*sp,float*sq,int*kp,int*kq),12,5.3求取平面上点列的凸包算法,G1【找内点】：找到点列的一个内点G，从内点作水平向右的一向量L；G2【排序】：连接内点和全部点列，根据这些连线与L的夹角按递增次序对点列排序，形成一个双向链接表；G3【求凸包上的起点】：求取点列中的任一个极点P0（x或y的最小/最大者）；,Min/Max,13,5.3求取平面上点列的凸包算法,G4【求凸包上的一个顶点】：从点1出发依次考察连续的三个顶点，如果是向逆向转（图中实心圆点），则表的指针加1，否则删去三个顶点中的中间点（图中空心圆点），且指针减1；,顺向点,逆向点,G5【求取凸包】：按G4遍历点表，其结果即为点列的有向凸包。这样求得的凸包是一个循环点列，选取任一个起点均可作为凸包的起点。,14,5.4包容性测试,决定平面上的一个点是在图形的内部还是在它的外部符号判别法角度判别法Griffiths判别法半射线交点计数判别法,15,5.4.1符号判别法（1）,如果图形是凸n多边形(只含一个环)。建立形成多边形的环的走向，保证边向量的左侧为多边形的内部求取通过各边向量的直线的方程系数(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而T却在多边形的内部。,18,5.4.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=0Pt在P的外面；若i=2Pt在P的里面。,20,5.4.2角度判别法（3）,这种角度的计算不需要很高的精度，其误差甚至可以达到也不失判别的正确性但是必须计算两向量间的夹角而涉及到反三角函数的计算，计算工作量较大计算量虽也是O(n)，但要比符号判别法的工作增加几倍其适用性能从凸多边形扩展到一般多边形,21,5.4.3Griffiths判别法（1）,为了在角度判别法中避免求取反三角函数，Griffiths在1981年(CADJANUARY1981NUMBER1VO113)提出了一种近似的方法以加快运算速度。其基本原理是：矢量积PtPiPtPi+1与sini成正比，而数量积PtPiPtPi+1与cosi成正比,于是tgi或ctgi可由这两个积的结果导出。,22,5.4.3Griffiths判别法（2）,角度i可由下列近似的线性逼近公式求得：arctgx=/4x+C式中,23,5.4.3Griffiths判别法（3）,当0X1时，使用线性逼近公式arctgx=/4x+C的最大误差是C，并且在X=0，X=，和X=1处出现从最坏的情况处看，即使每次都取得最大误差，那么只要多角形不大于88边形，所得的包容性测试还是准确的。这个近似公式直观而简单，且避免了三角函数的计算，能够满足常规应用。,24,5.4.4半射线交点计数判别法,令R是一条以P为起点任何方向的半射线当R和多角形的交点个数为奇数个时，点P在多角形的内部当交点个数为偶数或为零时，点P在多角形的外部,25,5.4.4半射线交点计数判别法,用这种方法来判别的困难在于：当所选择的半射线通过多角形的顶点，或者和多角形的边重合时，交点应如何记数的问题。,26,算法P：半射线交点计数包容性测试算法,P1【建立射线】由点Pt(Xt，Yt)向点(X，Yt)建立一射线向量。其中X是一个多角形顶点不可能达到的X大值，Yt意味着射线和X轴平行；P2【求交点】将此射线向量和多角形的各边向量求交。并记录交点几何参数和相对于射线和特征值，并将交点按其射线方向排队；,27,算法P：半射线交点计数包容性测试算法,P3【合并重点】判别相邻交点的几何参数，如为重点，则求其特征值的代数和，如代数和为零，则取消两个交点，否则取消其中一个交点；P4【合并相邻同特征交点】判别相邻两个交点的特征，如果相邻两个特征相同，则取消其中一个交点；P5【判别】计算交点个数，如为奇数，则点在多角形内部，否则在多角形外部。,28,重交点的特征值(1),考察相对于P1P2交点的特征值标为“1”的两个交点特征值和为+2标为“2”的两个交点特征值和为-2标为“3”和“4”的两组交点特征值和为0等等,29,重交点的特征值(2),分析当SUM=0时，表示向量从一侧穿越环(未进入环)，向量和环只有一个公共点(如交点3,4)当SUM0时，表示所给向量经过对方环的一个顶点穿入环(如交点2)穿出环(如交点1)实际上此时只起到一个交点的作用。,30,重交点的特征值(3),重交点的特征值：如果交点是一个重点，则把各交点的特征值的代数和的符号作为重交点的特征值的符号，当特征值代数和不为零时，特征值的绝对值仍取为1，取消其中1个交点（如1为、2为）代数和为零时，重交点的特征值取为零（取消重交点）。,2006年9月29日,上海交通大学计算机系何援军,31,5.5直线段和直线边界图形公共部份的求取(1),32,5.5直线段和直线边界图形公共部份的求取(1),直线段和图形公共部份的求取在计算机图形处理中经常碰到，是区域填充算法的基础；例如剖面线绘制的主要工作就是解决这个问题；在隐藏线消除中，则是对画面上的线段作相反的判断，公共部份是被隐藏的，而非公共部份则是需要绘制的。,33,5.5直线段和直线边界图形公共部份的求取(2),问题的解决归结于先求取向量P1P2与组成图形的各环的边向量的交点而由交点特征的几何意义知，向量上一入点到相邻出点间的部份即在图形的内部。特殊的情况是当交点出现重点时（图中实心点），即交点和环的顶点相重合的时候，将会破坏这种入点和出点的相邻性质。,34,算法C：直线与一个图形的公共部份的算法,C1【求交点并排序】求取线段(向量)与图形(环)的各边(向量)的交点，并对0,1，0,1的交点沿P1P2方向排序；C2【删除重交点】对交点参数相同的那些重交点累加其特征值SUM=IPC，若SUM=0，则取消此交点，否则删除其中一个交点，变重交点为一个交点，并以SUM的符号作为此交点的特征值；,35,算法C：直线与一个图形的公共部份的算法,C3【连续入、出点处理】取消连续排列的特征符号相同中的一个交点，若连续两个“+”交点，则取消后面一个“+”交点，若连续两个“-”交点，则取消前面一个“-”交点；C4【重迭判别】若无交点，则线段与图形无公共部份，算法结束；C5【求取公共部份】依次选取线段上所有从负交点到正交点的部份，即为线段与图形的公共部份。,36,5.6算法G：多边形裁剪算法,G1【建立方向】对多边形的顶点按“左侧为内”几何方向排序；G2【求交点】对此直线（向量）和多边形的各边向量求交。并记录交点几何参数和相对于直线和特征值，并将交点按直线方向排序；G3【合并重点】判别相邻交点的几何参数，如为重点，则求其特征值的代数和，如代数和为零，则取消两个交点，否则取消其中一个交点；,37,5.6算法G：多边形裁剪算法,G4【合并相邻同特征交点】判别相邻两个交点的特征，若相邻两个特征相同，如均为“”，则取消前面的交点，如均为“”，则取消后面的交点；G5【输出可见线段】依次输出直线上从负特征交点到相邻的正特征交点间的线段。,38,5.7算法S：剖面线算法,S1【建立方程】根据图形描述(圆弧曲线XYR)，对直线连接的，是根据二点式建立过二点的有向法线式系数，对圆弧连接的则根据附录子程序PPPR求取圆心位置。S2【求取剖面线范围】对各图形顶点根据问题三求取斜率为K的截距；对圆弧段部份，根据问题四求取截距；并在所有截距中求取和。,39,5.7算法S：剖面线算法,S3【建立初始剖面线】过点(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度斜线图案，再试着变化图案）。,