第5章二维几何01基本算法ppt课件

上传人:pu****.1 文档编号:592731861 上传时间:2024-09-22 格式:PPT 页数:43 大小:410.50KB
返回 下载 相关 举报
第5章二维几何01基本算法ppt课件_第1页
第1页 / 共43页
第5章二维几何01基本算法ppt课件_第2页
第2页 / 共43页
第5章二维几何01基本算法ppt课件_第3页
第3页 / 共43页
第5章二维几何01基本算法ppt课件_第4页
第4页 / 共43页
第5章二维几何01基本算法ppt课件_第5页
第5页 / 共43页
点击查看更多>>
资源描述

《第5章二维几何01基本算法ppt课件》由会员分享,可在线阅读,更多相关《第5章二维几何01基本算法ppt课件(43页珍藏版)》请在金锄头文库上搜索。

1、第第5 5章章 二维几何二维几何之一之一基本几何算法基本几何算法2006年9月29日1*2024/9/22上海交通大学计算机系 何援军25.1 概述概述1)r由由屏屏幕幕显显示示或或绘绘图图机机绘绘制制的的图图形形都都是是二二维维的的,通通过过计计算算机机处处理理的的三三维维或或更更多多维维的的图图形也都以二维状态表现出来。形也都以二维状态表现出来。r已已经经讨讨论论过过一一些些处处理理二二维维(平平面面)图图形形的的方方法法,主主要要是是基基本本几几何何元元素素:点点、直直线线、圆圆弧的建立和交切计算等问题。弧的建立和交切计算等问题。2024/9/22上海交通大学计算机系 何援军35.1 概

2、述概述2)r一一般般地地,这这些些基基本本子子程程序序包包就就构构成成了了一一个个平平面面作作图图系系统统的的基基本本内内容容。这这样样的的系系统统从从本本质质上上说说并并不不能能称称为为二二维维图图形形处处理理系系统统,只只涉涉及及“线线的的处处理理(“线线的的描描述述和和“线的交切计算等线的交切计算等)。r其其基基本本立立足足点点在在于于:通通过过对对“线线的的处处理理而而达达到到描描述述(或或者者输输出出)图图形形的的实实际际效效果果,很少从整体的观点去考虑图形的概念。很少从整体的观点去考虑图形的概念。r考考虑虑二二维维图图形形的的描描述述、生生成成和和图图形形的的运运算算问问题题。即即

3、需需要要考考虑虑图图形形的的外外部部和和内内部部,而而不是仅仅关心图形轮廓的描述。不是仅仅关心图形轮廓的描述。2024/9/22上海交通大学计算机系 何援军45.1 概述概述3)r在在生生成成新新的的二二维维图图形形时时,是是以以图图形形本本身身作作为为运运算算对对象和结果的。象和结果的。r例如,例如,r在在造造船船中中,人人们们需需将将一一矩矩形形钢钢板板切切割割成成一一定定的的外外形形,开开一一些些切切口口,而而在在内内部部则则挖挖各各种种类类型型的的孔孔以以构构成成一一些肋板、肘板等船体结构另件些肋板、肘板等船体结构另件r在服装行业要将一块长方形的布料裁剪成各种衣片在服装行业要将一块长方

4、形的布料裁剪成各种衣片r在在机机械械另另件件的的计计算算机机辅辅助助设设计计中中,有有时时要要对对一一些些标标准准零零件件作作裁裁剪剪、分分割割或或拼拼合合处处理理以以形形成成新新的的更更复复杂杂的零件和工件等的零件和工件等r在在套套料料时时,可可用用图图形形的的交交集集运运算算来来判判别别两两个个零零件件有有否碰撞否碰撞r在在三三维维物物体体的的二二维维表表示示中中,可可以以用用图图形形的的差差集集实实现现隐藏线的消除等等。隐藏线的消除等等。2024/9/22上海交通大学计算机系 何援军55.1 概述概述4)r能够区别出图形内部和外部的描述图形的能够区别出图形内部和外部的描述图形的方法方法r

5、判定一个点在图形的内部还是外部的方法判定一个点在图形的内部还是外部的方法r决定一条线在图形内部部份的算法决定一条线在图形内部部份的算法r两个图形进行交、并、差等几何运算的算两个图形进行交、并、差等几何运算的算法法r及图形显示中必不可少的图形裁剪算法等及图形显示中必不可少的图形裁剪算法等r这些都是二维图形处理中最根本和最基础这些都是二维图形处理中最根本和最基础的问题。的问题。2024/9/22上海交通大学计算机系 何援军65.2向量和向量间交点向量和向量间交点2024/9/22上海交通大学计算机系 何援军75.2 向量和向量间交点向量和向量间交点1)r设设平平面面上上有有由由P1(x1,y1)P

6、1(x1,y1)到到P2(x2,y2)P2(x2,y2)的的向向量量P1P2P1P2和和由由Q1(u1,v1)Q1(u1,v1)到到Q2(u2,v2)Q2(u2,v2)的的向向量量Q1Q2Q1Q2,则则两两向向量的交点满足方程组:量的交点满足方程组:r令令r当当0 0 时,两向量所在的直线有交点。时,两向量所在的直线有交点。2024/9/22上海交通大学计算机系 何援军85.2 向量和向量间交点向量和向量间交点2)r两向量交点的参数是:两向量交点的参数是:r当当且且仅仅当当0,1与与0,1时时,才才能说两向量有交点。能说两向量有交点。2024/9/22上海交通大学计算机系 何援军95.2 向量

7、和向量间交点向量和向量间交点3)rP1P2向向Q1Q2的旋向交点相对于的旋向交点相对于P1P2 特征值的符号与特征值的符号与的符号相同的符号相同 rQ1Q2向向 P1P2的旋向与的旋向与的符号相反的符号相反2024/9/22上海交通大学计算机系 何援军105.2 向量和向量间交点向量和向量间交点4)r/*rint plvlv(xp1,yp1,xp2,yp2,xq1,yq1,xq2,yq2,sp,sq,kp,kq)rThis function is used to find an intersection point X between two VECTORs.r INPUT:(xp1,yp1,

8、xp2,yp2) float line SEGMENT P1P2r(xq1,yq1,xq2,yq2) float line SEGMENT Q1Q2r OUTPUT:*spfloat parameterof on line SEGMENT P1P2*sqfloat parameterof on line SEGMENT Q1Q2r *kpint attribution of on line SEGMENT P1P2r*kqint attribution of on line SEGMENT Q1Q2r 返回值:1 交点在两向量上包括端点)2019.4.8 By He-1 直线有交点,但交点不在

9、向量上,即向量无有效交点r 0 两直线无交点r*sp,*sq,*kp,*kq are not availabler*/2024/9/22上海交通大学计算机系 何援军115.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=xq

10、1-xp1; /计算交点参数计算交点参数 vy=yq1-yp1; *sp=(qy*ux-qx*vy)/ Delta; *sq=(dy*ux-dx*vy)/ Delta; if (*sp) -Eps)&(*sq)-Eps) return 1; /正常出口正常出口 elsereturn -1; /无有效交点无有效交点 /End of if (| | Eps) return 0; /直线无交点直线无交点int plvlv(float xp1,float yp1,float xp2,float yp2,float xq1,float yq1,float xq2,float yq2,float *sp,

11、float *sq,int *kp,int *kq)2024/9/22上海交通大学计算机系 何援军125.3 求取平面上点列的凸包算求取平面上点列的凸包算法法rG1【找找内内点点】:找找到到点点列列的的一一个个内内点点G,从内点作水平向右的一向量,从内点作水平向右的一向量L;rG2【排排序序】:连连接接内内点点和和全全部部点点列列,根根据据这这些些连连线线与与L的的夹夹角角按按递递增增次次序序对对点点列列排序,形成一个双向链接表;排序,形成一个双向链接表;rG3【求求凸凸包包上上的的起起点点】:求求取取点点列列中中的的任一个极点任一个极点P0x或或y的最小的最小/最大者);最大者);Min/M

12、ax2024/9/22上海交通大学计算机系 何援军135.3 求取平面上点列的凸包算求取平面上点列的凸包算法法rG4【求求凸凸包包上上的的一一个个顶顶点点】:从从点点1出出发发依依次次考考察察连连续续的的三三个个顶顶点点,如如果果是是向向逆逆向向转转图图中中实实心心圆圆点点),则则表表的的指指针针加加1,否否则则删删去去三三个个顶顶点点中中的的中中间间点点图图中中空空心心圆点),且指针减圆点),且指针减1;顺向点顺向点逆向点逆向点rG5【求求取取凸凸包包】:按按G4遍遍历历点点表表,其其结结果果即即为为点点列列的的有有向向凸凸包包。这这样样求求得得的的凸凸包包是是一一个个循循环环点点列列,选选

13、取取任任一一个个起起点点均均可可作作为凸包的起点。为凸包的起点。2024/9/22上海交通大学计算机系 何援军145.4 包容性测试包容性测试r决定平面上的一个点是在图形的内决定平面上的一个点是在图形的内部还是在它的外部部还是在它的外部r符号判别法符号判别法r角度判别法角度判别法rGriffithsGriffiths判别法判别法r半射线交点计数判别法半射线交点计数判别法2024/9/22上海交通大学计算机系 何援军155.4.1符号判别法符号判别法1)r如如果果图图形形是是凸凸n多多边边形形(只只含含一一个个环环)。建建立立形形成成多多边边形形的的环环的的走走向向,保保证证边向量的左侧为多边形

14、的内部边向量的左侧为多边形的内部r求求取取通通过过各各边边向向量量的的直直线线的的方方程程系系数数r(Ai , Bi , Ci) (i=1,2,n)2024/9/22上海交通大学计算机系 何援军165.4.1 符号判别法符号判别法2)r设被测试点为设被测试点为T(XtT(Xt,Yt)Yt),计算,计算rDi=Aixt+Biyt+Ci (i=1,2,n)Di=Aixt+Biyt+Ci (i=1,2,n)r的值的值r一一旦旦有有一一个个Di0(Di0(或或Di=0)Di=0),则则被被测测试试点点在在多多边边形形的外部的外部( (或在边界上或在边界上) ),判断结束。,判断结束。r否否则则,所所有

15、有的的Di0 Di 0r而而T却在多边形的内部。却在多边形的内部。2024/9/22上海交通大学计算机系 何援军185.4.2 角度判别法角度判别法1)r令令 P=p1,p2,pn,p1是是 一一 个个 顶顶 点点 为为pi(xi,yi), i=1,2,n的的封封闭闭多多角角形形,pt是是一一个测试点。个测试点。rPtPi为为连连接接pt和和pi的的诸诸向向量量,i表表示示向向量量PtPi到到PtPi+1的夹角的夹角2024/9/22上海交通大学计算机系 何援军195.4.2 角度判别法角度判别法2)r若若i = 0 Pt在在P的外面;的外面;r若若i = 2 Pt在在P的里面。的里面。202

16、4/9/22上海交通大学计算机系 何援军205.4.2 角度判别法角度判别法3)r这这种种角角度度的的计计算算不不需需要要很很高高的的精精度度,其其误误差甚至可以达到差甚至可以达到也不失判别的正确性也不失判别的正确性r但但是是必必须须计计算算两两向向量量间间的的夹夹角角而而涉涉及及到到反反三角函数的计算,计算工作量较大三角函数的计算,计算工作量较大r计计算算量量虽虽也也是是O(n),但但要要比比符符号号判判别别法法的的工作增加几倍工作增加几倍r其适用性能从凸多边形扩展到一般多边形其适用性能从凸多边形扩展到一般多边形2024/9/22上海交通大学计算机系 何援军215.4.3 Griffiths

17、判别法判别法1)r为为了了在在角角度度判判别别法法中中避避免免求求取取反反三三角角函函数数,Griffiths在在1981年年(CAD JANUARY 1981 NUMBER 1 VO1 13) 提提出出了了一一种种近近似似的的方方法以加快运算速度。法以加快运算速度。r其基本原理是:其基本原理是:r矢矢量量积积PtPiPtPi+1与与sini成成正正比比,而而数数量量积积PtPiPtPi+1与与cosi成成正正比比,于于是是tgi或或ctgi可由这两个积的结果导出。可由这两个积的结果导出。2024/9/22上海交通大学计算机系 何援军225.4.3 Griffiths判别法判别法2)r角度角度

18、i可由下列近似的线性逼近公式求得:可由下列近似的线性逼近公式求得:rarctg x=/4x+Cr式中式中2024/9/22上海交通大学计算机系 何援军235.4.3 Griffiths判别法判别法3)r当当0X1时,使用线性逼近公式时,使用线性逼近公式rarctg x=/4x+Cr的最大误差是的最大误差是C,并且在,并且在rX=0,X= ,和,和X=1处出现处出现r从最坏的情况处看,即使每次都取得最大从最坏的情况处看,即使每次都取得最大误差,那么只要多角形不大于误差,那么只要多角形不大于88边形,所边形,所得的包容性测试还是准确的。得的包容性测试还是准确的。r这个近似公式直观而简单,且避免了三

19、角这个近似公式直观而简单,且避免了三角函数的计算,能够满足常规应用。函数的计算,能够满足常规应用。2024/9/22上海交通大学计算机系 何援军245.4.4半射线交点计数判别法半射线交点计数判别法r令令R是一条以是一条以P为起点任何方向的半射线为起点任何方向的半射线r当当R和和多多角角形形的的交交点点个个数数为为奇奇数数个个时时,点点P在多角形的内部在多角形的内部r当当交交点点个个数数为为偶偶数数或或为为零零时时,点点P在在多多角角形的外部形的外部2024/9/22上海交通大学计算机系 何援军255.4.4半射线交点计数判别法半射线交点计数判别法r用这种方法来判别的困难在于:用这种方法来判别

20、的困难在于:r当所选择的半射线通过多角形的顶点,或当所选择的半射线通过多角形的顶点,或者和多角形的边重合时,交点应如何记数者和多角形的边重合时,交点应如何记数的问题。的问题。2024/9/22上海交通大学计算机系 何援军26算法算法P:半射线交点计数包容性测试算法:半射线交点计数包容性测试算法rP1【建建立立射射线线】由由点点Pt(Xt,Yt)向向点点(X,Yt)建建立立一一射射线线向向量量。其其中中X是是一一个个多多角角形形顶顶点点不不可可能能达达到到的的X大大值值,Yt意意味味着着射射线线和和X轴平行;轴平行;rP2【求求交交点点】将将此此射射线线向向量量和和多多角角形形的的各各边边向向量

21、量求求交交。并并记记录录交交点点几几何何参参数数和和相相对对于于射射线和特征值,并将交点按其射线方向排队;线和特征值,并将交点按其射线方向排队;2024/9/22上海交通大学计算机系 何援军27算法算法P:半射线交点计数包容性测试算法:半射线交点计数包容性测试算法rP3【合合并并重重点点】判判别别相相邻邻交交点点的的几几何何参参数数,如如为为重重点点,则则求求其其特特征征值值的的代代数数和和,如如代代数数和和为为零零,则取消两个交点,否则取消其中一个交点;则取消两个交点,否则取消其中一个交点;rP4【合合并并相相邻邻同同特特征征交交点点】判判别别相相邻邻两两个个交交点点的的特特征征,如如果果相

22、相邻邻两两个个特特征征相相同同,则则取取消消其其中中一一个个交点;交点;rP5【判判别别】计计算算交交点点个个数数,如如为为奇奇数数,则则点点在在多多角形内部,否则在多角形外部。角形内部,否则在多角形外部。2024/9/22上海交通大学计算机系 何援军28重交点的特征值重交点的特征值 (1)r考察相对于考察相对于P1P2交点的特征值交点的特征值r标为标为“1的两个交点特征值和为的两个交点特征值和为 +2r标为标为“2的两个交点特征值和为的两个交点特征值和为 -2r标为标为“3和和“4的两组交点特征值和为的两组交点特征值和为 0r等等等等2024/9/22上海交通大学计算机系 何援军29重交点的

23、特征值重交点的特征值 (2)r分析分析r当当SUM=0时时,表表示示向向量量从从一一侧侧穿穿越越环环(未未进进入入环环),向量和环只有一个公共点向量和环只有一个公共点(如交点如交点3,4)r当当SUM0时,表示所给向量经过对方环的一个顶点时,表示所给向量经过对方环的一个顶点r穿入环穿入环(如交点如交点2)r穿出环穿出环(如交点如交点1) r实际上此时只起到一个交点的作用。实际上此时只起到一个交点的作用。2024/9/22上海交通大学计算机系 何援军30重交点的特征值重交点的特征值 (3)r重交点的特征值:如果交点是一个重点,那么重交点的特征值:如果交点是一个重点,那么r把把各各交交点点的的特特

24、征征值值的的代代数数和和的的符符号号作作为为重重交交点点的的特特征征值值的的符符号号,当当特特征征值值代代数数和和不不为为零零时时,特特征征值值的的绝绝对对值值仍仍取取为为1,取取消消其其中中1个个交交点点如如1为、为、2为)为)r代代数数和和为为零零时时,重重交交点点的的特特征征值值取取为为零零取取消消重交点)。重交点)。5.5直线段和直线边界图形公共部直线段和直线边界图形公共部份的求取份的求取(1)2006年9月29日31*2024/9/22上海交通大学计算机系 何援军325.5直线段和直线边界图形公共部份直线段和直线边界图形公共部份的求取的求取(1)r直直线线段段和和图图形形公公共共部部

25、份份的的求求取取在在计计算算机机图图形形处处理理中中经经常常碰碰到到,是是区区域域填填充充算算法法的的基基础;础;r例例如如剖剖面面线线绘绘制制的的主主要要工工作作就就是是解解决决这这个个问题;问题;r在在隐隐藏藏线线消消除除中中,则则是是对对画画面面上上的的线线段段作作相相反反的的判判断断,公公共共部部份份是是被被隐隐藏藏的的,而而非非公共部份则是需要绘制的。公共部份则是需要绘制的。2024/9/22上海交通大学计算机系 何援军335.5直线段和直线边界图形公共部份直线段和直线边界图形公共部份的求取的求取(2)r问问题题的的解解决决归归结结于于先先求求取取向向量量P1P2与与组组成成图图形的

26、各环的边向量的交点形的各环的边向量的交点r而而由由交交点点特特征征的的几几何何意意义义知知,向向量量上上一一入入点点到到相邻出点间的部份即在图形的内部。相邻出点间的部份即在图形的内部。r特特殊殊的的情情况况是是当当交交点点出出现现重重点点时时图图中中实实心心点点),即即交交点点和和环环的的顶顶点点相相重重合合的的时时候候,将将会会破破坏这种入点和出点的相邻性质。坏这种入点和出点的相邻性质。2024/9/22上海交通大学计算机系 何援军34算法算法C:直线与一个图形的公共部份的算法:直线与一个图形的公共部份的算法rC1【求求交交点点并并排排序序】求求取取线线段段(向向量量)与与图图形形(环环)的

27、的各各边边(向向量量)的的交交点点,并并对对0,1,0,1的的交交点沿点沿P1P2方向排序;方向排序;rC2【删删除除重重交交点点】对对交交点点参参数数相相同同的的那那些些重重交交点点累累加加其其特特征征值值SUM=IPC,若若SUM=0,则则取取消消此此交交点点,否否则则删删除除其其中中一一个个交交点点,变变重重交交点点为为一一个个交交点点,并以并以SUM的符号作为此交点的特征值;的符号作为此交点的特征值;2024/9/22上海交通大学计算机系 何援军35算法算法C:直线与一个图形的公共部份的算法:直线与一个图形的公共部份的算法rC3【连连续续入入、出出点点处处理理】取取消消连连续续排排列列

28、的的特特征征符符号号相相同同中中的的一一个个交交点点,若若连连续续两两个个“+”交交点点,则则取取消消后后面面一一个个“+”交交点点,若若连连续续两两个个“-”交交点点,则则取取消消前前面面一一个个“-”交点;交点;rC4【重重迭迭判判别别】若若无无交交点点,则则线线段段与与图图形形无无公公共共部部份,算法结束;份,算法结束;rC5【求求取取公公共共部部份份】依依次次选选取取线线段段上上所所有有从从负负交交点点到正交点的部份,即为线段与图形的公共部份。到正交点的部份,即为线段与图形的公共部份。2024/9/22上海交通大学计算机系 何援军365.6算法算法G:多边形裁剪算法:多边形裁剪算法rG

29、1【建建立立方方向向】对对多多边边形形的的顶顶点点按按“左左侧侧为为内内几几何方向排序;何方向排序;rG2【求求交交点点】对对此此直直线线向向量量和和多多边边形形的的各各边边向向量量求求交交。并并记记录录交交点点几几何何参参数数和和相相对对于于直直线线和和特特征征值,并将交点按直线方向排序;值,并将交点按直线方向排序;rG3【合合并并重重点点】判判别别相相邻邻交交点点的的几几何何参参数数,如如为为重重点点,则则求求其其特特征征值值的的代代数数和和,如如代代数数和和为为零零,则则取取消消 两两 个个 交交 点点 , 否否 则则 取取 消消 其其 中中 一一 个个 交交 点点 ;2024/9/22

30、上海交通大学计算机系 何援军375.6算法算法G:多边形裁剪算法:多边形裁剪算法rG4【合并相邻同特征交点】判别相邻两个【合并相邻同特征交点】判别相邻两个交点的特征,若相邻两个特征相同,如均交点的特征,若相邻两个特征相同,如均为为“”,则取消前面的交点,如均为,则取消前面的交点,如均为“”,则取消后面的交点;,则取消后面的交点;rG5【输出可见线段】依次输出直线上从负【输出可见线段】依次输出直线上从负特征交点到相邻的正特征交点间的线段。特征交点到相邻的正特征交点间的线段。2024/9/22上海交通大学计算机系 何援军385.7算法算法S:剖面线算法:剖面线算法rS1【建建立立方方程程】根根据据

31、图图形形描描述述(圆圆弧弧曲曲线线XYR),对对直直线线连连接接的的,是是根根据据二二点点式式建建立立过过二二点点的的有有向向法法线线式式系系数数,对对圆圆弧弧连连接接的的则则根根据据附附录录子子程程序序PPPR求取圆心位置。求取圆心位置。rS2【求求取取剖剖面面线线范范围围】对对各各图图形形顶顶点点根根据据问问题题三三求求取取斜斜率率为为K的的截截距距;对对圆圆弧弧段段部部份份,根根据据问问题题四四求取截距;并在所有截距中求取和。求取截距;并在所有截距中求取和。2024/9/22上海交通大学计算机系 何援军395.7算法算法S:剖面线算法:剖面线算法rS3【建立初始剖面线】过点【建立初始剖面

32、线】过点(0,+D),斜率为,斜率为K建建立直线立直线AX+BY+C=0,直线的方向可以任意,但,直线的方向可以任意,但一旦选定,则不再变更,一般情况下保持前进方向一旦选定,则不再变更,一般情况下保持前进方向的左侧为负。的左侧为负。rS4【求取一条剖面线】求此无穷直线和所有图形【求取一条剖面线】求此无穷直线和所有图形的交点,交点包括几何参数和特征,其中圆弧的特的交点,交点包括几何参数和特征,其中圆弧的特征按问题一处理;若与圆弧段的交点为切点,则切征按问题一处理;若与圆弧段的交点为切点,则切点不作交点,并对交点按直线方向排序。点不作交点,并对交点按直线方向排序。2024/9/22上海交通大学计算

33、机系 何援军405.7算法算法S:剖面线算法:剖面线算法rS5【重重点点处处理理】若若有有重重点点,则则将将重重点点特特征征值作代数和,若其代数和为值作代数和,若其代数和为0,则取消重点。,则取消重点。rS6【合合并并相相邻邻同同特特征征交交点点】判判别别相相邻邻两两个个交交点点的的特特征征,若若相相邻邻两两个个特特征征相相同同,如如均均为为“”,则则取取消消前前面面的的交交点点,如如均均为为“”,则则取消后面的交点。取消后面的交点。rS7【输输出出剖剖面面线线】依依次次输输出出从从负负特特征征交交点点到相邻的正特征交点间的线段。到相邻的正特征交点间的线段。rS8【判判别别】剖剖面面线线+D,

34、若若超超越越范范围围,则则结结束,否则转束,否则转S4。 2024/9/22上海交通大学计算机系 何援军41总结总结r平面图形的描述:指针的作用平面图形的描述:指针的作用r重点问题:几何计算的关键问题重点问题:几何计算的关键问题r交点特征:在处理重点问题中的作用交点特征:在处理重点问题中的作用2024/9/22上海交通大学计算机系 何援军42课外作业课外作业r1设计并实现一个平面上任意点列的凸包算法设计并实现一个平面上任意点列的凸包算法r2设计并实现一个判断平面上一点是否在一个设计并实现一个判断平面上一点是否在一个任意多角形内部的算法任意多角形内部的算法2024/9/22上海交通大学计算机系 何援军43思考题思考题r设计并实现一个对任意平面图形边界含圆弧设计并实现一个对任意平面图形边界含圆弧进展线形图案填充的算法。进展线形图案填充的算法。r (先实现(先实现45度斜线图案,再试着变化图案)。度斜线图案,再试着变化图案)。

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 医学/心理学 > 基础医学

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号