资源描述：
《维几何01-基本算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章二维几何之一——基本几何算法2006年9月29日1上海交通大学计算机系何援军5.1概述（1）由屏幕显示或绘图机绘制的图形都是二维的，通过计算机处理的三维或更多维的图形也都以二维状态表现出来。已经讨论过一些处理二维(平面)图形的方法，主要是基本几何元素：点、直线、圆弧的建立和交切计算等问题。25.1概述（2）一般地，这些基本子程序包就构成了一个平面作图系统的基本内容。这样的系统从本质上说并不能称为二维图形处理系统，只涉及“线”的处理(“线”的描述和“线”的交切计算等)。其基本立足点在于：通过对“线”的处理而达到描述(或者输出)图形
2、的实际效果，很少从整体的观点去考虑图形的概念。考虑二维图形的描述、生成和图形的运算问题。即需要考虑图形的外部和内部，而不是仅仅关心图形轮廓的描述。35.1概述（3）在生成新的二维图形时，是以图形本身作为运算对象和结果的。例如，在造船中，人们需将一矩形钢板切割成一定的外形，开一些切口，而在内部则挖各种类型的孔以构成一些肋板、肘板等船体结构另件在服装行业要将一块长方形的布料裁剪成各种衣片在机械另件的计算机辅助设计中，有时要对一些标准零件作裁剪、分割或拼合处理以形成新的更复杂的零件和工件等在套料时，可用图形的交集运算来判别两个零件有否碰撞在
3、三维物体的二维表示中，可以用图形的差集实现隐藏线的消除等等。45.1概述（4）能够区别出图形内部和外部的描述图形的方法判定一个点在图形的内部还是外部的方法决定一条线在图形内部部份的算法两个图形进行交、并、差等几何运算的算法及图形显示中必不可少的图形裁剪算法等这些都是二维图形处理中最根本和最基础的问题。55.2向量和向量间交点65.2向量和向量间交点（1）设平面上有由P1(x1,y1)到P2(x2,y2)的向量P1P2和由Q1(u1,v1)到Q2(u2,v2)的向量Q1Q2，则两向量的交点满足方程组：令当△≠0时，两向量所在的直线有交点
4、。75.2向量和向量间交点（2）两向量交点的参数是：当且仅当λ∈［0,1］与μ∈［0,1］时，才能说两向量有交点。85.2向量和向量间交点（3）P1P2向Q1Q2的旋向（交点相对于P1P2特征值的符号）与Δ的符号相同Q1Q2向P1P2的旋向与Δ的符号相反95.2向量和向量间交点（4）/**************************************************************intplvlv(xp1,yp1,xp2,yp2,xq1,yq1,xq2,yq2,sp,sq,kp,kq)Thisfunction
5、isusedtofindanintersectionpointXbetweentwoVECTORs.INPUT:(xp1,yp1,xp2,yp2)floatlineSEGMENTP1P2(xq1,yq1,xq2,yq2)floatlineSEGMENTQ1Q2OUTPUT:*spfloatparameterofλonlineSEGMENTP1P2*sqfloatparameterofμonlineSEGMENTQ1Q2*kpintattributionofλonlineSEGMENTP1P2*kqintattributionofμon
6、lineSEGMENTQ1Q2返回值:1交点在两向量上（包括端点）2002.4.8ByHe-1直线有交点，但交点不在向量上，即向量无有效交点0两直线无交点*sp,*sq,*kp,*kqarenotavailable**************************************************************/105.2向量和向量间交点（5）{floatdx,dy,qx,qy,ux,vy,Delta;dx=xp2-xp1;//计算△dy=yp2-yp1;qx=xq2-xq1;qy=yq2-yq1;Delta
7、=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)<(1.+Eps)&&(*sp)>-Eps)&&((*sq)<(1.+Eps)&&(*sq)>-Eps))return1;//正常出口elsereturn-1;//无有效交点}//Endofif(
8、
9、△
10、>Eps)return0;//直线无交点}intplvlv(floatxp1,floatyp1,floatxp2,floatyp2,floatxq1,floatyq1,floatxq2,floatyq2,float
