资源描述：
《第二章---扫描转换与区域填充》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、扫描转换与区域填充一基本概念•区域是指一组相邻而又相连的象素，且具有相同的属性。•根据边或顶点的简单描述，生成实区域的过程称为区域填充或多边形的扫描转换。1区域填充算法可分为两大类：种子填充算法；扫描转换填充算法；山东科技大学信息学院•种子填充算法：首先假定封闭轮廓线内某点是已知的，然后算法开始搜索与种子点相邻且位于轮廓线内的点。如果相邻点不在轮廓线内，那么就达到轮廓线的边界；如果相邻点位于轮廓线之内，那么这一点就成为新的种子点，然后继续递归地搜索下去。种子填充算法只适用于光栅扫描设备。•扫描转换填充算法则是按扫描线的顺
2、序确定某一点是否位于多边形或轮廓线范围内。山东科技大学信息学院2扫描转换多边形•多边形的表示方法–顶点表示–点阵表示•顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。•点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。山东科技大学信息学院3区域的建立表示方法：内点表示、边界表示•内点表示–枚举出区域内部的所有像素–内部的所有像素着同一个颜色–边界像素着与内部像素不同的颜色•边界表示–枚举出边界上所有的像素–边界上
3、的所有像素着同一颜色–内部像素着与边界像素不同的颜色山东科技大学信息学院4象素的连通区域填充要求区域是连通的•连通性4连通、8连通•4连通：•8连通山东科技大学信息学院4连通与8连通区域的区别–连通性：4连通可看作8连通区域，但对边界有要求–对边界的要求–关系：一个8连通区域的边界是4连通的一个4连通区域的边界是8连通的山东科技大学信息学院二、区域填充：种子填充算法1适合于内点表示区域的填充算法设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素
4、(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。山东科技大学信息学院种子填充算法•例：多边形由P0P1P2P3P4构成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)•设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序
5、如图中箭头所示山东科技大学信息学院种子填充算法递归算法可实现如下voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)==oldColor){PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldCo
6、lor,newColor);}}/*endofFloodFill4()*/山东科技大学信息学院种子填充算法2边界表示的4连通区域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){intcolor;color=GetPixel(x,y);if((color!=boundaryColor)&&(color!=newColor)){PutPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);Boun
7、daryFill4(x,y-1,oldColor,newColor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);}}/*endofBoundaryFill4()*/山东科技大学信息学院种子填充算法•该算法也可以填充有孔区域。•缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。•改进算法，减少递归次数，提高效率。
8、解决方法是用扫描线填充算法山东科技大学信息学院3扫描线种子填充算法•扫描线种子填充算法–目标：减少递归层次–适用于边界表示的4连通区域算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它
