多边形区域填充算法

13.设五边形的五个顶点坐标为(10,10)，(15,5)，(12,5)，(8,2)和(4,5)，利用多边形区域填充算法，编一程序生成一个实心图。解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表：AEDCBAEDCBymaxx|ymin1/knext……1041046/5EA1015-1BA545858-4/3DE584/3DC210用于存放AET活动边表该多边形的AET指针的内容为：1AET为空5858-4/3DE584/3DCAET2DCDEAETDCDEAET5-4/328/3-4/320/355-4/328/3-4/320/353DE-4/316/35-4/332/35DCAETDE-4/316/35-4/332/35DCAET46/5410-4/345DCEAAET6/5410-4/345DCEAAET5DE4/3125-11510BADE4/3125-11510BA1410BAEA6/526/510AET1410BAEA6/526/510AET-1-1BAEA6/532/510AET-11310BAEA6/532/510AET-113107EA6/538/510AET-11210BAEA6/538/510AET-11210BA810AET-11110BAEA44/56/510AET-11110BAEA44/56/591010BAEA6/51010AET-11010BAEA6/51010AET-110具体编程实现如下：第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};template<classT>structEnode{ 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表中结点的结构体template<classT>classET{ public: ET(intmSize); ~ET(); ResultCodeInsert(intu,Tymax,floatxi,floatm); intn;//覆盖该多边形的扫描线的总数，从0开始计数 Enode<T>**a;};//定义了边表类template<classT>ET<T>::ET(intmSize){ n=mSize; a=newEnode<T>*[n];for(inti=0;i<n;i++)a[i]=0;}//ET边表的初始化template<classT>ET<T>::~ET(){ Enode<T>*p,*q; deletea[0];for(inti=1;i<n;i++) { p=a[i];q=p; while(p) { p=p->next; deleteq; q=p; } } delete[]a;}//析构函数负责回收内存空间template<classT>ResultCodeET<T>::Insert(intu,Tymax,floatxi,floatm){ if(u<0||u>n-1)returnFailure; Enode<T>*p=newEnode<T>(ymax,xi,m,a[u]); a[u]=p; returnSuccess;}//依次插入结点构建出边表，其中a[1]到a[10]用于构建ET边表//a[0]用于构建活动AET边表(2)填充函数po_fill的实现和主函数的实现#include"base_class.h"#include"graphics.h"#include<iostream.h>voidpo_fill(ET<int>&etp,intep,intcolor)//多边形填充函数的实现{inti=1;//i作为控制变量标识扫描线 while(i<ep-1){ if(etp.a[i]!=NULL) { Enode<int>*p,*r; p=etp.a[i]; r=etp.a[0]; while(p) { Enode<int>*q=newEnode<int>(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->xi>q->xi){etp.a[0]=q;q->next=r;} else{ while(q->xi>r->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表中 Enode<int>*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) { Enode<int>*w; ints=1; while(s) { Enode<int>*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]) { Enode<int>*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用于标识填充颜色ET<int>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的取值为分数(浮点型)，这就导致像素点坐标值出现浮点型，这样经过取整运算，计算出来的像素点坐标值将可能与多边形填充点真实值之间存在偏差，导致所绘制的图形不完全与实际吻合。14.已知多边形各顶点坐标为(2,2)(2,4)(8,6)(12,2)(8,1)(6,2)及(2,2)，在用多边形区域填充时，请写出ET及全部AET内容。解：如图所示：P3PP3P1P2P6P5P4则该多边形的ET表为：662623P2P34612-1612-1P4P3420P1P22284284P5P428-2P5P61该多边形的AET指针的内容为：(每条扫描线均有3行指针链，第1行表示将ET表加入AET中，第2行表示从AET表中删去yi=ymax，第3行表示xi=xi+1/m后，学生只要写出第2行即可)28-228-2P5P6284P5P4AET1284284P5P428-2P5P6AET26-226-2P5P6AET2124P5P426-226-2P5P6420P1P2AET22122124P5P4612-1P4P3420P1P2420P1P2AET612-1P4P3AETAET420P1P2611-1P4P3611-1611-1P4P3420P1P2AET3AETAET420P1P2611-1P4P3AETAET420P1P2610-1P4P3610-1P4P3610-1P4P3AET623P2P3420P1P24610-1610-1P4P3623P2P3AET69-169-1P4P3653P2P3AET653653P2P369-1P4P3AET569-1P4P369-1P4P3653P2P3AETAETAET683P2P368-1P4P368-168-1P4P3683P2P3AET615.用扫描线种子填充算法，编写一个填充多边形区域的程序。BDEHFCGA该测试多边形的各个端点坐标分别为：BDEHFCGAA(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回车一定要在中间用逗号隔开噢，输完最后一个点后，屏幕上会依次画出各条边，最后填充满程序还不完善，比如颜色值应该用变量表示以易于修改，画多边形和求种子点应该做成独立的函数等等，以后再做上吧，这是细节的问题扫描的次序：先上后下进栈的次序：先右后左测试数据：第一个多边形：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<graphics.h>#include<stdio.h>#include<dos.h>#include<conio.h>#include<stdlib.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);//将该点置色 x0=x+1;//取种子右边的像素 while(getpixel(x0,y)!=4)//fillright填充右边像素 { putpixel(x0,y,4); x0=x0+1; } xr=x0-1;//记录最右值 xrold=xr;//再记录一次最右值，以备后用 x0=x-1;//取种子左边的像素 while(getpixel(x0,y)!=4)//fillleft填充左边像素 { putpixel(x0,y,4); x0=x0-1; } xl=x0+1;//记录最左值 xlold=xl;//再记录一次最左值，以备后用 y0=y+1;//goup向上移一条扫描线 go2=0;//go2也只是一个用来标记的变量 while(xr>xl&&go==0)//查找上一条线的最右值,并记录为xr { if(getpixel(xr,y0)==4)//看看上一条扫描线最右值是否超出了当前扫描线的坐标范围 xr=xr-1;//如果超出，则减1 else go=1;//若go=1这句执行的话就说明找到了最右值，并在while中的go==0中判断并退出while } while(xl<xr&&go2==0)//查找上一条线的最左值，并记录为xl { if(getpixel(xl,y0)==4)//看看上一条扫描线最左值是否超出了当前扫描线的坐标范围 xl=xl+1;//如果超出，则加1 else go2=1;//go2=1这句执行就说明找到了最左值，并在此while中的go2==0中退出while } if(go==1&&go2==1)//如果找到了最左值和最右值，则执行下面的语句 { push(xr,y0);//先将上一条线上的最右点作为种子点入栈 for(i=xl;i<xr;i++)//从最左到最右循环，在每个连续区间上找一个种子点入栈 { if(getpixel(i,y0)!=4)//如果不是边界点，什么也不做 {}//这样做的目的是如果出现ooBBooBBoooBooo的情况，其中o是未填充的点，B是边界点 elseif(getpixel(i-1,y0)!=4)//如果是边界点，则看它左边的点是不是边界点，如果不是，则入栈 { push(i-1,y0);//实际入栈的是最靠近边界点的右像素 } } } y0=y-1;//godown向下移一条扫描线 go=0; go2=0; xl=xlold;//还原最左，最右 xr=xrold; while(xr>xl&&go==0)//找下一条扫描线的最右像素 { if(getpixel(xr,y0)!=4) go=1; else xr--; } while(xl<xr&&go2==0)//找下一条扫描线的最左像素 { if(getpixel(xl,y0)!=4) go2=1; else xl++; } if(go==1&&go2==1)//如果找到最左和最右，则执行 { push(xr,y0); for(i=xl;i<=xr;i++) { if(getpixel(i,y0)!=4) {} elseif(getpixel(i-1,y0)!=4) { push(i-1,y0); } } } }}voidmain(){ voidfill(intx,inty); intgdriver,gmode;/*显示模式*/ detectgraph(&gdriver,&gmode); initgraph(&gdriver,&gmode,""); inti,j; intn,u,px,py,px0,py0,px1,py1; intya=0,yi=getmaxy(); printf("pleasinputthenumberofthepolygons:"); scanf("%d",&u);//看看究竟有多少个多边形(可能多边形里包含了多边形) for(intk=0;k<u;k++) { printf("pleasinputthenumberofthetoppoints:"); scanf("%d",&n);//看看该多边形究竟有几个端点 for(i=0;i<n;i++)//从键盘接受各顶点的坐标，依次入栈，并记录最大Y值和最小Y值 { printf("pleaseinputthecoordinateofthepoints--like:100,200:"); scanf("%d,%d",&px,&py); if(ya<py) ya=py;//ya是最大Y值 if(yi>py) yi=py;//yi是最小Y值 push(px,py); } setbkcolor(0); //cleardevice(); setcolor(4); pop(px0,py0);//输入的最后一个顶点出栈 px=px0; py=py0;//记录最后一个顶点 //drawtheplot while(stack!=0) { pop(px1,py1); line(px0,py0,px1,py1); px0=px1; py0=py1; delay(500);//时延，慢慢画 } line(px0,py0,px,py);//依次画线，画出多边形 } //画完多边形后，栈为空 //findtheyvalue j=