计算机图形学四连通区域种子填充算法实验
————————————————————————————————作者: ————————————————————————————————日期:
ﻩ
《计算机图形学实验》报告
任课教师:钱文华
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ｒ);
后的结果如下图:
实验总结:通过多组数据的测试，知道了上面算法的正确,普适性。
种子填充的递归算法的优点是原理非常简单,容易理解，缺点是由于多次递归，费时，费内存，效率不高,需要大量栈空间来存储相邻的点，太大的区域会由于递归太深而无法运行。
为了减少递归次数，可采用扫描线种子算法。
扫描线填充算法就是它的改进的方法。
它是通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈,从而可以节省大量的栈空间。