计算机图形学-区域填充的扫描线算法

计算机图形学——区域填充的扫描线算法一．实验名称：区域填充的扫描线算法二．实验目的：1、理解区域填充扫描线算法的原理；2、实现区域填充的扫描线算法并测试；三．算法原理：算法基本思想:首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存,这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。借助于栈结构，区域填充的扫描线算法之步骤如下：Step1.初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈；Step2.出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点；Step3.区段填充：从种子点(x,y)开始沿纵坐标为y的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor直至到达区域边界。分别以xl和xr表示该填充区段两端点的横坐标；Step4.新种子点入栈:分别确定当前扫描线上、下相邻的两条扫描线上位于区段[xl,xr]内的区域内的区段。若这些区段内的像素点颜色值为newolor,则转至Step2；否则以区段的右端点为种子点入种子点栈，再转至Step2。四．原程序代码：/*****************************************//*4-ScanLineFill区域填充的扫描线算法实现*//*****************************************/#includestdio.h#includeconio.h#includegraphics.h#includemalloc.h#defineStack_Size100//栈的大小常量//定义结构体,记录种子点typedefstruct{intx;inty;}Seed;//定义顺序栈(种子点)typedefstruct{SeedPoint[Stack_Size];inttop;}SeqStack;//初始化栈操作voidInitStack(SeqStack*&S){S=(SeqStack*)malloc(sizeof(SeqStack));S-top=-1;}//种子点栈置空；voidsetstackempty(SeqStack*S){S-top==-1;}//种子点栈状态检测函数intisstackempty(SeqStack*S){if(S-top==-1)returntrue;//空栈返回trueelsereturnfalse;//非空栈返回false}//种子点入栈；intstackpush(SeqStack*&S,Seedpoint){if(S-top==Stack_Size-1)//栈已满，返回falsereturnfalse;S-top++;//栈未满，栈顶元素加1S-Point[S-top]=point;returntrue;}//取栈顶元素；intstackpop(SeqStack*&S,Seed&point){if(S-top==-1)//栈为空，返回falsereturnfalse;point=S-Point[S-top];S-top--;//栈未空，top减1returntrue;}//画圆voidCirclePoints(intxc,intyc,intx,inty,intColor){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);}//中点画圆算法voidMidpointCircle(intradius,intColor){intx,y;floatd;x=0;y=radius;d=5.0/4-radius;CirclePoints(250,250,x,y,Color);while(xy){if(d0){d+=x*2.0+3;}else{d+=(x-y)*2.0+5;y--;}x++;CirclePoints(250,250,x,y,Color);}}//四连通扫描线算法voidScanLineFill4(intx,inty,intoldcolor,intnewcolor){intxl,xr,i;boolSpanNeedFill;Seedpt;//种子点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(xxr){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)&&(xxr))x++;}//上一条扫描线上检查完毕x=xl;y=y-2;//处理下面一条扫描线while(xxr){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)&&(xxr))x++;}}}//主函数检测voidmain(){intradius,color;intx,y;//种子点intoldcolor,newcolor;//原色与填充色//输入参数值printf(inputradiusandcolor:\n);//画圆参数scanf(%d,%d,&radius,&color);printf(inputxandy:\n);//读入内点scanf(%d,%d,&x,&y);printf(inputoldcolorandnewcolor:\n);//读入原色与填充色scanf(%d,%d,&oldcolor,&newcolor);intgdriver=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.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。