计算机图形学 区域填充算法的实现

实验四区域填充算法的实现班级 08信计2班学号 20080502088 姓名许延恒分数一、实验目的和要求：1、理解区域的表示和类型。

2、能正确区分四连通和八连通的区域3、了解区域填充的实验原理。

4、利用C++实现区域填充的递归算法。

二、实验内容：1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。

2 取（x，y）为种子点将整个区域填充为新的颜色。

3 进行递归填充。

三、实验结果分析区域填充属性包括填充样式，填充颜色和填充图案的类型。

C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充. 程序代码#include<graphics.h>#include<conio.h>#include<time.h>void floodfill4(int x,int y,int oldcolor,int newcolor){if(getpixel(x,y)==oldcolor){putpixel(x,y,newcolor);Sleep(1);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;int graphmode=0;initgraph(&graphdriver,&graphmode,"");cleardevice();setcolor(RED); rectangle(50,50,70,100); for(i=51;i<70;i++)for(j=51;j<100;j++) {putpixel(i,j,4);}a=57;b=70;c=4;d=RGB(0,255,0); floodfill4(a,b,c,d); getch();closegraph();}。

计算机图形学四连通区域种子填充算法实验————————————————————————————————作者: ————————————————————————————————日期:ﻩ《计算机图形学实验》报告任课教师:钱文华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.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。

计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念区域：指已经表⽰成点阵形式的填充图形，是象素的集合。

区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。

区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。

1、区域有两种表⽰形式1）内点表⽰：枚举出区域内部的所有象素，内部所有象素着同⼀个颜⾊，边界像素着与内部象素不同的颜⾊。

2）边界表⽰：枚举出区域外部的所有象素，边界上的所有象素着同⼀个颜⾊，内部像素着与边界象素不同的颜⾊。

21）四向连通区域：从区域上⼀点出发可通过【上、下、左、右】四个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

2）⼋向连通区域：从区域上⼀点出发可通过【上、下、左、右、左上、右上、左下、右下】⼋个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

⼆、简单种⼦填充算法给定区域G⼀种⼦点（x, y）,⾸先判断该点是否是区域内的⼀点，如果是，则将该点填充为新的颜⾊，然后将该点周围的四个点（四连通）或⼋个点（⼋连通）作为新的种⼦点进⾏同样的处理，通过这种扩散完成对整个区域的填充。

这⾥给出⼀个四连通的种⼦填充算法（区域填充递归算法），使⽤【栈结构】来实现原理算法原理如下：种⼦像素⼊栈，当【栈⾮空】时重复如下三步：这⾥给出⼋连通的种⼦填充算法的代码：void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color){if(x<w&&x>0&&y<h&&y>0){if (pixels[y*w+x]==old_color){pixels[y*w+x]== new_color);flood_fill_8(pixels, x,y+1,old_color,new_color);flood_fill_8(pixels, x,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y,old_color,new_color);flood_fill_8(pixels, x+1,y,old_color,new_color);flood_fill_8(pixels, x+1,y+1,old_color,new_color);flood_fill_8(pixels, x+1,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y+1,old_color,new_color);flood_fill_8(pixels, x-1,y-1,old_color,new_color);}}}简单种⼦填充算法的不⾜a)有些像素会多次⼊栈，降低算法效率，栈结构占空间b)递归执⾏，算法简单，但效率不⾼，区域内每⼀像素都要进/出栈，费时费内存c)改进算法，减少递归次数，提⾼效率三、扫描线种⼦填充算法基本思想从给定的种⼦点开始，填充当前扫描线上种⼦点所在的⼀区段，然后确定与这⼀段相邻的上下两条扫描线上位于区域内的区段（需要填充的区间），从这些区间上各取⼀个种⼦点依次把它们存起来，作为下次填充的种⼦点。

西安工程大学实验报告课程实验名称区第 1 页共 6 页系别组别_____________ 实验报告日期年月日姓名学号报告退发 ( 订正、重做 )E_mail:_________________________________ 教师审批评分___________________区域填充算法一、实验目的和任务1. 学习多边形填充的基于扫描线的区域填充算法2. 编程实现区域填充算法二、实验环境和设备windows系统下 vs2012 c++三、实验步骤和过程在MFC框架中通过菜单与对话框实现多边形顶点参量的输入，选择各种填充算法中的两种进行展示，其中栅栏填充和边填充算法不能同时选择，多边形的表示根据所选择的算法，以内点表示或边界表示均可四、实验故障与排除五、总结附录#include <glut.h>#include<Windows.h>const int POINTNUM = 7; //多边形点数./******定义结构体用于活性边表AET和新边表NET***********************************/ typedef struct XET{float x;float dx, ymax;XET* next;}AET, NET;/******定义点结构体point******************************************************/struct point{float x;float y;}polypoint[POINTNUM] = { 250, 50, 550, 150, 550, 400, 250, 250, 100, 350, 100, 100, 120, 30 };//多边形顶点void PolyScan(){/******计算最高点的y坐标(扫描到此结束)****************************************/int MaxY = 0;int i;for (i = 0; i<POINTNUM; i++)if (polypoint[i].y>MaxY)MaxY = polypoint[i].y;/*******初始化AET表***********************************************************/ AET *pAET = new AET;pAET->next = NULL;/******初始化NET表************************************************************/ NET *pNET[1024];for (i = 0; i <= MaxY; i++){pNET[i] = new NET;pNET[i]->next = NULL;}glClear(GL_COLOR_BUFFER_BIT); //赋值的窗体显示.glColor3f(0.0, 0.0, 0.0); //设置直线的颜色红色glBegin(GL_POINTS);/******扫描并建立NET表*********************************************************/ for (i = 0; i <= MaxY; i++){for (int j = 0; j<POINTNUM; j++)if (polypoint[j].y == i){ //一个点跟前面的一个点形成一条线段。