资源描述：
《计算机图形学 区域填充.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四讲区域填充有关概念逐点判断填充算法3.种子填充算法4.区域填充图案5.扫描线多边形填充算法6.边填充算法1.有关概念1)区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。3)区域填充：以某种属性对整个区域进行设置的过程。2）种类：①单域②复合域4）区域的建立（定义）方式：①内定区域：在所定义的区域内所有的像素具有相同的属性（如颜色等）。（内部定义方式）②边界定义区域：以区域的内外属性来划分，区域内的像素和边界上的像素可具有不同的属性。（外界定义方式）5）连通性：分为四向连通和八向连通。①四连通：各像素在水平、垂直的上、下、左、右四个方向上是连通的。
2、②八连通：各像素在上、下、左、右以及四个对角线方向都是连通的。2.逐点判断填充算法区域填充的基本(初级)方法:逐点判断填充算法逐点判断绘图窗口内的每一个像素；若在区域的内部：用指定的属性设置该点；否则不予处理；设有如下函数：TruewhenxDInside(D,x,y)=FalsewhenxDD取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包围D，则逐点判断填充算法如下：for(y=y1;y<=y2;y++)for(x=x1;x<=x2;x++)if(inside(D,x,y))drawpixel(x,y,color);上述算法原理简单、实用，但效率低；效率低
3、的原因是没有考虑各象素之间的联系，孤立地考察象素与区域的关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。1）射线法；2）累计角度法；3）编码法；4）……..这些内容在本书第八章几何造型中有专门介绍。如何判断点在多边形的内或外？（包含性检查的方法）这里以射线法为例进行说明：过被检测点任作一条射线,求其与边界的交点,若交点数为偶数,则该点在边界之外,否则在边界之内。当射线经过顶点时,可通过”左开右闭”,或”上开下闭”进行处理。PP3.种子填充算法1）深度递归的种子填充算法2）扫描线种子填充算法种子填充算法假设
4、在多边形内有一象素已知，由此出发利用连通性找到区域内的所有象素，并进行填充。1）深度递归的种子填充算法(漫水法）从已知种子点出发，每填充一点，在其周围寻找新种子点，重复进行，直到再无未填充的点为止。针对内点表示的4连通区域的递归填充具体步骤:1.种子入栈.2.当栈非空时,进行下面的操作,否则结束.3.栈顶元素出栈,如果是未填充的内部点,则将其填充.继续考察与其连通的点,若是未填充的内部点,则该点入栈.返回2.准备工作：typedefstruct{intx,y;}seed;typedefstruct{seeds[6400];inttop;}seedstack;VC
5、++程序实现可以直接利用函数的递归调用来实现.设（x,y）为内点表示的4连通区域内的一点，oldcolor为区域的原色，要将整个区域填充为新的颜色newcolor。内点表示的4连通区域的递归填充算法:voidFloodFill4(intx,inty,intoldcolor,intnewcolor){if(getpixel(x,y)==oldcolor){drawpixel(x,y,newcolor);FloodFill4(x,y+1,oldcolor,newcolor);FloodFill4(x,y-1,oldcolor,newcolor);FloodFill4
6、(x-1,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor);}}边界表示的4连通区域的递归填充算法:voidBoundaryFill4(intx,inty,intboundarycolor,intnewcolor){intcolor=Getpixel(x,y);if(color!=newcolor&&color!=boundarycolor){drawpixel(x,y,newcolor);BoundaryFill4(x,y+1,boundarycolor,newcolor);BoundaryFil
7、l4(x,y-1,boundarycolor,newcolor);BoundaryFill4(x-1,y,boundarycolor,newcolor);BoundaryFill4(x+1,y,boundarycolor,newcolor);}}对于内点表示和边界表示的8连通区域的填充，只要将上述相应代码中递归填充相邻的4个象素增加到递归填充8个象素即可。2）扫描线种子填充算法种子填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用采用扫描线算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点
8、所在扫描线上的位于给定区
