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

实验四 区域填充算法的实现班级 08信计二 学号 64 姓名 刘辉 分数一、实验目的和要求：1、 理解区域的表示和类型；2、 能够正确区分四连通、八连通的区域；3、 了解填充函数、区域填充的实现原理；4、 了解掌握区域填充的各种算法（种子填充算法、扫描线算法、边填充算法等），并实现种子填充算法和扫描线算法；5、 用种子填充算法实现四连同区域和八连通区域的填充，并观察他们之间的区别；6、 分析对比种子填充算法和扫描线算法实现的像素逼近效果和程序执行速度；二、实验原理： 用点阵方法表示的多边形区域，如果其内部像素具有同一种颜色，而边界像素具有另一种颜色，可以使用种子填充算法和扫描线算法等填充。种子填充算法是从区域内任一个种子像素位置（x，y）开始，由内向外将填充色扩散到整个多边形区域的填充过程；扫描线填充算法是当给定种子点（x，y）时，首先填充种子点所在扫描线上位于给定区域的一个区段，然后确定与这一段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来的过程。三、实验内容及步骤：3.1、实验内容：1. 利用种子算法实现内点表示的四连通区域的填充。如：设（x，y）为内点表示的四连通区域内的一点，oldcolor为区域的原色，要将整个区域填充为新的颜色newcolor；2. 利用扫描线算法实现以上区域的填充。如：填充以下图案，圆中填充蓝色，三角形中填充红色；3.2、实验步骤：种子填充算法的步骤：1. 种子入栈；2. 当栈非空时，进行下面的操作，否则结束；3. 栈顶元素出栈，如果是未填充的内部点，则将其填充，继续考察与其连通的点，若是为填充的内部点，则该点入栈，返回2步。扫描线填充算法的步骤：1. 初始化，置栈为空，将种子点（x，y）入栈。2. 出栈，若栈空则结束；否则取栈顶元素（x，y），以y作为扫描线。3. 填充并确定种子点所在区段，从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。4. 确定新的种子点，在以上确定的边界中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，返回2步。四、程序代码（1）、内点表示的四连通区域的种子递归填充算法（基于TurboC）：#includevoid floodfill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) putpixel(x,y,newcolor); delay(2000); 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(14); rectangle(250,250,300,300); for(i=251;i300;i+) for(j=251;j300;j+) putpixel(i,j,4); delay(1000); a=257; b=270; c=4; d=2; floodfill4(a,b,c,d); getch(); closegraph();（2）、内点表示的八连通区域的种子递归填充算法的调用函数：void floodfill8(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) putpixel(x,y,newcolor); delay(2000); 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); （3）、内点表示的四连通区域的扫描线填充算法（基于Vc+）：#include#include#include #define MaxSize 100typedef struct int x; int y;Seed,ElemType;typedef struct ElemType dataMaxSize;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-datas-top=e;return 1;int Pop(SqStack *&s,ElemType &e)if (s-top=-1)return 0;e=s-datas-top;s-top-;return 1;void ScanLineFill4(int x,int y,int oldcolor,int newcolor) int xl,xr,i; bool spanNeedFill; Seed pt,e; SqStack *s; InitStack(s); pt.x=x;pt.y=y; Push(s,pt); while(!StackEmpty(s) Pop(s,e); y=e.y; x=e.x; while(getpixel(x,y)=oldcolor) putpixel(x,y,newcolor); Sleep(1); x+; xr=x-1; x=pt.x-1; while(getpixel(x,y)=oldcolor) putpixel(x,y,newcolor); Sleep(1); 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; Push(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; Push(s,pt); spanNeedFill=FALSE; while(getpixel(x,y)!=oldcolor&x=xr) x+; 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(RED); int points=320,200,270,290,370,290; fillpoly(3,points); circle(320,240,160); a=RGB(255,255,255); b=RGB(255,0,0); ScanLineFill4(320,240,a,b); c=RGB(0,0,0); d=RGB(0,0,255); ScanLineFill4(320,180,c,d); getch(); closegraph();五、实验结果及分析（1）、实验结果：1、2、3、该算法实现了带孔图案的填充（2）实验分析：1. 种子填充算法适合于已经画出大量边界线的场合，适合于人机交互操作方式，或者事先保留了种子点，是最常用的是递归和扫描线的填充算法。2. 区域的连通方式对填充结果会产生影响。3. 区域填充的种子递归算法原理和程序都很简单，但由于多次递归，费时、费力、费内存，效率不高。为了减少递归次数，提高效率，可以采用扫描线算法。4. 扫描线算法减少了每个像素的访问次数，所需堆栈深度较浅，每次递归填充一行像素点，因而速度较快。5. 扫描线算法适用于边界定义的区域，四连通边界定义区域既可以是凸的，也可以是凹的，还可以是有孔的。六、实验总结在实