实验3区域填充算法答案

实验三区域填充算法的实现一、实验目的和要求：1、掌握区域填充算法基本知识2、理解区域的表示和类型，能正确区分四连通和八连通的区域3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0或win-TC实现区域种子填充的递归算法。

二、实验内容：1、编程完成区域填色2、利用画线函数，在屏幕上定义一个封闭区域。

3、利用以下两种种子填充算法，填充上述步骤中定义的区域(1)边界表示的四连通区域种子填充的实现(2)内点表示的四连通区域种子填充的实现4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法，并编程实现。

三、实验结果分析四连通图的实现:程序代码：#include<graphics.h>#include <conio.h>#include<math.h>#include<time.h>void BoundaryFill4(int x,int y,int Boundarycolor,int newcolor){if(getpixel(x,y) != newcolor && getpixel(x,y) !=Boundarycolor){putpixel(x,y,newcolor);Sleep(1);BoundaryFill4(x-1,y,Boundarycolor,newcolor);BoundaryFill4(x,y+1,Boundarycolor,newcolor);BoundaryFill4(x+1,y,Boundarycolor,newcolor);BoundaryFill4(x,y-1,Boundarycolor,newcolor);}}void polygon(int x0,int y0,int a,int n,float af){int x,y,i;double dtheta,theta;if(n<3)return;dtheta=6.28318/n;theta=af*0.0174533;moveto(x0,y0);x=x0;y=y0;for(i=1;i<n;i++){x=x+a*cos(theta);y=y+a*sin(theta);lineto(x,y);theta=theta+dtheta;}lineto(x0,y0);}void main(){int x=50,y=75;int a,b,c,d,i,j;int graphdriver=DETECT;int graphmode=0;initgraph(&graphdriver,&graphmode," ");cleardevice();setcolor(RGB(0,255,0));setfillstyle(WHITE);polygon(x,y,60,5,0.);a=100;b=100;c=RGB(0,255,0);d=RGB(255,0,255);BoundaryFill4(a,b,c,d);getch();closegraph();｝实验结果八连通的实现程序代码：#include<graphics.h>#include<conio.h>#include<time.h>#include <malloc.h>#include <windows.h>#define MaxSize 100typedef struct{int x;int y;}Seed,ElemType;typedef struct{ElemType data[MaxSize];int top; //栈顶指针} SqStack;void InitStack(SqStack *&s){s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}int StackEmpty(SqStack *s){return(s->top==-1);}int Push(SqStack *&s,ElemType e){if (s->top==MaxSize-1)return 0;s->top++;s->data[s->top]=e;return 1;}int Pop(SqStack *&s,ElemType &e){if (s->top==-1)return 0;e=s->data[s->top];s->top--;return 1;}void floodfill8(int x,int y,int oldcolor,int newcolor) {if(getpixel(x,y)==oldcolor){putpixel(x,y,newcolor);Sleep(2);floodfill8(x,y+1,oldcolor,newcolor);floodfill8(x,y-1,oldcolor,newcolor);floodfill8(x-1,y,oldcolor,newcolor);floodfill8(x+1,y,oldcolor,newcolor);floodfill8(x+1,y+1,oldcolor,newcolor);floodfill8(x+1,y-1,oldcolor,newcolor);floodfill8(x-1,y+1,oldcolor,newcolor);floodfill8(x-1,y-1,oldcolor,newcolor);}}void main(){int a,b,c,d,i,j;int graphdriver=DETECT;int graphmode=0;initgraph(&graphdriver,&graphmode," "); cleardevice();setfillstyle(RGB(255,255,255));setcolor(GREEN);int points[]={320,200,270,290,370,290}; fillpoly(3,points);rectangle(500,420,100,100);a=RGB(255,255,255);b=RGB(255,0,0);floodfill8(320,240,a,b);c=RGB(0,0,0);d=RGB(0,0,255);floodfill8(320,180,c,d);getch();closegraph();}实验结果:2、结果分析：通过以上各算法运行结果分析与对比可知：1．四连通算法的缺点是有时不能通过狭窄区域，因而不能填满多边形。

实验三区域填充原理实验目的掌握二维区域填充的填充算法；实验环境计算机、Turbo C、C++等其他语言程序设计环境实验学时2学时，必做实验。

实验内容1．二维封闭区域的种子填充算法和扫描线种子填充算法；2．熟悉多边形扫描线填充算法；内点表示四连通种子填充算法（漫水法）参考代码：#include<graphics.h>void floodfill4(int x,int y,int oldcolor,int newcolor){if(getpixel(x,y)==oldcolor){putpixel(x,y,newcolor);delay(20000);floodfill4(x,y+1,oldcolor,newcolor);floodfill4(x,y-1,oldcolor,newcolor);floodfill4(x-1,y,oldcolor,newcolor);floodfill4(x+1,y,oldcolor,newcolor);}}main(){int a,b,c,d,i,j;int graphdriver=DETECT, graphmode=0;initgraph(&graphdriver,&graphmode," ");cleardevice();setcolor(14);rectangle(100,100,150,150);for(i=101;i<150;i++)for(j=101;j<150;j++){ putpixel(i,j,4);delay(1000);}a=120; b=110; c=4; d=2;floodfill4(a,b,c,d);getch();closegraph();}边界表示的4连通区域的种子填充算法:#include<stdio.h>;#include<graphics.h>;void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) {if(getpixel(x,y)!=boundarycolor&getpixel(x,y)!=newcolor) {putpixel(x,y,newcolor);delay(20000);BoundaryFill4(x,y+1,boundarycolor,newcolor);BoundaryFill4(x,y-1,boundarycolor,newcolor);BoundaryFill4(x-1,y,boundarycolor,newcolor);BoundaryFill4(x+1,y,boundarycolor,newcolor);}}main() {int a,b,c=14,d,i,j;int graphdriver=DETECT,graphmode=0;initgraph(&graphdriver,&graphmode," ");cleardevice();setcolor(c);rectangle(100,100,150,150);for(i=101;i<150;i++)for(j=101;j<150;j++) { putpixel(i,j,4); delay(1000); } a=120; b=130; d=2;BoundaryFill4(a,b,c,d);getch();closegraph();}扫描线种子填充算法参考代码：#include<graphics.h>#include<stdio.h>#include<stdlib.h>#define bordercolor 15#define backcolor 0#define seedcolor 4#define fillcolor 10typedef struct Point{int x;int y;}point;typedef struct Stack{point *base;point *top;}*stack;void initstack(stack s){(*s).base=(point*)malloc(sizeof(point));if(!(*s).base)exit(1);(*s).top=(*s).base;}void push(stack s,point p){*((*s).top)=p;(*s).top++;}int stackempty(stack s){if((*s).top==(*s).base)return(1);else return(0);}point pop(stack s){(*s).top--;return(*((*s).top));}void drawgraphics(){int a[10]={100,140,260,80,300,200,160,240,100,140}; drawpoly(5, a);/*circle(200,200,150);*/}point produceseed(){point p;p.x=200;p.y=200;return(p);}void intostack(stack s,int y0,int xl,int xr){int x,y;point tm;for(x=xl,y=y0;x<=xr&&x<getmaxx();x++){if((x!=xr&&getpixel(x,y)==backcolor&&getpixel(x+1,y)!=backcolor)||(x==xr&&getpixel(x,y)==backcolor)){tm.x=x;tm.y=y;push(s,tm);putpixel(x,y,seedcolor);}if(x==xr&&getpixel(x,y)==backcolor)break;}}void fillgraphics(){int xl=0,xr=getmaxx(),x,y;point seed;stack s=NULL;seed=produceseed();putpixel(seed.x,seed.y,seedcolor);getch();initstack(s);push(s,seed);while(!stackempty(s)){seed=pop(s);for(x=seed.x,y=seed.y;getpixel(x,y)==backcolor||getpixel(x,y)==seedcolor;x++) {putpixel(x,y,fillcolor);}xr=x-1;for(x=seed.x-1,y=seed.y;getpixel(x,y)==backcolor||getpixel(x,y)==seedcolor;x--) {putpixel(x,y,fillcolor);}xl=x+1;intostack(s,seed.y+1,xl,xr);intostack(s,seed.y-1,xl,xr);getch();}}void main(){int gdriver ,gmode ;gdriver = DETECT;initgraph(&gdriver , &gmode ,"" );drawgraphics();fillgraphics();outtextxy(180,20,"Scan line filling graphics finished!"); getch();closegraph();}多边形扫描线填充算法参考代码：/* Note:扫描线填充算法*/#include <graphics.h>#include <conio.h>#include <math.h>#define MAXPOINT 20typedef struct {int y_top;float x_int;int delta_y;float x_cps;}E_ENTRY;void putin_sl(int entry,int x1,int y1,int x2,int y2,int next_y); void sortonby(int n);void updatefl(int count,int scan);void swap(E_ENTRY *x,E_ENTRY *y);void sortonx(int entry,int first_s);void processx(int first_s,int last_s);void drawline(int scan,int x_int_c,int index);void updatesl();E_ENTRY sides[MAXPOINT];int x[MAXPOINT]={0,210,240,230,350,380,340,200,180,150}; int y[MAXPOINT]={0,410,370,200,410,340,140,180,120,300}; int s_count,first_s,last_s,scan,bottom_s,x_int_c;main(){int driver,mode;int v_count=9;driver=DETECT;initgraph(&driver,&mode,"");setcolor(3);fillarea(v_count,x,y);getch();closegraph();}fillarea(int count){sortonby(count);first_s=1;last_s=1;for(scan=sides[1].y_top;scan>bottom_s;scan--){updatefl(count,scan);processx(first_s,last_s);drawline(scan,x_int_c,first_s);updatesl();}}void putin_sl(int entry,int x1,int y1,int x2,int y2,int next_y) {int maxy;float x2_temp,xch_temp;xch_temp=(float)(x2-x1)/(float)(y2-y1);x2_temp=x2;if((y2>y1)&&(y2<next_y)){y2--;x2_temp-=xch_temp;}else{if((y2<y1)&&(y2>next_y)){y2++;x2_temp+=xch_temp;}}maxy=(y1>y2)?y1:y2;while((entry>1)&&(maxy>sides[entry-1].y_top)){sides[entry]=sides[entry-1];entry--;}sides[entry].y_top=maxy;sides[entry].delta_y=abs(y2-y1)+1;if(y1>y2)sides[entry].x_int=x1;elsesides[entry].x_int=x2_temp;sides[entry].x_cps=xch_temp;}void sortonby(int n){int k,x1,y1;s_count=0;y1=y[n];x1=x[n];bottom_s=y[n];for(k=1;k<n+1;k++){if(y1!=y[k]){s_count++;putin_sl(s_count,x1,y1,x[k],y[k],y[k+1]);}else{/* line((short)x1,480-(short)y1,(short)x[k],480-(short)y1);*/moveto((short)x1,480-(short)y1);lineto((short)x[k],480-(short)y1);}if(y[k]<bottom_s) bottom_s=y[k];y1=y[k];x1=x[k];}}void updatefl(int count,int scan){while((sides[last_s+1].y_top>scan)&&(last_s<count))last_s++;while(sides[first_s].delta_y==0) first_s++;}void swap(E_ENTRY *x,E_ENTRY *y){int i_temp;float f_temp;i_temp=x->y_top;x->y_top=y->y_top;y->y_top=i_temp;f_temp=x->x_int;x->x_int=y->x_int;y->x_int=f_temp;i_temp=x->delta_y;x->delta_y=y->delta_y;y->delta_y=i_temp;f_temp=x->x_cps;x->x_cps=y->x_cps;y->x_cps=f_temp;}void sortonx(int entry,int first_s){while((entry>first_s)&&(sides[entry].x_int<sides[entry-1].x_int)) {swap(&sides[entry],&sides[entry-1]);entry--;}}void processx(int first_s,int last_s){int k;x_int_c=0;for(k=first_s;k<last_s+1;k++){if(sides[k].delta_y>0){x_int_c++;sortonx(k,first_s);}}}void drawline(int scan,int x_int_c,int index){int k,x,x1,x2;for(k=1;k<(int)(x_int_c/2+1.5);k++){while(sides[index].delta_y==0)index++;x1=(int)(sides[index].x_int+0.5);index++;while(sides[index].delta_y==0)index++;x2=(int)(sides[index].x_int+0.5);/*line((short)x1,480-(short)scan,(short)x2,480-(short)scan);*/ moveto((short)x1,480-(short)scan);lineto((short)x2,480-(short)scan);index++;}}void updatesl(){int k;for(k=first_s;k<last_s+1;k++){if(sides[k].delta_y>0){sides[k].delta_y--;sides[k].x_int-=sides[k].x_cps;}}}。

试验实验一:图形的区域填充一、实验目的区域填充是指先将区域内的一点（常称为种子点）赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。

区域填充技术广泛应用于交互式图形、动画和美术画的计算机辅助制作中。

本实验采用递归填充算法或打描线算法实现对光栅图形的区域填充。

通过本实验，可以掌握光栅图形编程的基本原理和方法。

实验内容掌握光栅图形的表示方法，实现种子算法或扫描线算法。

通过程序设计实现上述算法。

建议采用VC++实现OpenGL程序设计。

三、实验原理、方法和手段递归算法在要填充的区域内取一点（X, Y）的当前颜色记为oldcoloo用要填充的颜色ne wcolor去取代，递归函数如下：procedure flood-fill（XXoldcoloLnewcolor:integer）; beginif getpixel（fiainebufier,x,y）=oldcolorthen beginsetpixel（fiamebuffer,x,y,newcolor）; flood-fill（X.Y+1 .oldcoloLiiewcolor）;flood-fill（X.Y^ 1 ,oldcoloi;newcolor）; flood-fill（X-l,Y；oldcoloi;newcolor）; flood-fill（X+l,Yoldcoloi;newcolor）;endend扫描线算法扫描线算法的效率明显高于递归算法，其算法的基本思想如下：（1）（初始化）将算法设置的堆栈置为空，将给定的种子点（x,y）压入堆栈。

（2）（出栈）如果堆栈为空，算法结束；否则取栈顶元素（x,y）作为种子点。

（3）（区段填充）从种子点（x,y）开始沿纵坐标为y的当前扫描线向左右两个方向逐个象素进行填色，其值置为newcoloi;直到抵达边界为止。

（4）（定范围）以XleA和Xn血分别表示在步骤3中填充的区段两端点的横坐标。

（5）（进栈）分别在与当前扫描线相邻的上下两条打描线上，确定位于区间［Xldb Xn 曲］内的给定区域的区段。

计算机图形学实验二维填充图的生成1. 图元填充利用多种图元填充的方法绘制一面五星红旗。

方法有: 扫描转换多边形的逐点判断法（编码算法）, 扫描线算法, 区域填充的扫描线算法, 自创的向内复制边法。

1.1说明:1.1.1 宏定义和类型定义:#define max 400#define pi 3.14159265#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define false 0#define true 1#define ok 1#define error 0#define infeasible -1#define overflow -2typedef int Status;typedef int bool;typedef struct {int y,xLeft,xRight;}SElemType;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;typedef struct Edge{int ymax;float x,deltax;struct Edge *nextEdge;}Edge;Edge *EL[max];typedef struct{float x,y;}point;Status SetStackEmpty(SqStack *s){s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s->base) return overflow;s->top=s->base;s->stacksize=STACK_INIT_SIZE;return ok;}Status PushStack(SqStack *s,SElemType e){if(s->top-s->base>=s->stacksize){s->base=(SElemType*)(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s->base) return error;s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*s->top++=e;return ok;}Status PopStack(SqStack *s,SElemType *e){ if(s->top==s->base) return error;*e=*(--s->top);return ok;}Status IsStackEmpty(SqStack *s){if(s->base==s->top) return true;else return false;}1.1.2其他由于要填充五角星, 我们就要得到五角星的十个顶点。

计算机图形学四连通区域种子填充算法实验————————————————————————————————作者: ————————————————————————————————日期:ﻩ《计算机图形学实验》报告任课教师:钱文华2０16年春季学期实验:四连通区域种子填充算法实验时间：201６年12月8日实验地点：信息学院22０4实验目的：掌握种子填充算法的原理，并会用种子填充算法和opｅｎｇl并结合使用ｃ+＋语言编写程序绘制多边形。

实验原理:种子填充算法又称为边界填充算法。

其基本思想是:从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。

如果边界是以一种颜色指定的,则种子填充算法可逐个像素地处理直到遇到边界颜色为止。

内点的检测条件：ｉf(iｎｔerｉoｒCｏloｒ!=bo ｒｄerCoｌor&&interｉorColoｒ!＝ｆiｌlCｏlｏr）。

种子填充算法常用四连通域和八连通域技术进行填充操作。

从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。

用这种方法填充的区域就称为四连通域;这种填充方法称为四向连通算法。

从区域内任意一点出发,通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。

用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

一般来说，八向连通算法可以填充四向连通区域,而四向连通算法有时不能填充八向连通区域。

四向连通填充算法:a）种子像素压入栈中;b)如果栈为空,则转e）；否则转c）;c) 弹出一个像素,并将该像素置成填充色;并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是,则将该像素压入栈;d)转b）;ｅ）结束。

四连通填充算法利用到了递归的思想。

本实验只包括四连通填充算法程序代码:#ｉncludｅ<ｇlut.h>＃ｉｎｃlｕde<ｓtdｌib．h>＃ｉncｌudｅ<math．h>#include<ｗindowｓ.h＞voidｉniｔ（vｏid）{ glCｌearColor(１．０，１.0,1．0,0.０）；glMatrixMoｄｅ（ＧL_PROJＥCTION）;gｌｕOrtho２D（０．0，30０．0，０.0,30０.0);}voｉd setPixel(inｔx，ｉnｔy,lｏｎｇｆillCoｌor）{ ｇlColor3f（fｉllCoｌoｒ<<16,filｌCoｌor<<８,fillCｏloｒ)；ｇlＢｅgin（ＧL_ＰＯINTＳ);ｇlＶｅｒteｘ2i（x,y）;ｇlEnｄ();}ｖｏｉｄboundaryFill４(iｎt x,ｉnｔy,lｏng fillＣolor,lｏng bordeｒColor）{ unｓｉgneｄchａr paｒams[3];loｎg interioｒCoｌoｒ;glRｅaｄPixels(ｘ，y,1,1,GL_RGB,GＬ＿UNSIＧNＥD_BYＴE,par ａms）;interiorCoｌoｒ=RGB(paraｍs[0],ｐarａms[１］,paｒaｍs[2])；ｉf(inteｒiorＣolor!=boｒderCｏloｒ＆＆inteｒiｏrCoｌｏr!=filｌColor){ setＰixeｌ(x，ｙ,fｉｌlCoｌｏr);ｂoundaryFill4（x＋1,y,filｌＣoｌｏr,ｂordeｒCｏlor);ｂｏunｄaｒyＦｉｌl4(ｘ-1，y，fiｌlＣolor,borderColor); boundaryFilｌ４(x,ｙ+1,ｆｉlｌColｏr,borｄeｒCoｌor)；ｂounｄarｙFill4(x，y-1，ｆｉllColｏr，ｂorｄerＣolor);} }voiｄlineＳegment(voｉd) {long bｏrｄerCｏｌoｒ=RGB（255，0,０);lｏngｆiｌlColoｒ=RGB（０，0，255）;glClｅar（ＧL_COＬOR＿BUFFER_BIT); glCｏloｒ３ｆ(２55，0,0); ｇlＢegｉn（GL_ＬINE＿ＬＯＯP);glVeｒtex2ｉ(0,４0);glVｅｒteｘ2i(2０,0);glＶertex２i(６0,0）；glＶeｒtｅx2ｉ(80，4０）;ｇlVｅｒtex2i(６0,80);gｌVertex２i(20,80);gｌＥnd();boundaryＦill4(６０,60，ｆｉllＣolor,ｂorderColｏr)；gｌFlush()；}voｉｄmain(ｉｎt argc,chａr＊*aｒgv）｛ｇlutIｎｉｔ(&ａr ｇc,aｒｇv);glｕtInitDｉsｐｌaｙMode(GLUＴ＿ＳＩNGLE｜GLUT_ＲGB); glutInitＷindowPｏsiｔion（1５0,10０）;gluｔIｎitWinｄoｗSizｅ(300,３0０）;glutＣreateＷｉｎdow（"种子填充"）；init();glutDisｐlayFｕｎｃ(lｉneＳegｍeｎt);gｌｕtMａinＬｏoｐ(）;}上实验课时机房的实验结果:后来的实验结果:glVｅrteｘ2i（0,40);gｌＶerteｘ２i（20，0);glVerｔex2i（60,０);glVerteｘ2i（８0，４０);gｌＶertｅx2ｉ(60，80);ｇlＶerteｘ2i(２0,80)；ｇlEnｄ();ｂｏｕndaryFｉlｌ4(60,60，ｆｉlｌCｏlor,ｂorderＣoｌor）；以上这段程序改成如下glVerｔex2ｉ(９0，40);glVｅrtｅx２i（１2０, １00）;ｇlVertex2i(90,1６0);glVertｅｘ２i(60, 160);ｇlVertex2i(60, ４０);glEnd()；bouｎｄaryFilｌ4(７0,6０,fiｌｌCｏｌoｒ,bｏｒderCoｌor); 改变参数后：再把ｇlVeｒｔｅx2i（9０，40);glVertｅｘ２i(120, 100）；glＶｅrｔex2i(90,160）;glＶerｔex2i(60, １6０）;glVｅrtex２i（６0, 40）;gｌＥnd（);bｏundaryFill4（70,6０,fiｌlCｏloｒ,boｒdｅrCｏlor）；改成glVeｒtex2i(100, １０0)；glVｅrteｘ2i(２00, 100);gｌVｅｒteｘ2ｉ(1５0,150);/／glVｅrteｘ2ｉ(60, 1６0);／/glVertｅx2i(6０, 40)；glＥnd();ｂoundaryFill4(150，1２0,fiｌlCｏlor，borｄerCoｌoｒ);后的结果如下图:实验总结:通过多组数据的测试，知道了上面算法的正确,普适性。

计算机图形学——区域填充的扫描线算法一．实验名称：区域填充的扫描线算法二．实验目的：1、理解区域填充扫描线算法的原理；2、实现区域填充的扫描线算法并测试；三．算法原理：算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。

随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。

借助于栈结构，区域填充的扫描线算法之步骤如下：Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈；Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点；Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。

分别以xl 和xr 表示该填充区段两端点的横坐标；Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条扫描线上位于区段[xl, xr] 内的区域内的区段。

若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。

四．原程序代码：/*****************************************//*4-ScanLineFill 区域填充的扫描线算法实现*//*****************************************/#include <stdio.h>#include <conio.h>#include <graphics.h>#include <malloc.h>#define Stack_Size 100 //栈的大小常量//定义结构体,记录种子点typedef struct{int x;int y;}Seed;//定义顺序栈(种子点)typedef struct{Seed Point[Stack_Size];int top;}SeqStack;//初始化栈操作void InitStack(SeqStack *&S){S=(SeqStack *)malloc(sizeof(SeqStack));S->top=-1;}//种子点栈置空；void setstackempty (SeqStack *S){S->top==-1;}//种子点栈状态检测函数int isstackempty (SeqStack *S){if(S->top==-1)return true; //空栈返回trueelsereturn false; //非空栈返回false}//种子点入栈；int stackpush (SeqStack *&S,Seed point){if(S->top==Stack_Size-1)//栈已满，返回false return false;S->top++;//栈未满，栈顶元素加1S->Point[S->top]= point;return true;}//取栈顶元素；int stackpop (SeqStack *&S,Seed &point){if(S->top==-1)//栈为空，返回falsereturn false;point=S->Point[S->top];S->top --;//栈未空，top减1return true;}//画圆void CirclePoints (int xc, int yc, int x, int y, int Color) {putpixel (xc + x, yc + y, Color);putpixel (xc + x, yc - y, Color);putpixel (xc - x, yc + y, Color);putpixel (xc - x, yc - y, Color);putpixel (xc + y, yc + x, Color);putpixel (xc + y, yc - x, Color);putpixel (xc - y, yc + x, Color);putpixel (xc - y, yc - x, Color); }//中点画圆算法void MidpointCircle(int radius, int Color) {int x, y;float d;x=0;y=radius;d=5.0/4-radius;CirclePoints(250,250,x,y,Color);while(x<y){if (d<0){d+=x*2.0+3;}else{d+=(x-y)*2.0+5;y--;}x++;CirclePoints(250,250,x,y,Color);}}//四连通扫描线算法void ScanLineFill4(int x, int y, int oldcolor, int newcolor) {int xl, xr, i;bool SpanNeedFill;Seed pt;//种子点SeqStack *S;//定义顺序栈InitStack(S);//定义了栈之后必须把栈先初始化setstackempty(S);//种子点栈置空；pt.x = x;pt.y = y;stackpush (S,pt); // 种子点(x, y)入栈while (!isstackempty(S)){stackpop (S,pt);//取种子点y = pt.y;x = pt.x;while (getpixel (x,y)==oldcolor) {// 从种子点开始向右填充putpixel (x, y, newcolor);x++;}xr = x -1;x = pt.x -1;while (getpixel (x,y)==oldcolor) { // 从种子点开始向左填充putpixel (x, y, newcolor);x--;}xl = x + 1;x = xl;y = y +1; // 处理上面一条扫描线while (x < xr){SpanNeedFill = false;while (getpixel (x, y)==oldcolor){SpanNeedFill = true;x++ ;} // 待填充区段搜索完毕if (SpanNeedFill){// 将右端点作为种子点入栈pt.x = x - 1;pt.y = y;stackpush (S,pt);SpanNeedFill = false;} //继续向右检查以防遗漏while ((getpixel (x, y)!=oldcolor) && (x< xr)) x++;} //上一条扫描线上检查完毕x = xl;y=y-2; // 处理下面一条扫描线while (x < xr){SpanNeedFill = false;while (getpixel (x, y)==oldcolor){SpanNeedFill=true;x++ ;}if (SpanNeedFill){pt.x= x - 1;pt.y = y;stackpush (S,pt);SpanNeedFill=false;}while ((getpixel (x, y)!=oldcolor) && (x < xr))x++;}}}//主函数检测void main(){int radius,color;int x,y;//种子点int oldcolor,newcolor;//原色与填充色//输入参数值printf("input radius and color:\n");//画圆参数scanf("%d,%d",&radius,&color);printf("input x and y:\n"); //读入内点scanf("%d,%d", &x, &y);printf("input oldcolor and newcolor:\n"); //读入原色与填充色scanf("%d,%d", &oldcolor, &newcolor);int gdriver = DETECT,gmode;initgraph(&gdriver, &gmode, "c:\\tc");// 用背景色清空屏幕cleardevice();// 设置绘图色为红色setcolor(RED);MidpointCircle(radius,color);//用中点画圆算法画圆rectangle(150, 150, 350, 350);//再画一个矩形区域ScanLineFill4 (x,y,oldcolor,newcolor);//扫描线区域填充getch();closegraph();}五．运行结果与讨论：测试结果1：测试结果2：六．实验分析与讨论：1.通过借助栈这一数据结构，完成了区域填充的扫描线算法的实现，并利用以前所学的画圆等算法，进行综合运用，在此基础上进行扩充，设计多种图案，进行扫描线填充算法的检测，都得到了理想的结果，体现了算法的有效性；2.栈的数据结构给种子点的操作带来了极大的方便，为算法的实现提供了便利，同时还提高了算法的复用性和可靠性；3.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。

任课教师：李陶深教授tshli@12直线生成算法圆与椭圆的绘制算法5图元的概念436区域填充算法裁剪反走样技术4.4 区域填充算法4.4 区域填充算法—基础知识（3）线框多边形物体:只需扫描转换线段填充多边形物体:要扫描转换多边形本质：点阵表示。

特点：面着色，画面明暗自然、色彩丰富。

4.4 区域填充算法4.4 区域填充算法—基础知识（4）图形学中多边形的两种表示方式顶点表示：用多边形的有序顶点序列表示多边形点阵表示：用位于多边形内部的像素集合来表示多边形4.4 区域填充算法多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。

形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。

概括地说，该算法先画边界，然后对内定义区域填充。

所以，它一般只能用于人机交互填色，而难以用于程序填色。

4.4 区域填充算法—多边形填色算法的问题多边形填色算法面临的一个首要问题，是判断一个像素是在多边形内还是多边形外。

Question1: How to Judge…?Question2: How to improve …?图4.14 射线法图4.15 转角法4.4 区域填充算法4.4 区域填充算法4.4 区域填充算法4.4 区域填充算法4.4 区域填充算法大量的求交、乘除运算4.4 区域填充算法—扫描线填色算法（1）基本思路：扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。

该算法利用了扫描线的连续性和边的连续性，避免对像素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。

具体处理过程：先求出扫描线与多边形边的交点，利用扫描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所有扫描线由上到下依次处理。

4.4 区域填充算法—扫描线填色算法（2） 算法实现的步骤：对每一条扫描线执行如下四步:(1) 求交：求扫描线与多边形各边的交点;(2) 排序：将求得的交点按递增顺序进行排序;(3) 交点配对：确定相交区间;(4) 区间填色：将相交区间内的像素置成多边形色, 相交区间外的像素置成背景色。

实验三区域填充扫描线算法区域填充扫描线算法是一种计算机图形学算法，用于实现区域填充功能。

该算法通过扫描像素的方式，检测封闭区域内的每一条扫描线与区域边界的交点，并根据交点之间的像素颜色进行填充。

算法步骤如下：1.扫描线从画布的最底部开始，逐行向上移动。

2.检测扫描线与区域边界的交点，并记录交点的x坐标。

3.对于每对相邻的交点（称为活动边），按照交点的x坐标从左到右进行遍历。

4.遍历过程中，判断当前像素是否在封闭区域内。

如果在区域内，根据填充颜色进行颜色填充。

5.对于扫描线上的下一条扫描线，根据当前扫描线的活动边情况，更新活动边，即将下一条扫描线上的新交点加入到活动边中。

区域填充扫描线算法的优点在于其适用于任意形状的封闭区域，并且可以处理带有内部孔洞的区域。

相比其他填充算法，如扫描线填充算法，区域填充扫描线算法具有更好的效率和性能。

然而，区域填充扫描线算法也存在一些限制和问题。

首先，该算法要求区域边界是封闭的，并且必须采用逆时针顺序来定义区域内的边界。

其次，算法的实现和性能受到硬件设备的限制，特别是在处理较大尺寸的区域时可能出现性能问题。

为了解决这些问题，可以采用一些优化方法来改进算法的性能。

例如，可以使用空间填充曲线（Space Filling Curves）来加速扫描线的遍历过程。

还可以使用并行计算技术来加速算法的执行，特别是在处理大尺寸区域时。

总之，区域填充扫描线算法是一种常用的图形学算法，用于实现区域填充功能。

虽然具有一些限制和问题，但可以通过一些优化方法来改进算法的效率和性能，满足实际应用的需求。

计算机图形学四连通区域种子填充算法实验《计算机图形学实验》报告任课教师：钱文华2016年春季学期实验:四连通区域种子填充算法实验时间：2016年12月8日实验地点：信息学院2204实验目的：掌握种子填充算法的原理，并会用种子填充算法和opengl并结合使用c++语言编写程序绘制多边形。

实验原理：种子填充算法又称为边界填充算法。

其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。

如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。

内点的检测条件：if(interiorColor!=borderColor&&interiorColor!=fillColor)。

种子填充算法常用四连通域和八连通域技术进行填充操作。

从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。

用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。

从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。

用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。

四向连通填充算法：a）种子像素压入栈中；b）如果栈为空，则转e)；否则转c)；c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；d）转b）；e）结束。

四连通填充算法利用到了递归的思想。

本实验只包括四连通填充算法程序代码：#include<glut.h>#include<stdlib.h>#include<math.h>#include<windows.h>void init(void) { glClearColor(1.0,1.0,1.0,0.0);glMatrixMode(GL_PROJECTION);gluOrtho2D(0.0,300.0,0.0,300.0);}void setPixel(int x,int y,long fillColor){ glColor3f(fillColor<<16,fillColor<<8,fillColor); glBegin(GL_POINTS);glVertex2i(x,y); glEnd();}void boundaryFill4(int x,int y,long fillColor,long borderColor){ unsigned char params[3];long interiorColor;glReadPixels(x,y,1,1,GL_RGB,GL_UNSIGNED_BYTE,params); interiorColor=RGB(params[0],params[1],params[2]);if(interiorColor!=borderColor&&interiorColor!=fillColor){ setPixel(x,y,fillColor);boundaryFill4(x+1,y,fillColor,borderColor);boundaryFill4(x-1,y,fillColor,borderColor);boundaryFill4(x,y+1,fillColor,borderColor);boundaryFill4(x,y-1,fillColor,borderColor);} }void lineSegment(void) { long borderColor=RGB(255,0,0); long fillColor=RGB(0,0,255);glClear(GL_COLOR_BUFFER_BIT); glColor3f(255,0,0); glBegin(GL_LINE_LOOP);glVertex2i(0,40);glVertex2i(20,0);glVertex2i(60,0);glVertex2i(80,40);glVertex2i(60,80);glVertex2i(20,80);glEnd();boundaryFill4(60,60,fillColor,borderColor);glFlush(); }void main(int argc,char** argv) { glutInit(&argc,argv); glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); glutInitWindowPosition(150,100);glutInitWindowSize(300,300);glutCreateWindow("种子填充");init();glutDisplayFunc(lineSegment);glutMainLoop();}上实验课时机房的实验结果：后来的实验结果:glVertex2i(0,40); glVertex2i(20,0);glVertex2i(60,0);glVertex2i(80,40);glVertex2i(60,80);glVertex2i(20,80);glEnd();boundaryFill4(60,60,fillColor,borderColor); 以上这段程序改成如下glVertex2i(90, 40);glVertex2i(120, 100);glVertex2i(90, 160);glVertex2i(60, 160);glVertex2i(60, 40);glEnd();boundaryFill4(70,60,fillColor,borderColor); 改变参数后：再把glVertex2i(90, 40);glVertex2i(120, 100);glVertex2i(90, 160);glVertex2i(60, 160);glVertex2i(60, 40);glEnd();boundaryFill4(70,60,fillColor,borderColor); 改成glVertex2i(100, 100);glVertex2i(200, 100);glVertex2i(150, 150);//glVertex2i(60, 160);//glVertex2i(60, 40);glEnd();boundaryFill4(150,120,fillColor,borderColor);后的结果如下图：实验总结：通过多组数据的测试，知道了上面算法的正确，普适性。

实验题目：实验二有效边表填充算法1.实验目的：设计有效边表结点和边表结点数据结构设计有效边表填充算法编程实现有效边表填充算法2.实验描述：下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。

7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。

在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。

请使用有效边表算法填充该多边形。

图1示例多边形图2 屏幕显示多边形3.算法设计：（1）建立AET和BUCKET类；（2）初始化桶，并在建立桶结点时为其表示的扫描线初始化为带头结点的链表；（3）对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环；（4）按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按X值递增的顺序进行排序，配对，以确定填充区间；（5）用指定颜色点亮填充区间内的所有像素，即完成填充工作。

4.源程序：1)//AET.hclass AET{public:AET();virtual ~AET();double x;int yMax;double k;//代替1/kAET *next;};//AET..cppAET::AET(){}AET::~AET(){}2) //Bucket.h#include "AET.h"class Bucket{public:Bucket();virtual ~Bucket();int ScanLine;AET *p;//桶上的边表指针Bucket *next;};// Bucket.cppBucket::Bucket(){}Bucket::~Bucket(){}3)//TestView.h#include "AET.h"//包含有效边表类#include "Bucket.h"//包含桶类#define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView{。