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=