区域填充算法的研究.docVIP

区域填充算法的探究 本文由天空乐园大学生旅游网整理分享 摘要 区域填充算法是计算机图形学的一个重要研究课题．传统的区域填充算法存在填充结果不完备及算法效率不高的问题，在分析了两种传统区域填充算法的原理的基础上，详细阐述了四种改进的区域填充算法，并对算法的效率性能进行比较分析，指明了区域填充算法未来的研究热点区域填充；填充算法；扫描线算法；种子填充算法区域填充是指用不同的颜色、灰度、线条或符号填充一个有界区域，该区域可以是带孔的，也可以是不带孔的．它是计算机图形学的一项重要内容，在交互式图形设计、真实感图形显示、计算机辅助设计、图形分析等领域有着广泛的应用，一直是研究的热点．传统的区域填充算法有两种，一种是通过确定横跨区域的扫描线的覆盖间隔来填充的扫描线算法，另一种是从给定的位置开始填充直到指定的边界为止的种子填充算法．扫描线算法主要用来填充比较简单的标准多边形区域，比如圆、椭圆以及其他一些简单的多边形，它对轮廓线的形状有一定的要求，在处理复杂区域时往往失效．种子填充算法可以解决边界比较复的多边形区域填充问题，它必须首先确定一个或者多个区域内部的点作为种子点，并赋予填充色然后以该点为起点，用四向连通方法或八向连通方法找到区域内的所有点充扫描线算法在处理带水平边的凹拐点时不能正确填充，这是该算法的一个突出问题，但由于利用了扫描线上象素之问的连贯性，因此具有较高的效率．最简单直观的种子填充算法采用递归方法，由于进行大量的出入栈操作，因此效率很低，在填充较大的区域时，要求分配较大的堆栈空问，不仅浪费了内存，也可能出现堆栈溢出现象．填充结果的完备性和填充过程的高效高速是区域填充算法的度量标准．在传统区域填充算法的基础上，很多文献提出了更加正确高效的算法．本文介绍四种改进的区域填充算法，并对其进行比较分析在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内故不能直接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。多边形分为凸多边形、凹多边形、含内环多边形。 凸多边形：任意两顶点间的连线均在多边形内凹多边形任意两顶点间的连线含内环多边形形内扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为个步骤（1）求交：计算扫描线与多边形各边的交点（2）排序：把所有交点按x值递增顺序排序（3）配对：第一个与第二个，第三个与第四个等每对交点代表扫描线与多边形的一个相交区间（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。 （1）初始化：构造边表。 （2）对边表进行排序，构造活性边表。 （3）对每条扫描线对应的活性边表中求交点。 （4）判断交点类型，并两两配对。 （5）对符合条件的交点之间用画线方式填充。 （6）下一条扫描线，直至满足扫描结束条件。 2.2区域填充算法 这里的区域指已表示成点阵形式的填充图形，是素的集合。区域两种表示形式内点表示和边界表示。内点表示，区域内的所有素同颜色边界表示，区域的边界点同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 ○表示边界点●表示内点 图 区域的内点表示和边界表示图连通区域和连通区域区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。扫描线算法是按照扫描线顺序，计算扫描线与多边形的相交区间，再用颜色显示这个区间，区间的端点则是扫描线与多边形边界线的交点，可以通过计算获得．要完成这个扫描转换过程，首先计算扫描线与多边形各边的交点，然后对求得的交点进行排序，接下来利用奇偶配对求出扫描线与边形的相交区间，最后对这些相交区问填色．由于扫描线是一组连续的水平平行的直线，因此在计算其与多边形的交点时较容易，因为交点的纵坐标已知，即扫描线的编号，则可根据多边形的数学表达式求出交点的横坐标．对交点进行排序时采用横坐标由小到大的顺序，便于相交区间的确定．对于已经排序的交点，使用奇偶配对法确定相交区间，如：交点a。与交点a2为一对，交点a。