多边形区域填充算法

13.设五边形的五个顶点坐标为(10,10)，(15,5)，(12,5)，(8,2)和(4,5)，利用多边形区域填充算法，编一程序生成一个实心图。解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表：ymaxx|ymin1/knext6-10543210用于存放AET活动边表该多边形的AET指针的内容为：1AET为空234ABCDE…58-4/3DE584/3DC1046/5EA1015-1BAAET58-4/3DE584/3DCAET520/3-4/3DEDCAETAET528/3-4/3516/3-4/3DEDC532/3-4/31046/5EADC54-4/35678910具体编程实现如下：第1步：(1)根据输入的五个顶点坐标找到y值最小的点(例如点D，此时y=2)，并找到与D有边关系的两个顶点(此时为E和C)，在y=2处建立ET边表记录(ymax、xi和m值均可通过顶点坐标间的计算得到，例如DE边的建立，特别注意：当D点和E点y坐标值相同时，也即是DE与x轴平行，该边不能计入ET边表)，之后标记D点被访问过；(2)排除访问过的点以及和该点相关联的边，重复(1)直至将ET表建立完善。[注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y坐标值，ET边表采用邻接表的数据结构第2步：根据ET表构建AET表，并逐行完成多边形填充，具体的C++代码如下：(1)建立头文件base_class.h，主要是边表结点结构体和ET边表类的实现enumResultCode{Success,Failure};templateclassTstructEnode{Enode(){next=NULL;}Enode(Tpymax,floatpxi,floatpm,Enode*pnext){ymax=pymax;xi=pxi;m=pm;next=pnext;}Tymax,xi;//ymax表示最大的y值，xi表示最底端点的x坐标值floatm;//m表示斜率的倒数Enode*next;};//定义了ET表和AET表中结点的结构体5124/3DEBA1015-1AET1026/56/5EABA1014-1AET1032/56/5EABA1013-1AET1038/56/5EABA1012-1AET1044/56/5EABA1011-1AET10106/5EABA1010-1templateclassTclassET{public:ET(intmSize);~ET();ResultCodeInsert(intu,Tymax,floatxi,floatm);intn;//覆盖该多边形的扫描线的总数，从0开始计数EnodeT**a;};//定义了边表类templateclassTETT::ET(intmSize){n=mSize;a=newEnodeT*[n];for(inti=0;in;i++)a[i]=0;}//ET边表的初始化templateclassTETT::~ET(){EnodeT*p,*q;deletea[0];for(inti=1;in;i++){p=a[i];q=p;while(p){p=p-next;deleteq;q=p;}}delete[]a;}//析构函数负责回收内存空间templateclassTResultCodeETT::Insert(intu,Tymax,floatxi,floatm){if(u0||un-1)returnFailure;EnodeT*p=newEnodeT(ymax,xi,m,a[u]);a[u]=p;returnSuccess;}//依次插入结点构建出边表，其中a[1]到a[10]用于构建ET边表//a[0]用于构建活动AET边表(2)填充函数po_fill的实现和主函数的实现#includebase_class.h#includegraphics.h#includeiostream.hvoidpo_fill(ETint&etp,intep,intcolor)//多边形填充函数的实现{inti=1;//i作为控制变量标识扫描线while(iep-1){if(etp.a[i]!=NULL){Enodeint*p,*r;p=etp.a[i];r=etp.a[0];while(p){Enodeint*q=newEnodeint(p-ymax,p-xi,p-m,NULL);if(!etp.a[0]){etp.a[0]=q;r=q;}else{if(r-xi==q-xi){q-next=r-next;r-next=q;r=q;}if(r-xiq-xi){etp.a[0]=q;q-next=r;}else{while(q-xir-xi&&r-next)r=r-next;if(r-next){q-next=r-next;r-next=q;}else{r-next=q;q-next=NULL;}}}p=p-next;}}//按照xi值的大小将当前ET表中的记录放置到AET表中Enodeint*f,*g;if(etp.a[0]){f=etp.a[0];while(f-next){g=f;f=f-next;for(intj=g-xi;j=g-next-xi;j++)putpixel(j,i,color);}//把一对相邻结点的xi区间范围进行填充}if(etp.a[0]!=NULL){Enodeint*w;ints=1;while(s){Enodeint*z=NULL;w=etp.a[0];s=0;while(w&&w-ymax!=i){z=w;w=w-next;}if(!w)break;if(z)z-next=w-next;elseetp.a[0]=w-next;deletew;s=1;}//删去AET表中i值已经等于ymax的结点记录if(etp.a[0]){Enodeint*u,*v;u=etp.a[0];while(u){v=u;u=u-next;v-xi=v-xi+v-m;}}//用xi+m来替代原有的xi}i++;//进入下一条扫描线}}voidmain()//主函数的实现{intgdriver,gmode;gdriver=DETECT;gmode=VGAHI;initgraph(&gdriver,&gmode,);//图形系统初始化inte=11;intcolor=5;//color用于标识填充颜色ETintet(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的取值为分数(浮点型)，这就导致像素点坐标值出现浮点型，这样经过取整运算，计算出来的像素点坐标值将可能与多边形填充点真实值之间存在偏差，导致所绘制的图形不完全与实际吻合。14.已知多边形各顶点坐标为(2,2)(2,4)(8,6)(12,2)(8,1)(6,2)及(2,2)，在用多边形区域填充时，请写出ET及全部AET内容。解：如图所示：则该多边形的ET表为：65P3P1P2P6P5P4623P2P34321该多边形的AET指针的内容为：(每条扫描线均有3行指针链，第1行表示将ET表加入AET中，第2行表示从AET表中删去yi=ymax，第3行表示xi=xi+1/m后，学生只要写出第2行即可)12328-2P5P6284P5P4420P1P2612-1P4P3AET28-2P5P6284P5P4AET28-2P5P6284P5P4AET26-2P5P62124P5P4420P1P2612-1P4P3AET420P1P2611-1P4P3AET26-2P5P62124P5P4AET420P1P2611-1P4P3AET420P1P2612-1P4P3AET420P1P2611-1P4P3AET420P1P2610-1P4P345615.用扫描线种子填充算法，编写一个填充多边形区域的程序。该测试多边形的各个端点坐标分别为：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回车一定要在中间用逗号隔开噢，输完最后一个点后，屏幕上会依次画出各条边，最后填充满程序还不完善，比如颜色值应该用变量表示以易于修改，画多边形和求种子点应该做成独立的函数等等，以后再做上吧，这是细节的问题AET420P1P2623P2P3610-1P4P3AET653P2P369-1P4P3AET683P2P368-1P4P3AET623P2P3610-1P4P3AET653P2P369-1P4P3AET653P2P369-1P4P3AET683P2P368-1P4P3ADCEFGHB扫描的次序：先上后下进栈的次序：先右后左测试数据：第一个多边形：A(50,150)，B(50,100)，C(100,50)，D(250,50)，E(200,150)；第二个多边形：F(100,100)，G(100,75)，H(175,135)；*****************************************************************************/#includegraphics.h#includestdio.h#includedos.h#includeconio.h#includestdlib.h//creatastackstructstack_node{//stack_node(){next=NULL;}//定义构造函数intx;inty;stack_node*next;};typedefstack_nodestack_list;typedefstack_list*link;//用单链表来表示堆栈linkstack=0;//stack标识栈顶指针//pushanelementvoidpush(intxx,intyy){stack_list*new_node;new_node=newstack_list();new_node-x=xx;new_node-y=yy;new_node-next=stack;stack=new_node;}//popanelementvoidpop(int&xx,int&yy){linktop;top=stack;xx=stack-x;yy=stack-y;stack=stack-next;deletetop;}//filltheplotvoidfill(intx,inty){intx0,y0,xl,xr,xlold,xrold;/*x0,y0用来标记x,y的值,xl记录x的最左值,xr记录x的最右值*/intgo=0,go2=0;inti=0;push(x,y);//种子像素入栈while(stack!=0)//如果栈不空则循环，stack==0表示栈空{go=0;//go只是一个标记pop(x,y);//从栈中将栈顶元素弹出putpixel(x,y,4);//