0区域填充算法的研究

《0区域填充算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、区域填充算法的研究摘要：本文主要介绍了一种常见的区域填充算法扫描线算法，其核心思想是利用区域的连贯性，扫描线的连贯性和边的连贯性，实现时首先计算扫描线与多边形区间，再用颜色或图案来显示这些像素，利用边的相关性及记录，边表及活动边表来完成多边形的区域填充。最后又介绍了一系列区域填充的改进算法，奇一偶规则扫描线算法，非零环绕规则的改进算法，逐点判断填充算法，种子填充算法，填充图案填充算法，边界标志算法和边缘填充算法以及他们的实现过程，对他们做出了比较，指出了每种算法存在的优点和不足，并加以改进，最后又对这几种算法的结果做出了分析，得出了扫描线算法比

2、较快，适合用软件实现，但算法比较复杂，对于有边相交的情况，有可能出现异常的结论。对于在其基础上进行的改进算法，也都各有千秋，为此我们可以根据图形的具体情况选择最适用的填充算法。关键字：区域填充，扫描线算法，区域填充的改进算法本文由天空乐园大学生旅游网分享引言图形的区域填充是计算机图形学的基本图形操作。计算机图形学是计算机应用技术的基础内容之一,尤其是在虚拟现实技术、科学计算可视化、网络通信界面设计等领域有着越来越广泛的应用。其中,图形区域填充算法的优劣直接影响图形显示速度和显示质量.传统的多边形填充经典算法有扫描线填充算法和种子填充算法两种。而

3、扫描线算法是从多边形的顶端开始,到多边形的底端为止,即先用一根根水平线进行扫描,并求得每一条水平扫描线与多边形各边的交点,然后将交点配成“交点对”,并在其间进行填充，这是最基础的一种区域填充算法。但是区域填充的扫描线算法又有很大的局限性，对于有边相交的情况还可能会出现异常，为此我们还要对其进行改进，以更好的应用于实践。一、基本理论扫描线多边形区域填充算法基本原理是待填充区域按Y方向(X方向亦可)扫描线顺序扫描生成。具体实现时，首先按扫描线顺序，计算扫描线与多边形的相交区间；再用要求的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的

4、端点可以通过计算扫描线与多边形边界线的交点获得。1.利用边的相关性可以简单有效的解决这个问题。对于一条扫描线，多边形的填充过程可以分为四个步骤：１５1）求交：计算扫描线与多边形各边的交点；2）排序：把所有交点按x值递增顺序排序；3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间；4)填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。重合点的处理:当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用“起闭终开”或“起开终闭”。水平边处理2.边表（ET）和活动表（AET）１５边表是一个包

5、含多边形全部边记录的表，又称ET表，它按y坐标（与扫描线一一对应）递增（或递减）的顺序存放边界区域的所有边。每个y坐标值存放一个或几个边记录。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。随着扫描线从一条到另一条的转换，AET表也应随之变动，利用公式可以算出AET表中x域中的新值xi。凡是与这另一条扫描线相交的任何新边都加到AET表中，而与之不相交的边又被从AET表中删除。活性边表的每个节点的内容：第1项存当前扫描线与边的交点坐标x值；第2项存从当前扫描线到下一条扫描线间

6、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）,存放

7、在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。当某条扫描线yi碰到多边形边界的新边时（以边线低端为准），则在ET表中相应的y坐标值处写入一个边记录。当同时有多条边进入时，则在ET表中按链表结构写入相应数目的多个记录，这些记录是按边线较低端点的x值增加的顺序排列。当没有新边加入时，表中对应的y坐标值储存内容为空。注意：在ET表中：1、与x轴平行的边不记录;2、多边形的顶点分为两大类，一类是局部极值点，另一类是非极值点。当扫描线与第一类顶点相遇时，应看作两个点；当扫描线与第二类顶点相遇时，应视

8、为一个点。3.算法过程（1）根据给出的顶点坐标数据，按y递增顺序建立ET表。（2）根据AET指针，使之为空。１５（3）使yi=ymin（ymin为顶点