区域的填充

数学与计算科学学院实验报告实验项目名称区域的填充所属课程名称计算机图形学实验类型验证性实验日期2015-3-27班级学号姓名成绩第1页共7页一、实验概述：【实验目的】1、掌握多边形填充的基本原理；2、掌握边界标志算法来实现多边形填充的思想。要求掌握多边形区域扫描线填充的有序边表算法的基本原理和算法设计。通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理，掌握多边形区域填充算法的基本过程。掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。，【实验原理】种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。这里讨论的区域指已经表示成点阵形式的填充图形，它是象素的集合。区域可采用内点表示和边界表示两种表示形式。在内点表示中，区域内的所有象素着同一颜色。在边界表示中，区域的边界点着同一颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。【实验环境】1.硬件环境2.2.软件环境Visualc++6.0二、实验内容：第2页共7页【实验过程】（实验步骤）区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素；8向连通区域指的是从区域内每一象素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。(1)初始化：堆栈置空。将种子点(x,y)入栈。(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。（3）填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。(3)【实验结论】四连通区域八连通区域图2.3.7四连通区域和八连通区域图2.3.8区域的内点表示和边界表示第3页共7页【实验小结】（收获体会）种子填充算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。扫描线填充算法就是它的改进的方法。它是通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。通过实验，实现多边形区域扫描线填充的有序边表算法，并将实现的算法应用于任意多边形的填充，要求多边形的顶点由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。同时掌握了边形区域扫描线填充的有序边表算法的基本原理和算法设计。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：第4页共7页附录：源程序区域填充的扫描线算法typedefstruct{//记录种子点intx;inty；}Seed;voidScanLineFill4(intx,inty,COLORREFoldcolor,COLORREFnewcolor){intxl,xr,i;boolspanNeedFill;Seedpt;setstackempty();pt.x=x;pt.y=y;stackpush(pt);//将前面生成的区段压入堆栈while(!isstackempty()){pt=stackpop();y=pt.y;x=pt.x;while(getpixel(x,y)==oldcolor)//向右填充第5页共7页{drawpixel(x,y,newcolor);x++;}xr=x-1;x=pt.x-1;while(getpixel(x,y)==oldcolor)//向左填充{drawpixel(x,y,newcolor);x--;}xl=x+1;//处理上面一条扫描线x=xl;y=y+1;while(xxr){spanNeedFill=FALSE;while(getpixel(x,y)==oldcolor){spanNeedFill=TRUE;x++;第6页共7页}if(spanNeedFill){pt.x=x-1;pt.y=y;stackpush(pt);spanNeedFill=FALSE;}while(getpixel(x,y)!=oldcolor&&xxr)x++;}//Endofwhile(ixr)//处理下面一条扫描线，代码与处理上面一条扫描线类似x=xl;y=y-2;while(xxr){....}//Endofwhile(ixr)}//Endofwhile(!isstackempty())}