区域填充算法区域填充算法.ppt

6.7区域填充算法;6.7区域填充算法;;2、扫描线种子填充算法 （1）扫描线种子填充算法 扫描线种子填充算法的对象是一个个扫描线段。扫描线段是指区域内同值相邻像素在水平方向的组合，它的两端以具有边界值的像素为边界，即一段扫描线段的中间只有同一种像素。 扫描线种子填充算法适用于边界定义的区域。区域可以是凸的，也可以是凹的，还可以包含一个或多个孔。 ;（1）扫描线种子填充算法 实现方法： 第一步，建立一个存放每条扫描线各填充区段右端点的堆栈，最初把种子像素压入堆栈。 第二步，沿扫描线对出栈像素的左、右像素进行填充直至遇到边界像素为止，即每出栈一个像素就对区域内包含该像素的整个连续区段进行填充。 第三步，检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素。若存在非边界、未填充的像素则把未填充的每一连续区段最左像素作为新种子像素入栈。 第四步，重复一至三步，直到所有的区域都填充完成。 ;2、扫描线种子填充算法 （2）扫描线种子填充算法的改进 为了避免在后续填充时重复检查内部像素点的问题，倪玉山等（2000）在种子填充算法和扫描线种子填充算法的基础上，提出了一种扫描线种子填充算法的改进算法，该算法一定程度上提高了区域填充的效率。 改进算法的基本思想是：每找到一个新的内部区段时,不仅将新区段的y值(yn)和左右列值xnl，xnr压入堆栈，而且同时把当前区段的y值和左右列值xl,xr也压入堆栈，以保存和传递有关的信息。 ;3、基于曲线积分的区域填充算法 基于曲线积分的区域填充算法是邓国强，孙景鳌等（2001）提出的一种以格林公式求区域面积为基本原理进行区域填充的特殊算法。 该算法具有运算速度快、对图形的适应性强、填充结果重复性好等优点；它从根本上克服了多边形填充法对区域形状有一定限制，种子填充法要求知道区域内一点（填充胚）以及对区域内像素点进行重复判断等弊端；而且该算法适应于任何一种可以准确描绘出边界曲线的区域填充处理。;3、基于曲线积分的区域填充算法 算法的实现： 对一个区域进行轮???跟踪，求出区域的边界像素点序列L； 利用面积计算公式识别出区域像素集的内点。 ;;4、区域填充算法在地图制图中的应用 （1）填充图案 ;4、区域填充算法在地图制图中的应用 （2）计算多边形面积 ;4、区域填充算法在地图制图中的应用 （2）计算多边形面积 SA=M2·Sa SB=M2·Sb SC=M2·Sc ;