0区域填充算法的研究

区域填充算法的研究摘要：本文主要介绍了一种常见的区域填充算法扫描线算法，其核心思想是利用区域的连贯性，扫描线的连贯性和边的连贯性，实现时首先计算扫描线与多边形区间，再用颜色或图案来显示这些像素，利用边的相关性及记录，边表及活动边表来完成多边形的区域填充。最后又介绍了一系列区域填充的改进算法，奇一偶规则扫描线算法，非零环绕规则的改进算法，逐点判断填充算法，种子填充算法，填充图案填充算法，边界标志算法和边缘填充算法以及他们的实现过程，对他们做出了比较，指出了每种算法存在的优点和不足，并加以改进，最后又对这几种算法的结果做出了分析，得出了扫描线算法比较快，适合用软件实现，但算法比较复杂，对于有边相交的情况，有可能出现异常的结论。对于在其基础上进行的改进算法，也都各有千秋，为此我们可以根据图形的具体情况选择最适用的填充算法。关键字：区域填充，扫描线算法，区域填充的改进算法本文由天空乐园大学生旅游网分享引言图形的区域填充是计算机图形学的基本图形操作。计算机图形学是计算机应用技术的基础内容之一,尤其是在虚拟现实技术、科学计算可视化、网络通信界面设计等领域有着越来越广泛的应用。其中,图形区域填充算法的优劣直接影响图形显示速度和显示质量.传统的多边形填充经典算法有扫描线填充算法和种子填充算法两种。而扫描线算法是从多边形的顶端开始,到多边形的底端为止,即先用一根根水平线进行扫描,并求得每一条水平扫描线与多边形各边的交点,然后将交点配成“交点对”,并在其间进行填充，这是最基础的一种区域填充算法。但是区域填充的扫描线算法又有很大的局限性，对于有边相交的情况还可能会出现异常，为此我们还要对其进行改进，以更好的应用于实践。一、基本理论扫描线多边形区域填充算法基本原理是待填充区域按Y方向(X方向亦可)扫描线顺序扫描生成。具体实现时，首先按扫描线顺序，计算扫描线与多边形的相交区间；再用要求的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。1.利用边的相关性可以简单有效的解决这个问题。对于一条扫描线，多边形的填充过程可以分为四个步骤：１1）求交：计算扫描线与多边形各边的交点；2）排序：把所有交点按x值递增顺序排序；3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间；4)填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。重合点的处理:当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用“起闭终开”或“起开终闭”。水平边处理2.边表（ET）和活动表（AET）边表是一个包含多边形全部边记录的表，又称ET表，它按y坐标（与扫描线一一对应）递增（或递减）的顺序存放边界区域的所有边。每个y坐标值存放２一个或几个边记录。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。随着扫描线从一条到另一条的转换，AET表也应随之变动，利用公式可以算出AET表中x域中的新值xi。凡是与这另一条扫描线相交的任何新边都加到AET表中，而与之不相交的边又被从AET表中删除。活性边表的每个节点的内容：第1项存当前扫描线与边的交点坐标x值；第2项存从当前扫描线到下一条扫描线间x的增量Dx；第3项存该边所交的最高扫描线号ymax；第4项存指向下一条边的指针。假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。(连贯性)设该边的直线方程为：ax+by+c=0；若y＝yi，x=xi；则当y=yi+1时，xi+1=xi-b/a其中ΔX=-b/a为常数，另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。扫描线6的活性边表扫描线7的活性边表３为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。当某条扫描线yi碰到多边形边界的新边时（以边线低端为准），则在ET表中相应的y坐标值处写入一个边记录。当同时有多条边进入时，则在ET表中按链表结构写入相应数目的多个记录，这些记录是按边线较低端点的x值增加的顺序排列。当没有新边加入时，表中对应的y坐标值储存内容为空。注意：在ET表中：1、与x轴平行的边不记录;2、多边形的顶点分为两大类，一类是局部极值点，另一类是非极值点。当扫描线与第一类顶点相遇时，应看作两个点；当扫描线与第二类顶点相遇时，应视为一个点。3.算法过程（1）根据给出的顶点坐标数据，按y递增顺序建立ET表。（2）根据AET指针，使之为空。４（3）使yi=ymin（ymin为顶点坐标中最小y值）。（4）反复做下述各步，直至yi=ymax（顶点坐标中y的最大值）或ET与AET为空：1、将ET表加入到AET中，并保持AET链中的记录按x值增大排序；2、对扫描线yi依次成对取出AET中xi值，并在每对xi之间填上所要求的颜色或图案；3、从AET表中删去yi=ymax的记录；4、对保留下来的AET中的每个记录，用xi+1/m代替xi，并重新按x递增排序；5、使yi+1，以便进入下一轮循环。区域填充算法的扫描线算法理论上可以采用，但是再实际实现过程中效率却不是很高，所以下面在此基础上对其进行了一系列的改进，他们都在一定程度上实现了区域填充算法的改进。二、改进算法1．奇一偶规则扫描线算法解决奇一偶规则扫描线算法的有效方法是先建立扫描线多边形有序边表(sortededgetable)，然后,从多边形的底部到顶部处理扫描线，对每条与多边形相交的扫描线生成一个活化边表（AET表），填充位于AET表中奇数交点和偶数交点之间的扫描区段。（1）建立有序边表对每条边建立如下结点信息：TypedefstructtEdge{IntyUpper;FloatxIntersect;FloatdxPerScan;StructtEdge*next;}Edge;根据上述结点信息,建立多边形的有序边表.（2）建立活化边表（AET）及填充算法设Ymax为最大扫描线的Y坐标值，Yi为第I条扫描线。①按上述要求建立多边形有序边表（Y桶链表）②I=0，AET置空③把有序边表中Yi所指向的结点链到AET链尾,并对AET链按结点中X坐标值的不减次序重排各结点。④填充AET链中位于奇数结点和偶数结点之间的扫描区段５⑤更新AET链表结点，删除结点分量yUpper=I的结点,对其余结点P用公式P-xIntersect=P-xIntersect+P-dxPerScan更新xIntersect分量⑥I=I+1，若I=Ymax则转,否则算法结束2．改进算法以适应非零环绕规则根据非零环绕规则和环绕数计算方法,我们可以从以下几个方面对算法1进行修该：不失一般性,在计算环绕方法中从P点引射线可以取成从P点沿X轴负方向引水平射线，则射线PQ的向量u的值为(XQ–XP，0)∴公式（1）Z=UXEY–UYEx=（XQ-XP）EY∵XQ-XP0∴Z与Ex异号故只要能保存多边形有向边的Y方向上的符号,就可以计算出点P的环绕数。为此改变有序边表中的结点结构：只须增加一个ySignEdge分量,当yUpper=有向边终点的y坐标值时,ySignEdge=1；否则当yUpper=有向边起点的y坐标值时,ySignEdge=-1.改变后的点结构为：yUpperxIntersectdxPerScanySignEdgenext改进算法1对于算法1,只须改动第④步,其余步骤无须变动.改动后的第④步为:设nonzeroNumber=0;NodeNumber=0;顺序遍历AET链表,对每一结点P置nonzeroNumber=nonzeroNumber+P-ySignEdge;NodeNumber=NodeNumber+1;若对nonzeroNumber≠0的后续区段进行填充,则完成非零环绕数规则填充算法.若对NodeNumber为奇数的后续区段进行填充,则完成奇一偶规则填充算法其中后续区段指当前结点和下结点X坐标之间的区域。3．逐点判断填充算法逐点判断填充算法的基本思想是逐点判断绘图窗口内的每一个像素，若在区域的内部则用指定的属性设置该点，否则不予处理。设有如下函数：６y)x,Inside(D,DxwhenFalseDxwhenTrue取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包围D，则逐点判断填充算法如下：for(y=y1;y=y2;y++)for(x=x1;x=x2;x++)if(inside(D,x,y))drawpixel(x,y,color);上述算法原理简单、实用，但效率低；效率低的原因是没有考虑各象素之间的联系，孤立地考察象素与区域的关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。一般用射线法来判断点在多边形的内或外。过被检测点任作一条射线,求其与边界的交点,若交点数为偶数,则该点在边界之外,否则在边界之内。当射线经过顶点时,可通过”左开右闭”,或”上开下闭”进行处理。７逐点判断法计算量比较大，比较慢，但方法比较简单，填充的图形类型比较多。4.种子填充算法种子填充算法假设在多边形内有一象素已知，由此出发利用连通性找到区域内的所有象素，并进行填充。种子填充算法又分为深度递归的种子填充算法和扫描线种子填充算法两种。下面是对这两种算法的介绍：（1）深度递归的种子填充算法(漫水法）从已知种子点出发，每填充一点，在其周围寻找新种子点，重复进行，直到再无未填充的点为止。针对内点连通区域的递归填充具体步骤:1.种子入栈.2.当栈非空时,进行下面的操作,否则结束.3.栈顶元素出栈,如果是未填充的内部点,则将其填充.继续考察与其连通的点,若是未填充的内部点,则该点入栈.返回2.准备工作：typedefstruct{intx,y;}seed;typedefstruct{seeds[6400];inttop;}seedstack;（2）扫描线种子填充算法1．种子填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用采用扫描线算法。2．算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，确定新种子点，并依次保存下来。反复这个过程，直到填充结束。上述算法对于每一个待填充区段，只需压栈一次；而在递归算法中，每个象素都需要压栈。因此，扫描线填充算法提高了区域填充的效率。扫描线种子区域填充算法可由下列四个步骤实现：1．初始化：堆栈置空。将种子点（x，y）入栈。2．出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。3．填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到非内部。分别标记区段的左、右端点坐标为xl和xr。８4．并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第2步。5．填充图案前面介绍的那些区域填充算法，都是把区域内部的全部的象素设置为同一种颜色。但在实际应用中，有时需要用一种图案来填充平面区域。可以通过对前述算法中写象素的那部分内容稍作修改来实现：在确定了区域内一象素之后，不是马上往该象素填色，而是先查询图案位图的对应位置。进行图案填充时，在不考虑图案旋转的情况下，必须确定区域与图案之间的位置关系。这可以通过把图案原点与区域某点对齐的办法来实现。1.对齐方法有两种：第一种是把图案原点与填充区域边界或内部某点对齐。第二种方法是把图案原点与填充区域外部的某点对齐。2.用第一种方法填充的图案，将随着区域的移动而移动，看起来很自然。对于多边形，可取区域边界上最左边