区域填充算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,6.7区域填充算法,6.7,区域填充算法,区域填充算法是指给出一个区域的边界，要求在边界范围内对所有像素单元赋予指定的颜色代码。,目前，区域填充算法中最常用的是,多边形填色,，,常用的多边形填色算法有两种：,递归种子填充算法,扫描线种子填充算法。,1,、递归种子填充算法,递归种子填充算法，又称,边界填色算法,。,算法的,原理,是：让单个像元作为填充胚，在给定的区域范围内，通过某种方法进行,蔓延,，最终填充满整个多边形区域。为了实现填充胚的蔓延，可采用,四邻法,或,八邻法,进行填充。,2,、扫描线种子填充算法,（,1,）扫描线种子填充算法,扫描线种子填充算法的对象是一个个,扫描线段,。扫描线段是指区域内同值相邻像素在水平方向的组合，它的两端以具有边界值的像素为边界，即一段扫描线段的中间只有,同一种像素,。,扫描线种子填充算法适用于边界定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。,（,1,）扫描线种子填充算法,实现方法：,第一步,，建立一个存放每条扫描线各填充区段,右端点,的堆栈，最初把种子像素压入堆栈。,第二步,，沿扫描线对出栈像素的,左、右,像素进行填充直至遇到边界像素为止，即每出栈一个像素就对区域内包含该像素的整个连续区段进行填充。,第三步,，检查与当前扫描线,相邻的上下,两条扫描线的有关像素是否全为边界像素或已填充的像素。若存在非边界、未填充的像素则把未填充的每一连续区段,最左,像素作为新种子像素入栈。,第四步,，重复一至三步，直到所有的区域都填充完成。,2,、扫描线种子填充算法,（,2,）扫描线种子填充算法的改进,为了避免在后续填充时,重复检查内部像素点,的问题，倪玉山等（,2000,）在种子填充算法和扫描线种子填充算法的基础上，提出了一种扫描线种子填充算法的改进算法，该算法一定程度上提高了区域填充的效率。,改进算法的,基本思想,是：每找到一个新的内部区段时,不仅将新区段的,y,值,(,yn,),和左右列值,xnl,，,xnr,压入堆栈，而且同时把当前区段的,y,值和左右列值,xl,xr,也压入堆栈，以保存和传递有关的信息。,3,、基于曲线积分的区域填充算法,基于曲线积分的区域填充算法是邓国强，孙景鳌等（,2001,）提出的一种以,格林公式,求区域面积为基本原理进行区域填充的特殊算法。,该算法具有运算速度快、对图形的适应性强、填充结果重复性好等优点；它从根本上克服了多边形填充法对区域形状有一定限制，种子填充法要求知道区域内一点（填充胚）以及对区域内像素点进行重复判断等弊端；而且该算法适应于任何一种可以准确描绘出边界曲线的区域填充处理。,3,、基于曲线积分的区域填充算法,算法的实现：,对一个区域进行轮廓跟踪，求出区域的边界像素点序列,L,；,利用面积计算公式识别出区域像素集的内点。,4,、区域填充算法在地图制图中的应用,区域填充算法在地图制图及其它领域中有着广泛的应用，如图案的填充、距离和多边形面积的量算、栅格图形的局部删除及动画片和图形艺术处理等方面。,4,、区域填充算法在地图制图中的应用,（,1,）填充图案,4,、区域填充算法在地图制图中的应用,（,2,）计算多边形面积,4,、区域填充算法在地图制图中的应用,（,2,）计算多边形面积,SA=M,2,S,a,SB=M,2,S,b,SC=M,2,S,c,谢谢观赏,