《计算机图形学》第1-5章课后习题参考答案2.pdf

《《计算机图形学》第1-5章课后习题参考答案2.pdf》由会员分享，可在线阅读，更多相关《《计算机图形学》第1-5章课后习题参考答案2.pdf（54页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

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

4、7、当前计算机图形学研究的课题有哪些？答：见课本P10-U页 的1.4节。8、简述三维图形生成和输出的流水线？答：见课本P13页 1.5.6.节。9、向量图形和点阵图形之间的区别有哪些？答：通过矢量法产生的图形称为矢量图形或者向量图形，用描点法产生的图形称为点阵图形。向量图形区别点阵图形的特点在于描述图形几何形状的数学模型及依据此模型生成几何图形的计算机命令。向量图形由各个基本图形构成，这就要求各个基本图形有各自独立的信息。如果用点阵图形来表示一个向量图形，构成向量图形的某个基本图形（如直线段、圆弧等）的所有点应有一个信息。因此，在描述一个基本图形时，同时要描述其相应的信息。向量图形最基本的优

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

6、展示了计算机图形系统的组成。计算机图形系统是为了支持应用程序，便于实现图形的输入输出的硬件和软件组合体。没有图形系统支持，就难以实现应用软件的开发。主要功能见课本2.1.2节。2、计算机图形系统有哪几种？各有什么特点？答：一种分类方法：交互式图形系统允许操作者以某种方式（对话方式或命令方式）来控制和操作图形生成过程，使得图形可以边生成、边显示、边修改，直至符合要求为止。而被动式绘图系统，图形在生成过程中，操作者无法对图形进行实时操作和控制，不具备交互功能，只提供各种图形命令或图形程序库，通过编程获得所需图形。另一种分类方法：见课本2.1.3节，分为脱机绘图系统、联机绘图系统和交互式绘图系统。3

7、、阴极射线管由哪些部分组成？它们的功能分别是什么？答：C R T 由四部分组成：电子枪、聚焦系统、偏转系统和荧光屏，这四部分都在真空管内。电子枪由灯丝、阴极和控制栅极组成。灯丝加热阴极，阴极表面向外发射自由电子，控制栅控制自由电子是否向荧光屏发出，若允许电子通过，形成的电子流在到达屏幕的途中，被聚焦系统（电子透镜）聚焦成很窄的电子束，由偏转系统产生电子束的偏转电场（或磁场）,使电子束左右、上下偏转，从而控制荧光屏上光点上下、左右运动，使得在指定时刻在屏幕指定位置上产生亮点。4、光栅扫描显示器由哪些部分组成？它们的功能分别是什么？答：见课本P21页图2.9所展示的组成框图，其后有各部分的介绍及功

8、能。5、对于分辨率为1024*1024的光栅系统,若每一像素用8 位 和 12位二进制来表示存储信息,各需多大光栅存储容量以及显存？每一屏幕最多能显示多少颜色？若 R,G,B 灰度都占8位，其显示颜色的总数是多少？解：1）每一像素用8位二进制来表示存储信息，所需容量为1024*1024*1=220（Byte）=1 MB彩色素：28=256（项）2）若每一像素用12位二进制表示存储信息，所需容量为：1024*1024*1.5=1.5*2?（Byte）=1.5MB（由于显示卡的显存是按2 的指数次倍增长的，因此所需显存为2M）彩色素：2o=4096（项）3）颜色总数：2*2*2=2 =167772

9、16（种）6、对 于 19英寸显示器，若 X 和 Y 两方向的分辨率相等，即 1024*1024,那么每个像素点的直径是多少？19*25.4 19解：-尸=0.33(mm)或-尸=0.013(英寸)1024V2 1024V27、对于分辨率为1024X768的光栅系统，若调色板设置为真彩色32位，此时需要显示一个三维图形，各需要多大光栅存储容量以及显存？答：调色板为真彩色32位，即意味着像素值的位长为32所需容量为1024*768*32/8*3=9MB因此所需要的显存为16M8、GKS有哪三种坐标系？它们有什么不同？试写出它们之间对应关系？答：GKS有 3 种不同的坐标系。第一种是供应用程序使用

10、的实际世界坐标系统（WorldCoordinate System,简 称 WC）；第二种是G K S内部使用的规范设备坐标系（NormalizedDevice Coordinate,简称NDC）,它的取值范围为0,1,这是一种既与设备无关也与应用无关的坐标系；第三种是各工作站物理设备使用的设备坐标系（Device Coordinate System,简 称 DC）。G K S只支持二维对象的图形处理，因此上述3 个坐标系都是二维坐标系。详见课本图3.28的描述。9、GKS中输入设备有哪6 种逻辑功能？请各举出对应的物理设备。答：见课本2.45节。10、当前主流的图形软件有哪些？答：见课本2.6

11、.3节。第三章1、编写画一正方形程序，并在其中用不同的颜色画15个正方形，每一个都比前一个小。#includefctgraphics.h,#includeconio.hvoid main()(int i,color=0,ls=0;intj=700;int gdriver=VGA;int gmode=VGAHI;initgraph(&gdriver,&gmode,)；setbkcolor(15);fbr(i=0;i225;i=i+15,j=j-30)setcolor(color);bar(i,i,j,j)；color;ls+;31批改说明；必须至少包含graphics*initgraph(&gd

12、river,&gmode,u,);必须包含15个正方形，一般用for循环，也可能用到while等。注意查看是否是正方形(i,i,j,j)即：x2-xl=y2-yl 注 意 查 看 颜 色 是 否 有 1 5 种：也就是说gdriver=CGA肯定是错的，可以为DETECT、VGA、EGAo3-2批改说明；注意查看3 部分内容 setlinestyle(i%4),0,k);k 对线宽的设置。getch();closegraph();2、用不同的线形绘制题1 中的图形#include“graphics.h#include“conio.hvoid main()(int i,color=l,ls=0;

13、intj=700;int gdriver=VGA;gmode=VGAHI;initgraph(&gdriver,&gmode,)；setbkcolor(15);fbr(i=0;i0;i-,j-)(setfillstyle(EMPTY_FILL,O);pieslice(387+j,290,start,end,3 7);pieslice(525+j,290,start,end,37);start+=40;end+=40;delay(5);/处于运动状态的自行车车轮的轴线的绘制putimage(i-1,200,w,COPY_PUT);line(2,327,562,327);delay(lO);自行车

14、行驶动画的实现)fbr(i=0;iabs(y2-y 1)length=abs(x2-x 1);elselength=abs(y2-y 1);increx=(x2-x 1 )/length;increy=(y2-y l)/length;x=xl;y=yi;for(i=1 ;i=length;i+)putpixel(x,y,l);x=x+increx;y=y+increy;void main()int driveiDETECT,mode=0;initgraph(&driver,&mode,“)；int x 1 =0,y 1 =0,x2=4,y2=12;int x3=12,y3=4;DDA_Line

15、(x 1 ,yl,x2,y2);DDA_Line(x I,yl,x3,y3);getch();)3.根据逐点比较法编程序画一段圆弧，其圆心为(0,0),圆弧两点为A(5,0)、B(0,5)方 法 1：顺 4 象限#include graphics.h#include stdio.h#include conio.hvoid ZDBJ_ARC(float xO,float yO,float xl,float yl,float x2,float y2);void main()int gdriver=CGA,mode=CGACO;initgraph(&gdriver,&mode,n n);ZDBJ_A

16、RC(0,0,25,0,0,25);getch();closegraph();void ZDBJ_ARC(float xO,float yO,float xl,float yl,float x2,float y2)float f=O.O,F;float dx=l,dy=l;while(abs(x 1 -x2)1)(if(f=0)(xl=xl-dx;yi=yi;putpixel(xl,yl,l);f=f-2*dx*(x 1 -xO)+dx*dx;)elsex1=x1;yl=yl+dy;putpixel(xl,yl,l);f=f+-2*dy*(yl-y0)+dy*dy;|)方法2：逆 4 象限#i

17、nclude graphics+”include stdlib.hM#include conio.hvoid ZDBJ_ARC(float xO,float yO,float x 1,float y l,float x2,float y2);void main()int gdriver=CGA,mode=CGACO;initgraph(&gdriver,&mode,M n);ZDBJ_ARC(0,0,0,25,25,0);getch();closegraph();void ZDBJ_ARC(float xO,float yO,float xl,float yl,float x2,float y

18、2)float f=O.O,F;float dx=l,dy=l;while(abs(y l-y2)1)(ig O)(xl=xl;yl=yl-dy;putpixel(xl,yl,l);f=f-2*dy*abs(y 1-yO)+dy*dy;elsexl=xl+dx;yl=yl;putpixel(xl,yl,l);f=f+-2*dx*abs(x 1 -xO)+dx*dx;)方法3：顺 1象限#include“graphics.省略了图形初始化的步骤#include“conio.h#include“math.hvoid main()(int x 1 =5,y 1 =0,x2=0,y2=5;int x0

19、=0,y0=0;int R=sqrt(x2-x0)*(x2-x0)+(y2-y0)*(y2-y0);int dx=abs(x2-xl);int dy=abs(y2-yl);int n=dx+dy;putpixel(x2,y2,l);intf;int x=x2,y=y2;for(int i=O;i n;i+)(f=(x-xO)*(x-xO)+(y-yO)*(y-yO)-R*R;if(f=0)putpixel(x,y-J);elseputpixel(x-H-,y,l)；getch();closegraph();另一种做法是采用课本P97页表4.2的公式4.编一程序用角度DDA法画一圆以圆点为圆心，

20、半径为20 的圆#include“graphics./省略了图形初始化的步骤#include conio.h#include math.hvoid main()(int x0=0,y0=0,R=20;int xl,yl,xi,yi;int N=R*8;float a=2*3.14/N;xl=20,yl=0;for(int i=l;iv=N;i+)xi=xO+R*cos(i*a)yi=yO+R*sin(i*a);line(xl,yl,xi,yi);xl=xi;yi=yi;getch();closegraph();)5.如果线段端点坐标值不是整数，采用DDA算法产生的直线和将端点坐标值先取整后再用

21、Brcssenham算法产生的直线是否完全相同？为什么？能否扩充整数Bressenham算法使之能够处理当线段端点坐标值不是整数的情况。答：不相同。因 为 DDA算法总是选择A x 或者A y 中的较大者作为步进的方向，不失一般性，假设选择x 方向，则 x 方向每前进个像素点，y 方向前进的像素点个数应该在0,1区间，但是由于采用了(向上或者向下或者四舍五入)取整运算，必然会导致某些像素点偏在了真实直线的一侧。而B r e s s e nh a m算法每一步都会根据实际直线与网格的距离来决定下一个像素点的选择，因此所选像素点更加贴近于真实的直线。可以扩充整数B r e s s e nh a m

22、算法使之能够处理当线段端点坐标值不是整数的情况。6 .若采用B r e s e nh a m算法实现画圆，写出算法实现的具体流程(包括判别公式推导等等)。答：给定圆心在原点，半径为R的圆，其方程为x 2+y 2=R 2,构造函数F(x,y尸x 2+y 2-R 2,对于圆上的点，有F(x,y)=O；对于圆外的点，F(x,y)0；而对于圆内的点，F(x,y)0 此处仅考虑如图所示的第一象限内xe卜,R/、反 的1/8圆弧，此时中点B r e s e nh a m画圆算法要从(0,咫到(R/JI R/四)顺时针地确定最佳逼近于该圆弧的像素序列。由于最大位移方向为x,因此其基本原理：每次x方向匕走一步

23、，而y方向上或减1或减0。假定当前与圆弧最近者已确定，为P N,y,),那么下一候选像素只能是正右方的P u(X +1,y)和右下方的P d(Xi +1,y 4)。到底选取哪一个候选点依旧用中点进行判别。假设M是P u和P d的中点,即有M(Xi+l,y0.5),则当F(XM,囚)0,M在圆外，说明P d离圆弧更近；当F(XM,y M尸0，则约定取P d。构造判别式 d i=F(xM,yM)=F(Xi +1,y0.5)=(Xi +l)2+(yr0.5)2-R2(1)当dsO,取Pu(Xi+l,y,),计算下一步的的判别式di+i=F(xu,yu)=F(Xj +2,y0.5)=(x(+2)2+(

24、y j-0.5)2-R2=&+2 x i+3所以沿正右方向，&的增量为2%+3。(2)当d仑0,取Pd(Xi+l,y i+l),计算下一步的的判别式di+i=F(xd,yd)=F(Xj +2,yr1.5)=(x s +2)2+(yr1.5)2-R2=&+2(%而+5所以沿右下方向，&的增量为2 8-乂)+5。显然，所绘制圆弧段的第一个像素为P0(0,R),因此判别式d o的初始值为L 2 5-R,可以令d=d-0.2 5来摆脱小数运算，则判别式dS O对应于4 -0.2 5,由于d始终是整数，d i -0.2 5等价于d,bP=p;m_ maxlndex=len-1;void Bezier:d

25、raw()通过公有函数调用私有函数drawFrame();drawCurve();)void Bezier:drawFrame()其功能是绘制出多边形和各个端点setcolor(12);fbr(int i=0;im_maxIndex;i+)(line(bPi.x,bPi.y,bPi+l.x,bPi+l.y);绘制多边形circle(bPi.x,bPi.y,5);绘制各个端点circle(bPm_maxlndex.x,bPm_maxIndex.y,5);void Bezier:drawCurve()实现多段Bezier曲线绘制的功能(fbr(int i=0;i=m_maxIndex-3;i+=3

26、)(drawCurve(i,i+1 ,i+2,i+3);void Bezier:drawCurve(int pO,int pl,int p2,int p3)实现绘制某一段Bezier曲线的功能(double tmpx=0.0;double tmpy=0.0;double t=0.0;for(；tbP=p;m maxlndex=len;void B_Spline:draw()通过公有函数调用私有函数(drawFrame();drawCurve();void B_Splinc:drawFramc()其功能是绘制出多边形和各个端点(setcolor(12);fbr(int i=O;im_maxlnd

27、ex-l;i+)(line(bPi.x,bPi.y,bPi+l.x,bPi+l.y);绘制多边形circle(bPi.x,bPi.y,5);绘制多边形各个端点)circle(bPm maxindex-l.x,bPm_maxIndex-l.y,5);void B Spline:drawCurve()实现多段B样条曲线绘制的功能fbr(int i=0;im_maxIndex-2;i+)(drawCurve(i,i+l,i+2);)void B_Spline:drawCurve(int pO,int pl,int p2)实现绘制某一段Bezier曲线的功能double tmpx=0.0;double

28、 tmpy=0.0;double t=0.0;for(；t 7 3 6 劭+9 7 9 2 q +1 3 6 0 0 0 6/2=1 0 5 6 4所求多项式为 y=f(x)=1.0 7 9 3+1.0 9 2 1 x-0.0 0 6 7 9 6 x2劭=1.0 7 9 3%=1.0 9 2 12=-0.0 0 6 7 9 61 3.设五边形的五个顶点坐标为(1 0,1 0),(1 5,5),(1 2,5),(8,2)和(4,5),利用多边形区域填充算法，编程序生成一个实心图。解：假设以上五个顶点依次对应编号A-B-C-D-E,首先计算得到E T 表：6-10543210该多边形的AET指针的

29、内容为:1 AET为空2345具体编程实现如下：第 1 步：（1）根据输入的五个顶点坐标找到y 值最小的点（例如点D,此时y=2）,并找到与D有边关系的两个顶点（此时为E 和 C）,在 y=2处建立ET边表记录（ymax、x i和 m 值均可通过顶点坐标间的计算得到，例如D E边的建立，特别注意：当 D 点和E 点 y 坐标值相同时,也即是D E与 x 轴平行，该边不能计入ET边表），之后标记D 点被访问过；（2）排除访问过的点以及和该点相关联的边，重复（1）直至将ET表建立完善。注 边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y 坐标值，ET边表采用邻接表的数据结

30、构第 2 步：根据ET表构建AET表，并逐行完成多边形填充，具体的C+代码如下：（1）建立头文件base_class.h,主要是边表结点结构体和ET边表类的实现enum ResultCodeSuccess,Failure;template struct EnodeEnode()next=NULL;Enode(T pymax,float pxi,float pm,Enode*pnext)ymax=pymax;xi=pxi;m=pm;next=pnext;)T ymax,xi;/ymax表示最大的y 值，x i表示最底端点的x 坐标值float m;/m表示斜率的倒数Enode*next;)；定义

31、了 ET表和AET表中结点的结构体template class ETpublic:ET(int mSize);ET();ResultCode Insert(int u,T ymax,float xi,float m);int n;覆盖该多边形的扫描线的总数，从 0 开始计数Enode*a;);定义了边表类template ET:ET(int mSize)n=mSize;a=new Enode*n;for(int i=0;in;i-F+)ai=0;/ET边表的初始化template ET T:ET()Enode*p,*q;delete a0;fbr(int i=l;inext;delete q;

32、q=p;)delete a;析构函数负责回收内存空间template ResultCode ET:Insert(int u,T ymax,float xi,float m)(if(un-l)return Failure;Enode*p=new Enode(ymax,xi,m,au);au=p；return Success;)依次插入结点构建出边表，其中al到 a10用于构建ET边表/a0用于构建活动AET边表 填 充 函 数 的 实 现 和 主:函 数 的 实 现#include nbase_class.hn#include graphicsj”#include void po_fill(ET

33、&etp,int ep,int color)/多边形填充函数的实现int i=l;i 作为控制变量标识扫描线whilc(iep-l)ifi(etp.ai!=NULL)Enode*p,*r;p=etp.ai;r=etp.a0;while(p)Enode*q=new Enode(p-ymax,p-xi,p-m,NULL);if(!etp.a0)etp.a0=q;r=q;elseififr-xi=q-xi)q-next=r-next;r-next=q;r=q;if(r-xiq-xi)etp.a0=q;q-next=r;else while(q-xir-xi&r-next)r=r-next;ifl(r

34、-next)q-next=r-next;r-next=q;else r-next=q;q-next=NULL;p=p-next;)按照x i值的大小将当前ET表中的记录放置到AET表中Enode*f,*g;if(etp.aO)(f=etp.aO;while(f-next)g=f；f=f-next;fbr(int j=g-xi;jnext-xi;j+)putpixel(j,i,color);/把一对相邻结点的x i区间范围进行填充if(etp.aO!=NULL)Enode*w;int s=l;while(s)(Enode*z=NULL;w=etp.aO;s=0;while(w&w-ymax!=i

35、)(z=w;w=w-next;)if(!w)break;iRz)z-next=w-next;else etp.a0=w-next;delete w;s=l;删去AET表中i 值已经等于ymax的结点记录if(etp.aO)(Enode*u,*v;u=etp.aO;while(u)(v=u;u=u-next;v-xi=v-xi-i-v-m;)用xi+m来替代原有的xii+；进入下一条扫描线)void main。主函数的实现int gdriver,gmode;gdriver=DETECT;gmode=VGAHI;initgraph(&gdriver,&gmode,巧;图形系统初始化int e=l

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

37、取整运算，计算出来的像素点坐标值将可能与多边形填充点真实值之间存在偏差，导致所绘制的图形不完全与实际吻合。1 4,已知多边形各顶点坐标为(2,2)(2,4)(8,6)(12,2)(8,1)(6,2)及(2,2),在用多边形区域填充时，请写出ET及全部AET内容。解:如图所不:2109876543210则该多边形的ET表为:64P2P3623420P4P3612-1该多边形的AET指针的内容为：（每条扫描线均有3行指针链，第1行表示将E T表力H入A E T中，第2行表示从AET表中删去y i=y m a x，第3行表示X i=X i+l/m后，学生只要写出第2行即可）A E T _ _ _ _

38、 _ _ _ _ _ P 1 P 2 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ P 4P 342061 2-1A E T _ _ _ _ _ _ _ _ _ P 1 P 2 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ P 4 P 342061 1-1A E T _ _ _ _ _ _ _ _ _ P 1 P 2 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ P 4P 342061 1-1A E T 、,P 1,P 2 ,P 4P 34420.61 1-1651 5.用扫描线种子填充算法，编写一个填充多边形区域的

39、程序。该测试多边形的各个端点坐标分别为：A(50,1 50),B(50,1 0 0),C(1 0 0,50),D(2 50,50),E(2 0 0,1 50)；F(1 0 0,1 0 0),G(1 0 0,7 5),H(1 7 5,1 3 5)；本程序实现区域填充功能，首先输入多边形顶点的个数，回车，然后依次输入各顶点的坐标格式如下：1 0 0,1 2 3 回车一定要在中间用逗号隔开噢，输完最后一个点后，屏幕上会依次画出各条边，最后填充满程序还不完善，比如颜色值应该用变量表示以易于修改，画多边形和求种子点应该做成独立的函数等等，以后再做上吧，这是细节的问题扫描的次序：先上后下进栈的次序：先右后

40、左测试数据：第一个多边形:A(5 0,1 5 0),B(5 0,1 0 0),C(1 0 0,5 0),D(2 5 0,5 0),E(2 0 0,1 5 0)；第二个多边形：F(1 0 0,1 0 0),G(1 0 0,7 5),H(1 7 5,1 3 5)；#include#include#include#include#include/creat a stackstruct stack node/stack_node()next=NULL;定义构造函数int x;int y;stack_node*next;typedef stack node stack_list;typedef stac

41、k list*link;用单链表来表示堆栈link stack=0;/stack 标识栈顶指针/push an elementvoid push(int xx,int yy)(stack_list*new_node;new_node=new stack_list();new_node-x=xx;new_node-y=yy;new_node-next=stack;stack=new_node;/pop an elementvoid pop(int&xx,int&yy)link top;top=stack;xx=stack-x;yy=stack-y;stack=stack-next;delete

42、top;)/fill the plotvoid fill(int x,int y)int xO,yO,xl,xr,xlold,xro!d;/*xO,yO用来标记x,y的值,xl记录x 的最左值,x r记录x 的最右值*/int go=0,go2=0;int i=0;push(x,y);种子像素入栈while(stack!=O)如果栈不空则循环，stack=O表示栈空go=0;/go只是一个标记pop(x,y);/从栈中将栈顶元素弹出putpixel(x,y,4);将该点置色xO=x+l;取种子右边的像素while(getpixel(x0,y)!=4)/fill right 填充右边像素(put

43、pixel(x0,y,4);xO=xO+l;xr=xO-l;/记录最右值xrold=xr;再记录一次最右值，以备后用xO=x-l;取种子左边的像素while(getpixel(x0,y)!=4)/fill left 填充左边像素|putpixel(x0,y,4);xO=xO-l;)xl=xO+l;/记录最左值xlold=xl;再记录一次最左值，以备后用yO=y+l;/go u p 向上移一条扫描线go2=0;/go2也只是一个用来标记的变量while(xrxl&go=0)查找上一条线的最右值，并记录为xr(if(getpixel(xr,yO尸=4)/看看上一条扫描线最右值是否超出了当前扫描线的

44、坐标范围xr=xr-l;/如果超出，则 减 1elsego=l;若 go=l这句执行的话就说明找到了最右值，并在while中的go=0中判断并退出whilewhile(xl xr&go2=0)查找上一条线的最左值，并记录为xl(if(getpixel(xl,y0)=4)看看上一条扫描线最左值是否超出了当前扫描线的坐标范围xl=xl+l;如果超出，则 力 口 1elsego2=l;/go2=l这句执行就说明找到了最左值，并在此while中的go2=0中退出whileif(go=l&go2=D 如果找到了最左值和最右值，则执行下面的语句push(xr,yO);先将上一条线上的最右点作为种子点入栈f

45、or(i=xl;ivxr;i+)从最左到最右循环，在每个连续区间上找一个种子点入栈(if(getpixel(i,yO)!=4)如果不是边界点,什么也不做 这样做的目的是如果出现ooBBooBBoooBooo的情况，其中o 是未填充的点，B 是边界点else if(getpixel(il,y0)!=4)如果是边界点，则看它左边的点是不是边界点,如果不是，则入栈(push(i-l,yO);实际入栈的是最靠近边界点的右像素)yO=y-l;/go dow n向下移一条扫描线go=0;go2=0;xl=xlold;还原最左，最右xr=xrold;while(xrxl&go=0)找卜一条扫描线的最右像素(

46、if(getpixel(xr,y0)!=4)go=l；elsexr;)while(xlvxr&go2-0)找下一条扫描线的最左像素(if(getpixel(xl,y0)!=4)go2=l;elsexl+;)if(go=l&go2=l)如果找到最左和最右，则执行push(xr,yO);fbr(i=xl;i=xr;i+)(if(getpixel(i,y0)!=4)else ififgetpixel(i-1 ,yO)!=4)(push(i-l,yO);)void main()|void fill(int x,int y);int gdriver,gmode;/*显示模式*/detectgraph(&

47、gdriver,&gmode);initgraph(&gdriver,&gmode/n,);int i,j;int n,u,px,py,pxO,pyO,px 1 ,py 1;int ya=O,yi=getmaxy();printfifpleas input the number of the polygons:);scanf(”%d”,&u);看看究竟有多少个多边形(可能多边形里包含了多边形)fbr(int k=0;ku;k+)printf(npleas input the number of the top points:)；scanf(%d”,&n);看看该多边形究竟有儿个端点for(i=

48、0;ivn;i+)从键盘接受各顶点的坐标，依次入栈，并记录最大Y值和最小Y值printfifplease input the coordinate of the points-like:100,200:”)；scanf(n%d,%dH,&px,&py);if(yapy)yi=py;/yi是最小Y值push(px,py);setbkcolor(O);/cleardevice();setcolor(4);pop(pxO,pyO);输入的最后一个顶点出栈px=pxO;py=pyO;记录最后一个顶点/draw the plotwhile(stack!=0)(pop(pxl,pyl);line(pxO,

49、pyO,pxl,pyl);px0=px1;py0=pyl;delay(500);时延，慢慢画)line(pxO,pyO,px,py);依次画线，画出多边形)画完多边形后，栈为空/find the y valuej=(ya+yi)/2;找 Y 的中间值,就是第一个种子点的Y 值i=0;n=0;记录入栈个数/find the seed elementwhile(igetmaxx()&n!=2)/J$X 值从0 到 X 最大值依次查找，并在入栈个数为2 的时候退出(if(gctpixel(i,j)=4)如果是多边形上的点，则入栈，用 n 记录入栈的个数(push(ij);n=n+l;)i=i+l;i

50、 是记录当前的X 值pop(i,j);第二个交点出栈pop(n,j);第一个交点出栈，虽然覆盖了 Y 值，但这不重要，我们要的是X 值i=(i+n)/2;现 在 i 是我们要找的种子点的X 值/fill the plotfiii(i,j)；/将种子点作为参数传入fm()方法delay(lOOO);outtextxy(100,410,nthe red line was drawing,fill over”)；getch();closegraph();特别指出：该程序在理论上是没有问题的，但是由于使用了 l in e 函数，导致某些多边形的端点数据，会出现运行未果或者错误的问题。出现这种错误的原因