计算机图形学教程课后习题答案

1、-. z.第一章试述计算机图形学研究的根本容？答：见课本P5-6页的节。计算机图形学、图形处理与模式识别本质区别是什么？请各举一例说明。答：计算机图形学是研究根据给定的描述，用计算机生成相应的图形、图像，且所生成的图形、图像可以显示屏幕上、硬拷贝输出或作为数据集存在计算机中的学科。计算机图形学研究的是从数据描述到图形生成的过程。例如计算机动画制作。图形处理是利用计算机对原来存在物体的映像进展分析处理，然后再现图像。例如工业中的射线探伤。模式识别是指计算机对图形信息进展识别和分析描述，是从图形图像到描述的表达过程。例如分捡设备扫描信件上手写的邮政编码，并将编码用图像复原成数字。计算机图形学与CA

2、D、CAM技术关系如何？答：见课本P4-5页的节。举3个例子说明计算机图形学的应用。答：事务管理中的交互绘图应用图形学最多的领域之一是绘制事务管理中的各种图形。通过从简明的形式呈现出数据的模型和趋势以增加对复杂现象的理解，并促使决策的制定。地理信息系统地理信息系统是建立在地理图形根底上的信息管理系统。利用计算机图形生成技术可以绘制地理的、地质的以及其它自然现象的高精度勘探、测量图形。计算机动画用图形学的方法产生动画片，其形象逼真、生动，轻而易举地解决了人工绘图时难以解决的问题，大大提高了工作效率。计算机绘图有哪些特点？答：见课本P8页的节。计算机生成图形的方法有哪些？答：计算机生成图形的方法有

3、两种：矢量法和描点法。矢量法：在显示屏上先给定一系列坐标点，然后控制电子束在屏幕上按一定的顺序扫描，逐个点亮临近两点间的短矢量，从而得到一条近似的曲线。尽管显示器产生的只是一些短直线的线段，但当直线段很短时，连成的曲线看起来还是光滑的。描点法：把显示屏幕分成有限个可发亮的离散点，每个离散点叫做一个像素，屏幕上由像素点组成的阵列称为光栅，曲线的绘制过程就是将该曲线在光栅上经过的那些像素点串接起来，使它们发亮，所显示的每一曲线都是由一定大小的像素点组成的。当像素点具有多种颜色或多种灰度等级时，就可以显示彩色图形或具有不同灰度的图形。7、当前计算机图形学研究的课题有哪些？答：见课本P10-11页的1

4、.4节。8、简述三维图形生成和输出的流水线？答：见课本P13页.节。9、向量图形和点阵图形之间的区别有哪些？ 答：通过矢量法产生的图形称为矢量图形或者向量图形，用描点法产生的图形称为点阵图形。向量图形区别点阵图形的特点在于描述图形几何形状的数学模型及依据此模型生成几何图形的计算机命令。向量图形由各个根本图形构成，这就要求各个根本图形有各自独立的信息。如果用点阵图形来表示一个向量图形，构成向量图形的*个根本图形(如直线段、圆弧等)的所有点应有一个信息。因此，在描述一个根本图形时，同时要描述其相应的信息。向量图形最根本的优点是它本身是由准确的数据给出，所以可以充分利用各种输出图形设备的分辨率尽可能

5、准确地输出图形。也正因为如此，向量图形的尺寸可以任意变化而不损失图形显示的质量。但是向量图形仅适合于描绘简单图形，而点阵图形可以描绘绚烂多彩的复杂图形。10、什么是虚拟现实技术和可视化技术？答：虚拟现实技术：利用计算机生成一种模拟环境，通过多种传感器和设备使用户投入到该环境中，实现用户和该环境直接进展交互的技术。例如模拟飞机驾驶舱。可视化技术：通过对空间数据场构造中间几何因素，或用图形绘制技术在屏幕上产生二维图像。例如分子模型构造。第二章1、计算机图形系统有什么特点？有哪些主要功能？答：课本的图2.1展示了计算机图形系统的组成。计算机图形系统是为了支持应用程序，便于实现图形的输入输出的硬件和软

6、件组合体。没有图形系统支持，就难以实现应用软件的开发。主要功能见课本2.1.2节。2、计算机图形系统有哪几种？各有什么特点？答：一种分类方法：交互式图形系统允许操作者以*种方式(对话方式或命令方式)来控制和操作图形生成过程，使得图形可以边生成、边显示、边修改，直至符合要求为止。而被动式绘图系统，图形在生成过程中，操作者无法对图形进展实时操作和控制，不具备交互功能，只提供各种图形命令或图形程序库，通过编程获得所需图形。另一种分类方法：见课本节，分为脱机绘图系统、联机绘图系统和交互式绘图系统。3、阴极射线管由哪些局部组成？它们的功能分别是什么？答：CRT由四局部组成：电子枪、聚焦系统、偏转系统和荧

7、光屏，这四局部都在真空管。电子枪由灯丝、阴极和控制栅极组成。灯丝加热阴极，阴极外表向外发射自由电子，控制栅控制自由电子是否向荧光屏发出，假设允许电子通过，形成的电子流在到达屏幕的途中，被聚焦系统电子透镜聚焦成很窄的电子束，由偏转系统产生电子束的偏转电场或磁场，使电子束左右、上下偏转，从而控制荧光屏上光点上下、左右运动，使得在指定时刻在屏幕指定位置上产生亮点。4、光栅扫描显示器由哪些局部组成？它们的功能分别是什么？ 答：见课本P21页图2.9所展示的组成框图，其后有各局部的介绍及功能。5、对于分辨率为1024*1024的光栅系统，假设每一像素用8位和12位二进制来表示存储信息，各需多大光栅存储容

8、量以及显存？每一屏幕最多能显示多少颜色？假设R，G，B灰度都占8位，其显示颜色的总数是多少？解：1)每一像素用8位二进制来表示存储信息，所需容量为1024*1024*1=Byte=1MB彩色素：=256(项)2)假设每一像素用12位二进制表示存储信息，所需容量为：1024*1024*1.5=1.5*(Byte)=1.5MB (由于显示卡的显存是按2的指数次倍增长的，因此所需显存为2M)彩色素：=4096( 项)3)颜色总数：*=16777216种6、对于19英寸显示器，假设*和Y两方向的分辨率相等，即1024*1024，则每个像素点的直径是多少？解：=0.33mm或=0.013英寸7、对于分辨

9、率为1024768的光栅系统，假设调色板设置为真彩色32位，此时需要显示一个三维图形，各需要多大光栅存储容量以及显存？答：调色板为真彩色32位，即意味着像素值的位长为32所需容量为1024*768*32/8*3=9MB 因此所需要的显存为16M8、GKS有哪三种坐标系？它们有什么不同？试写出它们之间对应关系？答：GKS有3种不同的坐标系。第一种是供给用程序使用的实际世界坐标系统World Coordinate System，简称 WC；第二种是GKS部使用的规设备坐标系Normalized Device Coordinate，简称NDC，它的取值围为0,1，这是一种既与设备无关也与应用无关的坐

10、标系；第三种是各工作站物理设备使用的设备坐标系Device Coordinate System，简称DC。GKS只支持二维对象的图形处理，因此上述3个坐标系都是二维坐标系。详见课本图3.28的描述。9、GKS中输入设备有哪6种逻辑功能？请各举出对应的物理设备。答：见课本.节。10、当前主流的图形软件有哪些？答：见课本节。第三章1、编写画一正方形程序，并在其中用不同的颜色画15个正方形，每一个都比前一个小。#includegraphics.h#includeconio.hvoid main()int i,color=0,ls=0;int j=700;int gdriver=VGA;int gmo

11、de=VGAHI;initgraph(&gdriver,&gmode,);3-1批改说明； 必须至少包含graphics.hinitgraph(&gdriver,&gmode,);必须包含15个正方形，一般用for循环，也可能用到while等。注意查看是否是正方形i, i, j, j即：*2-*1=y2-y1注意查看颜色是否有15种：也就是说gdriver=CGA肯定是错的，可以为DETECT、VGA、EGA。setbkcolor(15);for(i=0;i225;i=i+15,j=j-30)setcolor(color);bar(i,i,j,j);color+;ls+;getch();clo

12、segraph();2、用不同的线形绘制题1中的图形#includegraphics.h#includeconio.hvoid main()int i,color=1,ls=0;3-2批改说明； 注意查看3_1局部内容setlinestyle(i%4),0,k);k对线宽的设置。int j=700;int gdriver=VGA;gmode=VGAHI;initgraph(&gdriver,&gmode,);setbkcolor(15);for(i=0;i=225;i=i+15, j=j-30)setcolor(color);/setlinestyle(ls%4,0,1);或者setlines

13、tyle(4,ls,3);rectangle(i,i,j,j);setfillstyle(SOLID_FILL,color);/floodfill(getma*()/2,getma*y()/2,color); 此句会出现最后只用一种颜色填充的情况color+;ls+;getch();closegraph();3、画一五颜六色的图(此例为画一个五颜六色的圆)#includegraphics.h#includeconio.hvoid main()int driver=DETECT,mode=0;int i,start,end;3-3批改说明； 必须至少包含graphics.hinitgraph(&

14、gdriver,&gmode,);如果是这个版本的图，注意end比start要大。restorecrtmode()可能有人写成retorecrtmode()initgraph(&driver,&mode,);start=0;end=20;for(i=0;i0;i-,j-)setfillstyle(EMPTY_FILL,0);pieslice(387+j,290,start,end,37);pieslice(525+j,290,start,end,37);start+=40;end+=40;delay(5); /处于运动状态的自行车车轮的轴线的绘制 putimage(i-1,200,w,COPY

15、_PUT);line(2,327,562,327);delay(10); /自行车行驶动画的实现 for(i=0;iabs(y2-y1)length=abs(*2-*1);elselength=abs(y2-y1);incre*=(*2-*1)/length;increy=(y2-y1)/length;*=*1;y=y1;for(i=1;i1) if(f=0)*1=*1-d*;y1=y1;putpi*el(*1,y1,1);f=f-2*d*(*1-*0)+d*d*; else *1=*1;y1=y1+dy;putpi*el(*1,y1,1);f=f+2*dy*(y1-y0)+dy*dy; 方法

16、2：逆4象限#include graphics.h#include stdlib.h#include conio.hvoid ZDBJ_ARC(float *0,float y0,float *1,float y1,float *2,float y2);void main()int gdriver=CGA,mode=CGAC0;initgraph(&gdriver,&mode, ); ZDBJ_ARC(0,0,0,25,25,0); getch(); closegraph();void ZDBJ_ARC(float *0,float y0,float *1,float y1,float *2,

17、float y2) float f=0.0,F; float d*=1,dy=1; while(abs(y1-y2)1) if(f0)*1=*1;y1=y1-dy;putpi*el(*1,y1,1);f=f-2*dy*abs(y1-y0)+dy*dy; else *1=*1+d*;y1=y1;putpi*el(*1,y1,1);f=f+2*d*abs(*1-*0)+d*d*; 方法3：顺1象限#includegraphics.h/省略了图形初始化的步骤AB#includeconio.h#include math.hvoid main()int *1=5,y1=0,*2=0,y2=5;int *

18、0=0,y0=0;int R=sqrt(*2-*0)* (*2-*0)+(y2-y0)* (y2-y0);int d*=abs(*2-*1);int dy=abs(y2-y1);int n=d*+dy;putpi*el(*2,y2,1);int f;int *=*2,y=y2;for(int i=0;i=0)putpi*el(*,y-,1);elseputpi*el(*+,y,1);getch();closegraph(); /另一种做法是采用课本P97页表4.2的公式4.编一程序用角度DDA法画一圆/以圆点为圆心，半径为20的圆#includegraphics.h/省略了图形初始化的步骤#i

19、ncludeconio.h#include math.hvoid main()int *0=0,y0=0,R=20;int *1,y1,*i,yi;int N=R*8;float a=2*3.14/N;*1=20,y1=0;for(int i=1;i0；而对于圆的点，F(*, y)0。Y*PPdPuM1/8圆弧PuPdM此处仅考虑如下图的第一象限*的1/8圆弧，此时中点Bresenham画圆算法要从(0, R)到()顺时针地确定最正确逼近于该圆弧的像素序列。由于最大位移方向为*，因此其根本原理：每次*方向上走一步，而y方向上或减1或减0。假定当前与圆弧最近者已确定，为P(*i, yi)，则下一

20、候选像素只能是正右方的Pu(*i +1, yi)和右下方的Pd(*i +1, yi-1)。到底选取哪一个候选点依旧用中点进展判别。假设M是Pu和Pd的中点，即有M(*i +1, yi-0.5)，则当F(*M, yM)0，M在圆外，说明Pd离圆弧更近；当F(*M, yM)=0，则约定取Pd。构造判别式di=F(*M, yM)= F(*i +1, yi-0.5)=(*i +1)2+(yi-0.5)2- R2(1) 当di0，取Pu(*i +1, yi)，计算下一步的的判别式di+1=F(*u, yu)= F(*i +2, yi-0.5)= (*i +2)2+(yi-0.5)2- R2= di+2*

21、i+3 所以沿正右方向，di的增量为2*i+3。(2) 当di0，取Pd(*i +1, yi+1)，计算下一步的的判别式di+1=F(*d, yd)= F(*i +2, yi-1.5)= (*i +2)2+(yi-1.5)2- R2= di+2(*i-yi)+5所以沿右下方向，di的增量为2(*i-yi)+5。显然，所绘制圆弧段的第一个像素为P0(0, R)，因此判别式d0的初始值为1.25-R，可以令d=d-0.25来摆脱小数运算，则判别式di0对应于di-0.25，由于d始终是整数，di-0.25等价于dibP=p;m_ma*Inde*=len-1;void Bezier:draw() /

22、通过公有函数调用私有函数drawFrame();drawCurve();void Bezier:drawFrame() /其功能是绘制出多边形和各个端点setcolor(12);for(int i=0;im_ma*Inde*;i+)line( bPi.*, bPi.y, bPi+1.*, bPi+1.y ); /绘制多边形circle(bPi.*, bPi.y,5); /绘制各个端点circle(bPm_ma*Inde*.*,bPm_ma*Inde*.y,5);void Bezier:drawCurve() /实现多段Bezier曲线绘制的功能for(int i=0;i=m_ma*Inde*-

23、3;i+=3)drawCurve(i,i+1,i+2,i+3);void Bezier:drawCurve(int p0,int p1,int p2,int p3) /实现绘制*一段Bezier曲线的功能double tmp*=0.0;double tmpy=0.0;double t=0.0;for(;tbP=p;m_ma*Inde*=len;void B_Spline:draw() /通过公有函数调用私有函数drawFrame();drawCurve();void B_Spline:drawFrame() /其功能是绘制出多边形和各个端点setcolor(12);for(int i=0;im

24、_ma*Inde*-1;i+)line( bPi.*, bPi.y, bPi+1.*, bPi+1.y ); /绘制多边形circle(bPi.*, bPi.y,5); /绘制多边形各个端点circle(bPm_ma*Inde*-1.*,bPm_ma*Inde*-1.y,5);void B_Spline:drawCurve() /实现多段B样条曲线绘制的功能for(int i=0;im_ma*Inde*-2;i+)drawCurve(i,i+1,i+2);void B_Spline:drawCurve(int p0,int p1,int p2) /实现绘制*一段Bezier曲线的功能doubl

25、e tmp*=0.0;double tmpy=0.0;double t=0.0;for(;t=1.0;t+=0.001)tmp*=(0.5*bPp0.*-bPp1.*+0.5*bPp2.*)*t*t+(-bPp0.*+bPp1.*)*t+0.5*bPp0.*+0.5*bPp1.*;tmpy=(0.5*bPp0.y-bPp1.y+0.5*bPp2.y)*t*t+(-bPp0.y+bPp1.y)*t+0.5*bPp0.y+0.5*bPp1.y;putpi*el(tmp*,tmpy,3);void main() /主函数的实现int graphdriver=DETECT,graphmode;init

26、graph(&graphdriver,&graphmode,); /图形初始化setbkcolor(15);DPOINT* p;p=new DPOINT4; p0.*=50.0;p0.y=130.0;p1.*=120.0;p1.y=40.0;p2.*=190.0;p2.y=130.0;p3.*=260.0;p3.y=40.0;B_Spline b_sp(p,4);b_sp.draw();delete p;getch();closegraph();11. 简述NURBS曲线产生的背景和特点？答：NURBS曲线具有局部可调性、凸包性、几何和透视投影变换不变性等等，它采用有理参数多项式可以准确表示圆

27、锥曲线、二次曲面等，对于几何造型算法提供了思路。12. 将以下数据* 2 6 10 12 14 16Y 3 8 11 13 15 17按最小二乘法曲线拟合，分别求一次和二次多项式曲线，拟合以上数据并画图表示。解：如下表所示：i1236412816268483628821612963101111010011001000100004121315614418721728207365141521019629402744384166161727225643524096655366067802736105649792136000一次多项式的情形： 6+60=67 =1.4608 60+736=802 =0

28、.9706所求多项式为y=f(*)=1.4608+0.9706*二次多项式的情形： 6+60+736=67 =1.0793 60+736+9792=802 =1.0921 736+9792+136000=10564 =-0.006796213. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表：AEDCB1046/5EA1015-1BA 6-10 5 458-4/3DE584/3DC 3 2 1 0 用于存放AET活动边表该

29、多边形的AET指针的容为：1 AET为空58-4/3DE584/3DCAET2DCDEAET5-4/328/3-4/320/353DE-4/316/35-4/332/35DCAET46/5410-4/345DCEAAET5DE4/3125-11510BA1410BAEA6/526/510AET-16BAEA6/532/510AET-113107EA6/538/510AET-11210BA810AET-11110BAEA44/56/591010BAEA6/51010AET-110具体编程实现如下：第1步：(1) 根据输入的五个顶点坐标找到y值最小的点(例如点D，此时y=2)，并找到与D有边关系的

30、两个顶点(此时为E和C)，在y=2处建立ET边表记录(yma*、*i和m值均可通过顶点坐标间的计算得到，例如DE边的建立，特别注意：当D点和E点y坐标值一样时，也即是DE与*轴平行，该边不能计入ET边表)，之后标记D点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET表建立完善。注边关系的建立可通过邻接矩阵的数据构造实现，权值可以为该矩阵行编号对应点的y坐标值，ET边表采用邻接表的数据构造第2步：根据ET表构建AET表，并逐行完成多边形填充，具体的C+代码如下：(1) 建立头文件base_class.h，主要是边表结点构造体和ET边表类的实现enum ResultCod

31、eSuccess, Failure;template struct EnodeEnode() ne*t=NULL;Enode(T pyma*, float p*i, float pm, Enode *pne*t)yma*=pyma*; *i=p*i;m=pm; ne*t=pne*t;T yma*, *i; /yma*表示最大的y值，*i表示最底端点的*坐标值float m; /m表示斜率的倒数Enode *ne*t; /定义了ET表和AET表中结点的构造体template class ETpublic:ET(int mSize); ET();ResultCode Insert(int u, T

32、 yma*, float *i, float m);int n; /覆盖该多边形的扫描线的总数，从0开场计数Enode *a; /定义了边表类template ET:ET(int mSize)n=mSize;a=new Enode *n; for(int i=0;in;i+) ai=0; /ET边表的初始化template ET:ET()Enode *p, *q;delete a0; for(int i=1;ine*t;delete q;q=p;delete a; /析构函数负责回收存空间template ResultCode ET:Insert(int u, T yma*, float *i

33、, float m)if(un-1) return Failure;Enode *p=new Enode(yma*, *i, m, au);au=p;return Success; /依次插入结点构建出边表，其中a1到a10用于构建ET边表 /a0用于构建活动AET边表(2) 填充函数po_fill的实现和主函数的实现#include base_class.h#include graphics.h#include void po_fill(ET &etp, int ep, int color) /多边形填充函数的实现 int i=1; /i作为控制变量标识扫描线while(iep-1) if(

34、etp.ai!=NULL)Enode *p,*r;p=etp.ai;r=etp.a0;while(p) Enode *q=new Enode(p-yma*,p-*i,p-m,NULL); if(!etp.a0) etp.a0=q; r=q; else if(r-*i=q-*i) q-ne*t=r-ne*t; r-ne*t=q; r=q; if(r-*iq-*i) etp.a0=q; q-ne*t=r; else while(q-*ir-*i & r-ne*t) r=r-ne*t;if(r-ne*t) q-ne*t=r-ne*t; r-ne*t=q; else r-ne*t=q; q-ne*t=

35、NULL; p=p-ne*t; /按照*i值的大小将当前ET表中的记录放置到AET表中 Enode *f,*g;if(etp.a0)f=etp.a0;while(f-ne*t)g=f;f=f-ne*t;for(int j=g-*i;jne*t-*i;j+)putpi*el(j,i,color); /把一对相邻结点的*i区间围进展填充if(etp.a0!=NULL)Enode *w;int s=1;while(s)Enode *z=NULL;w=etp.a0;s=0;while(w & w-yma*!=i)z=w; w=w-ne*t; if(!w) break;if(z) z-ne*t=w-ne

36、*t;else etp.a0=w-ne*t;delete w;s=1; /删去AET表中i值已经等于yma*的结点记录 if(etp.a0)Enode *u,*v;u=etp.a0;while(u)v=u;u=u-ne*t;v-*i=v-*i+v-m; /用*i+m来替代原有的*ii+; /进入下一条扫描线 void main() /主函数的实现 int gdriver, gmode; gdriver=DETECT; gmode=VGAHI; initgraph(&gdriver, &gmode,); /图形系统初始化 int e=11; int color=5; /color用于标识填充颜色

37、 ET et(e); et.Insert(2,5,8,4/3); et.Insert(2,5,8,-4/3); et.Insert(5,10,15,-1); et.Insert(5,10,4,6/5); /根据初始数据建立边表 po_fill(et, e, color); /调用填充函数getch(); closegraph();注第2步的实现存在两个问题：(1) 没有实现世界坐标系统(第1象限)到设备坐标系统的转换，所以显示出来的图形是以上所画图形的倒置，解决方法就是从世界坐标系统的最高y值开场扫描；(2) 由于m的取值为分数(浮点型)，这就导致像素点坐标值出现浮点型，这样经过取整运算，计算

38、出来的像素点坐标值将可能与多边形填充点真实值之间存在偏差，导致所绘制的图形不完全与实际吻合。14. 多边形各顶点坐标为(2, 2)(2, 4)(8, 6)(12, 2)(8, 1)(6, 2)及(2, 2)，在用多边形区域填充时，请写出ET及全部AET容。解：如下图：P3P1P2P6P5P4则该多边形的ET表为： 6623P2P3 5 4612-1P4P3420P1P2 3 2284P5P428-2P5P6 1该多边形的AET指针的容为：(每条扫描线均有3行指针链，第1行表示将ET表参加AET中，第2行表示从AET表中删去yi=yma*，第3行表示*i=*i+1/m后，学生只要写出第2行即可)

39、28-2P5P6284P5P4AET1284P5P428-2P5P6AET26-2P5P6AET2124P5P426-2P5P6420P1P2AET22124P5P4612-1P4P3420P1P2AET612-1P4P3AET420P1P2611-1P4P3611-1P4P3420P1P2AET3AET420P1P2611-1P4P3AET420P1P2610-1P4P3610-1P4P3AET623P2P3420P1P24 610-1P4P3623P2P3AET69-1P4P3653P2P3AET653P2P369-1P4P3AET569-1P4P3653P2P3AETAET683P2P3

40、68-1P4P368-1P4P3683P2P3AET6 15. 用扫描线种子填充算法，编写一个填充多边形区域的程序。BDEHFCGA该测试多边形的各个端点坐标分别为：A(50, 150)，B(50, 100)，C(100, 50)，D(250, 50)，E(200, 150)；F(100, 100)，G(100, 75)，H(175, 135)；/*本程序实现区域填充功能，首先输入多边形顶点的个数，回车，然后依次输入各顶点的坐标格式如下：100,123回车一定要在中间用逗号隔开噢，输完最后一个点后，屏幕上会依次画出各条边，最后填充满程序还不完善，比方颜色值应该用变量表示以易于修改，画多边形和求

41、种子点应该做成独立的函数等等，以后再做上吧，这是细节的问题扫描的次序：先上后下进栈的次序：先右后左测试数据：第一个多边形：A(50, 150)，B(50, 100)，C(100, 50)，D(250, 50)，E(200, 150)；第二个多边形：F(100, 100)，G(100, 75)，H(175, 135)；*/#include #include #include #include #include /creat a stackstruct stack_node/stack_node() ne*t=NULL; /定义构造函数int *;int y;stack_node *ne*t;ty

42、pedef stack_node stack_list;typedef stack_list *link;/用单链表来表示堆栈link stack = 0; /stack标识栈顶指针/push an elementvoid push(int *,int yy)stack_list *new_node;new_node=new stack_list();new_node-*=*;new_node-y=yy;new_node-ne*t=stack;stack=new_node;/pop an elementvoid pop(int &*,int &yy)link top;top=stack;*=s

43、tack-*;yy=stack-y;stack=stack-ne*t;delete top;/fill the plotvoid fill(int *,int y)int *0,y0,*l,*r,*lold,*rold;/*0,y0用来标记*,y的值,*l记录*的最左值,*r记录*的最右值*/int go=0,go2=0;int i=0;push(*,y);/种子像素入栈while(stack!=0)/如果栈不空则循环，stack=0表示栈空go=0; /go只是一个标记pop(*,y); /从栈中将栈顶元素弹出putpi*el(*,y,4); /将该点置色*0=*+1;/取种子右边的像素wh

44、ile(getpi*el(*0,y)!=4)/fill right 填充右边像素putpi*el(*0,y,4);*0=*0+1;*r=*0-1;/记录最右值*rold=*r;/再记录一次最右值，以备后用*0=*-1;/取种子左边的像素while(getpi*el(*0,y)!=4)/fill left 填充左边像素putpi*el(*0,y,4);*0=*0-1;*l=*0+1;/记录最左值*lold=*l;/再记录一次最左值，以备后用y0=y+1;/go up 向上移一条扫描线go2=0;/go2 也只是一个用来标记的变量while(*r*l&go=0)/查找上一条线的最右值,并记录为*r

45、if(getpi*el(*r,y0)=4)/看看上一条扫描线最右值是否超出了当前扫描线的坐标围*r=*r-1; /如果超出，则减1elsego=1;/假设go=1这句执行的话就说明找到了最右值，并在while中的go=0中判断并退出whilewhile(*l*r&go2=0)/查找上一条线的最左值，并记录为*lif(getpi*el(*l,y0)=4)/看看上一条扫描线最左值是否超出了当前扫描线的坐标围*l=*l+1; /如果超出，则加1elsego2=1;/go2=1这句执行就说明找到了最左值，并在此while中的go2=0中退出whileif(go=1&go2=1)/如果找到了最左值和最右

46、值，则执行下面的语句push(*r,y0);/先将上一条线上的最右点作为种子点入栈for(i=*l;i*l&go=0)/找下一条扫描线的最右像素if(getpi*el(*r,y0)!=4)go=1;else*r-;while(*l*r&go2=0)/找下一条扫描线的最左像素if(getpi*el(*l,y0)!=4)go2=1;else*l+;if(go=1&go2=1)/如果找到最左和最右，则执行push(*r,y0);for(i=*l;i=*r;i+)if(getpi*el(i,y0)!=4)else if(getpi*el(i-1,y0)!=4)push(i-1,y0);void mai

47、n()void fill(int *,int y);int gdriver,gmode;/*显示模式*/detectgraph(&gdriver,&gmode);initgraph(&gdriver,&gmode,);int i,j;int n,u,p*,py,p*0,py0,p*1,py1;int ya=0,yi=getma*y();printf(pleas input the number of the polygons:);scanf(%d,&u);/看看终究有多少个多边形(可能多边形里包含了多边形)for(int k=0;ku;k+)printf(pleas input the num

48、ber of the top points:);scanf(%d,&n);/看看该多边形终究有几个端点for(i=0;in;i+)/从键盘承受各顶点的坐标，依次入栈，并记录最大Y值和最小Y值printf(please input the coordinate of the points-like:100,200 :);scanf(%d,%d,&p*,&py);if(yapy)yi=py;/yi是最小Y值push(p*,py);setbkcolor(0); /cleardevice(); setcolor(4);pop(p*0,py0);/输入的最后一个顶点出栈p*=p*0;py=py0;/记录

49、最后一个顶点/draw the plotwhile(stack != 0)pop(p*1,py1);line(p*0,py0,p*1,py1);p*0=p*1;py0=py1;delay(500);/时延，慢慢画line(p*0,py0,p*,py);/依次画线，画出多边形/画完多边形后，栈为空/find the y valuej=(ya+yi)/2;/找Y的中间值,就是第一个种子点的Y值i=0;n=0;/记录入栈个数/find the seed elementwhile(igetma*()&n!=2)/按*值从0到*最大值依次查找，并在入栈个数为2的时候退出if(getpi*el(i,j)=

50、4)/如果是多边形上的点，则入栈，用n记录入栈的个数push(i,j);n=n+1;i=i+1;/i是记录当前的*值pop(i,j);/第二个交点出栈pop(n,j);/第一个交点出栈，虽然覆盖了Y值，但这不重要，我们要的是*值i=(i+n)/2;/现在i是我们要找的种子点的*值 /fill the plotfill(i,j);/将种子点作为参数传入fill()方法delay(1000);outte*t*y(100,410,the red line was drawing,fill over);getch();closegraph();特别指出：该程序在理论上是没有问题的，但是由于使用了lin

51、e函数，导致*些多边形的端点数据，会出现运行未果或者错误的问题。出现这种错误的原因就是line函数采用了离散的像素点来取代连续的边界点。大家可以试试u=1，n=3，F(100, 100)，G(100, 75)，H(175, 135)，如图(a)所示；此时的问题在于种子的选取，计算出来的种子y坐标为105，没有问题，此时i从0开场向右搜索，遇到两个边界点分别记录并在第二个边界点停顿搜索，则记录的应该分别是A点(110, 105)和B点(137.5, 105)，然后种子的*坐标就应该是(110+137.5)/2=123，结果程序运行后居然是(110+111)/2=110，这个结果说明A点是边界，A

52、点紧右相邻的点也是边界点，看这个图就知道不可能啊，在理论上是绝不可能。但是看看图(b)就知道在实际上是可能的而且是经常发生的。如果一旦出现了这种情况，fill()函数里面的诸多判断也会出现问题，而且这个问题是随着多边形的端点数据的变化而难以捕捉。105AB图(a)图(b)16. 四边形各顶点坐标为(0, 0)，(20, 0)，(20, 15)和(0, 15)，对此图形分别进展以下比例变换：(1) 使长度方向缩小一半，高度方向增长一倍；(2) 使整个图形放大一倍。解：如下图，实线局部为原图，虚线局部为变换后得到的图形： Y 30 15 (1) (2)10 20 40 *(1) 原先坐标 变换矩阵

53、 变换后坐标*=(2) 原先坐标 变换矩阵 变换后坐标*= 归一化 17.三角形各顶点坐标为10，10，10，30，30，15，试对其进展以下变换，写出变换矩阵，画出变换后的图形。沿*向平移20，沿Y向平移15，再绕原点旋转90度绕原点旋转，再沿*向平移20，沿Y轴平移15解：1由二维图形变换相关知识，可得变换矩阵为1 0 0 cos90 sin 90 0 0 1 00 1 0 -sin90 cos90 0 = -1 0 020 15 1 0 0 1 -15 20 1根据得出的新坐标可画出图形图形略新坐标的值为-25, 30-45, 30-30, 502变换矩阵为：10 10 1 0 1 0T

54、= 10 30 1 -1 0 030 15 1 20 15 1 坐标数据点 变换矩阵10 25 1T= -10 25 15 45 1由得出的新坐标画图图形略18.直线方程y=k*+b*/a+y/b=1(a!=0.b!=0)试求出图形对该直线进展对称变换得变换矩阵解：(1) k*-y+b=0=arctg(-A/B) =arctgk(1) cos2 sin2 0T= sin2 -cos2 0 (2)(Cos2-1)C/A sin2C/A 1将(1)代入(2)式可得变换矩阵，并根据万能公式sin2 =2sincos cos2 =cos2-sin2 tg =sin/cos 可得 1-K2/1+K2 2

55、K/1+K2 0T= 2K/1+K2 K2-1/K2+1 0-2bK/1+K2 2b/1+K2 1(2)*/a +y/b =1b*+ay-ab=0所以=arctg(-A/B)=arctg(-b/a).(3)将(3)代入(2)式得 (a2-b2)/(a2+b2) -2ab/(a2+b2) 0T= -2ab/(a2+b2) (b2-a2)/(b2+a2) 0 2ab2/(a2+b2) 2a2b/(a2+b2) 119. 编一程序实现直线的编码裁剪法解：具体源代码如下所示：#include graphics.h #include conio.h#include math.h#include stdi

56、o.hint w1=90, w2=270, w3=40, w4=160;/定义窗口的几个关键点坐标void clipline(char *a,int &*,int &y,int *1,int y1,int *2,int y2) /求出与区域中各个方向边的交点int *t1=0,yt1=0,*t2=0,yt2=0,*t3=0,yt3=0,*t4=0,yt4=0;if(*a=1)yt1=y1+(y2-y1)*(w1-*1)/(*2-*1);*t1=w1; /求左交点if(*(a+1)=1)yt2=y1+(y2-y1)*(w2-*1)/(*2-*1);*t2=w2; /求右交点if(*(a+2)=1

57、)*t3=*1+(*2-*1)*(w3-y1)/(y2-y1);yt3=w3; /求下交点if(*(a+3)=1)*t4=*1+(*2-*1)*(w4-y1)/(y2-y1);yt4=w4; /求上交点/有可能会求出两个交点，例如左交点和上交点，必然有一个是超出窗口围的/必须将其排除if(*t1=90 & yt1=40) *=*t1; y=yt1;if(*t2=90 & yt2=40) *=*t2; y=yt2;if(*t3=90 & yt3=40) *=*t3; y=yt3;if(*t4=90 & yt4=40) *=*t4; y=yt4;void code(int *i, int yi,

58、char *a) /四位编码的实现if(*iw2) *(a+1)=1; /右if(yiw4) *(a+3)=1; /上return;void clipdraw(int *1, int y1, char *a, int *2, int y2, char *b) int *11,y11,*21,y21;int s1=0,s2=0;code(*1,y1,a); /得到直线第一个端点的编码code(*2,y2,b); /得到直线第二个端点的编码 if(*a=0 & *b=0 & *(a+1)=0 & *(b+1)=0 & *(a+2)=0 & *(b+2)=0 & *(a+3)=0 & *(b+3)=

59、0)line(*1,y1,*2,y2); /假设两个端点的编码全为0，则直线完全可见else if(a0-48)*(b0-48)+(a1-48)*(b1-48)+(a2-48)*(b2-48)+(a3-48)*(b3-48)=0) /两端点四位编码的逻辑乘为0if(!(a0=0&a1=0&a2=0&a3=0) /第一个端点不在窗口，求与窗口交点clipline(a,*11,y11,*1,y1,*2,y2);s1=1;if(!(b0=0&b1=0&b2=0&b3=0) /第二个端点不在窗口，求与窗口交点clipline(b,*21,y21,*1,y1,*2,y2);s2=1;if(s1=1&s2

60、=1) line(*11,y11,*21,y21); /说明两个端点均不在窗口，直线与窗口有两个交点if(s1=1&s2=0) line(*11,y11,*2,y2); /说明第一个端点不在窗口，第二个在，直线与窗口有一个交点if(s1=0&s2=1) line(*1,y1,*21,y21); /说明第二个端点不在窗口，第一个在，直线与窗口有一个交点void main()int *1,y1,*2,y2;scanf(%d%d%d%d,&*1,&y1,&*2,&y2);/读入直线两个端点的坐标char a4=0,0,0,0;char b4=0,0,0,0; /分别初始化两个端点的编码数组int d