区域填充算法的探究.doc

《区域填充算法的探究.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、区域填充算法的探究1摘要本文旨在通过探究区域填充算法尤其是扫描线种子填充算法和种子填充算法近年来的发展状况，比较它们之间的优点与不足，对图形学的区域填充算法有更深入的理解。在准备本报告的同时还加以实验环节，选用扫描线填充算法和扫描线种子填充算法来对算法加以验证、调试和理解。2区域填充基本知识点介绍2.1多边形扫描转换在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表

2、示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。多边形可分为凸多边形、凹多边形、含内环多边形。（1）凸多边形：任意两顶点间的连线均在多边形内。（2）凹多边形：任意两顶点间的连线有不在多边形内的部分。（3）含内环多边形：多边形内包含有封闭多边形。扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素。区间的端点可以通过计算扫描线与多

3、边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为4个步骤。（1）求交：计算扫描线与多边形各边的交点。（2）排序：把所有交点按x值递增顺序排序。（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间。（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。多边形扫描转换算法步骤如下：（1）初始化：构造边表。（2）对边表进行排序，构造活性边表。（3）对每条扫描线对应的活性边表中求交点。（4）判断交点类型，并两两配对。（5）对符合条件的交点之间用画线方式填充。（6）下一条扫描线，

4、直至满足扫描结束条件。2.2区域填充算法这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图2-1所示。内点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。图2-1区域的内点表示和边界表示图2-24连通区域和8连通区域区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图2-2所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提

5、下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。2.2.1区域填充的扫描线算法算法的基本过程如下：给定种子点（x，y），首先填充种子点所在扫描线上给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。求出yminymax开始结束yminyy+1y求出由扫描线y确定的水平线与多边形两个交点（x1，y），（x2，y）将（x1，y）与（x2，y）连接y>ymaxNY图

6、2-3扫描线填充算法流程图区域填充的扫描线算法可由下列3个步骤实现。Step1：求出每条水平扫描线与多边形各边的交点。Step2：将每条水平扫描线上的交点按X值递增的顺序排列。Step3：将交点的交点配成“交点对”。Step4：在交点对间填色。2.2.2区域填充的种子算法种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上

7、、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。a)连通域及其内点b)填充四连通域图2-4四向连通填充算法一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2-4a所示的区域的内部，而四向连通填充算法只能完成如图2-4b的部分填充。3区域填充算法日新月

8、异的发展上面所提到的区域填充算法，扫描线算法和种子填充算法适用条件苛刻，要么对所要填充的多边形有一定的局限性，要么就是由于采用递归次数太多，区域内的每个像素都引起一次递归，即系统堆栈的一次进出