第5章二维几何01–基本算法.pptVIP

2006年9月29日 计算机图形学 上海交通大学计算机系 何援军 第5章 二维几何 之一——基本几何算法 5.1 概述（1） 由屏幕显示或绘图机绘制的图形都是二维的，通过计算机处理的三维或更多维的图形也都以二维状态表现出来。 已经讨论过一些处理二维(平面)图形的方法，主要是基本几何元素：点、直线、圆弧的建立和交切计算等问题。 5.1 概述（2） 一般地，这些基本子程序包就构成了一个平面作图系统的基本内容。这样的系统从本质上说并不能称为二维图形处理系统，只涉及“线”的处理(“线”的描述和“线”的交切计算等)。 其基本立足点在于：通过对“线”的处理而达到描述(或者输出)图形的实际效果，很少从整体的观点去考虑图形的概念。 考虑二维图形的描述、生成和图形的运算问题。即需要考虑图形的外部和内部，而不是仅仅关心图形轮廓的描述。 5.1 概述（3） 在生成新的二维图形时，是以图形本身作为运算对象和结果的。 例如， 在造船中，人们需将一矩形钢板切割成一定的外形，开一些切口，而在内部则挖各种类型的孔以构成一些肋板、肘板等船体结构另件 在服装行业要将一块长方形的布料裁剪成各种衣片 在机械另件的计算机辅助设计中，有时要对一些标准零件作裁剪、分割或拼合处理以形成新的更复杂的零件和工件等 在套料时，可用图形的交集运算来判别两个零件有否碰撞 在三维物体的二维表示中，可以用图形的差集实现隐藏线的消除等等。 5.1 概述（4） 能够区别出图形内部和外部的描述图形的方法 判定一个点在图形的内部还是外部的方法 决定一条线在图形内部部份的算法 两个图形进行交、并、差等几何运算的算法 及图形显示中必不可少的图形裁剪算法等 这些都是二维图形处理中最根本和最基础的问题。 5.2向量和向量间交点 5.2 向量和向量间交点（1） 设平面上有由P1(x1,y1)到P2(x2,y2)的向量P1P2和由Q1(u1,v1)到Q2(u2,v2)的向量Q1Q2，则两向量的交点满足方程组： 令 当△≠0 时，两向量所在的直线有交点。 5.2 向量和向量间交点（2） 两向量交点的参数是： 当且仅当λ∈［0,1］与μ∈［0,1］时，才能说两向量有交点。 5.2 向量和向量间交点（3） P1P2向Q1Q2的旋向（交点相对于P1P2 特征值的符号）与Δ的符号相同 Q1Q2向 P1P2的旋向与Δ的符号相反 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) 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 not available **************************************************************/ 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 *