区域填充算法

《区域填充算法》由会员分享，可在线阅读，更多相关《区域填充算法（15页珍藏版）》请在金锄头文库上搜索。

1、6.7区域填充算法,6.7区域填充算法,区域填充算法是指给出一个区域的边界，要求在边界范围内对所有像素单元赋予指定的颜色代码。目前，区域填充算法中最常用的是多边形填色，常用的多边形填色算法有两种： 递归种子填充算法 扫描线种子填充算法。,1、递归种子填充算法 递归种子填充算法，又称边界填色算法。算法的原理是：让单个像元作为填充胚，在给定的区域范围内，通过某种方法进行蔓延，最终填充满整个多边形区域。为了实现填充胚的蔓延，可采用四邻法或八邻法进行填充。,2、扫描线种子填充算法 （1）扫描线种子填充算法扫描线种子填充算法的对象是一个个扫描线段。扫描线段是指区域内同值相邻像素在水平方向的组合，它的两端

2、以具有边界值的像素为边界，即一段扫描线段的中间只有同一种像素。扫描线种子填充算法适用于边界定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。,（1）扫描线种子填充算法 实现方法： 第一步，建立一个存放每条扫描线各填充区段右端点的堆栈，最初把种子像素压入堆栈。 第二步，沿扫描线对出栈像素的左、右像素进行填充直至遇到边界像素为止，即每出栈一个像素就对区域内包含该像素的整个连续区段进行填充。 第三步，检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素。若存在非边界、未填充的像素则把未填充的每一连续区段最左像素作为新种子像素入栈。 第四步，重复一至三步，直到所

3、有的区域都填充完成。,2、扫描线种子填充算法 （2）扫描线种子填充算法的改进 为了避免在后续填充时重复检查内部像素点的问题，倪玉山等（2000）在种子填充算法和扫描线种子填充算法的基础上，提出了一种扫描线种子填充算法的改进算法，该算法一定程度上提高了区域填充的效率。 改进算法的基本思想是：每找到一个新的内部区段时,不仅将新区段的y值(yn)和左右列值xnl，xnr压入堆栈，而且同时把当前区段的y值和左右列值xl,xr也压入堆栈，以保存和传递有关的信息。,3、基于曲线积分的区域填充算法基于曲线积分的区域填充算法是邓国强，孙景鳌等（2001）提出的一种以格林公式求区域面积为基本原理进行区域填充的特

4、殊算法。 该算法具有运算速度快、对图形的适应性强、填充结果重复性好等优点；它从根本上克服了多边形填充法对区域形状有一定限制，种子填充法要求知道区域内一点（填充胚）以及对区域内像素点进行重复判断等弊端；而且该算法适应于任何一种可以准确描绘出边界曲线的区域填充处理。,3、基于曲线积分的区域填充算法 算法的实现： 对一个区域进行轮廓跟踪，求出区域的边界像素点序列L； 利用面积计算公式识别出区域像素集的内点。,4、区域填充算法在地图制图中的应用 区域填充算法在地图制图及其它领域中有着广泛的应用，如图案的填充、距离和多边形面积的量算、栅格图形的局部删除及动画片和图形艺术处理等方面。,4、区域填充算法在地图制图中的应用 （1）填充图案,4、区域填充算法在地图制图中的应用 （2）计算多边形面积,4、区域填充算法在地图制图中的应用 （2）计算多边形面积 SA=M2Sa SB=M2Sb SC=M2Sc,谢谢观赏,