第4章多边形的转换与区域填充

1、第第4章章 多边形的扫描转换与区域填充多边形的扫描转换与区域填充第第4章章 多边形的扫描转换与区域填充多边形的扫描转换与区域填充一、在计算机图形学中，多边形有两种重要的表示方法：一、在计算机图形学中，多边形有两种重要的表示方法：1.1.顶点表示顶点表示u用多边形的顶点序列来刻画多边形用多边形的顶点序列来刻画多边形u顶点表示特点顶点表示特点表示方法直观，几何意义强，占内存空间少，但没指明哪些像素在表示方法直观，几何意义强，占内存空间少，但没指明哪些像素在多边形内，不能直接用于着色。多边形内，不能直接用于着色。 多边形的顶点表示多边形的顶点表示第第4章章 多边形的扫描转换与区域填充多边形的扫描转换

2、与区域填充2.2.点阵表示点阵表示v用位于多边形内部或边界上的像素集合来刻画多边形用位于多边形内部或边界上的像素集合来刻画多边形v点阵表示特点点阵表示特点会失去很多重要的几何信息，不过它是光栅显示系统显会失去很多重要的几何信息，不过它是光栅显示系统显示面着色时所需的图形表示形式。示面着色时所需的图形表示形式。多边形的点阵表示多边形的点阵表示第第4章章 多边形的扫描转换与区域填充多边形的扫描转换与区域填充二、多边形填充方式二、多边形填充方式1.多边形扫描转换多边形扫描转换：顶点表示不能直接用于显示，必须要进行从多边形顶点表示到点阵表顶点表示不能直接用于显示，必须要进行从多边形顶点表示到点阵表示的

3、转换，这种转换就是给多边形包围的区域着色的过程，即从多边示的转换，这种转换就是给多边形包围的区域着色的过程，即从多边形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色值写入帧缓存中相应的单元。主要用来填充多边形区域以及由多边形值写入帧缓存中相应的单元。主要用来填充多边形区域以及由多边形拟合的其他简单曲线区域。拟合的其他简单曲线区域。2.区域填充：区域填充：从给定的位置开始涂描直到指定的边界为止。用在具有复杂形状边界从给定的位置开始涂描直到指定的边界为止。用在具有复杂形状边界的多边形以及交互式绘图系统中。的多边形以及交互式绘图

4、系统中。第第4章章 多边形的扫描转换与区域填充多边形的扫描转换与区域填充n4.1 矩形填充矩形填充n4.2 多边形扫描转换多边形扫描转换n4.3 区域填充区域填充n4.4 多边形扫描转换与区域填充的区别多边形扫描转换与区域填充的区别n4.5 光栅图形的反走样光栅图形的反走样4.1 矩形填充为了将它用指定的颜色均匀填充，只要填充从为了将它用指定的颜色均匀填充，只要填充从y yminmin到到y ymaxmax每条扫每条扫描线位于描线位于x xminmin和和x xmaxmax之间的区段就可以。其程序如下：之间的区段就可以。其程序如下：4.1 矩形填充为了减少函数调用的次数，每条扫描线上的为了减少

5、函数调用的次数，每条扫描线上的xxminmin，x xmaxmax 区间可区间可以用画线函数填充，其程序如下：以用画线函数填充，其程序如下：4.1 矩形填充存在问题：存在问题：如果两个矩形共享一条边：如果两个矩形共享一条边：（1 1）如果象素的中心落在某个矩形区域内，则它属于该区域。）如果象素的中心落在某个矩形区域内，则它属于该区域。（2 2）如果将中心落在其共享边界的像素看成是同时属于两个矩形）如果将中心落在其共享边界的像素看成是同时属于两个矩形图元区域，那么，落在共享边界上的像素就会被重画两次。图元区域，那么，落在共享边界上的像素就会被重画两次。（3 3）如果将中心落在其共享边界的像素看成

6、是不属于任何区域，）如果将中心落在其共享边界的像素看成是不属于任何区域，那么，中心落在共享边界上的像素就会被丢失。那么，中心落在共享边界上的像素就会被丢失。处理措施：处理措施：如果像素的中心落在矩形边界的左方或下方时，该像素属于矩形，如果像素的中心落在矩形边界的左方或下方时，该像素属于矩形，否则不属于该多边形区域，也就是说，如果象素的中心落在矩形否则不属于该多边形区域，也就是说，如果象素的中心落在矩形边界的右方或上方时，该象素不属于矩形区域。边界的右方或上方时，该象素不属于矩形区域。4.2 多边形扫描转换4.2.1 逐点判断算法n基本思想基本思想：v逐个判断绘图窗口内的像素，确定它们是否在多边

7、形区逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。实现域内部，从而求出位于多边形区域内的像素的集合。实现扫描转换多边形最简单方法就是逐点判断。扫描转换多边形最简单方法就是逐点判断。n实质：实质：进行多边形对平面上点的包含性检查进行多边形对平面上点的包含性检查n常用方法常用方法：n射线法射线法n弧长法弧长法4.2.1 逐点判断算法1.1.射线法射线法基本思想：基本思想：v由被测点向某方向作射线，计算此射线与多边形所有边由被测点向某方向作射线，计算此射线与多边形所有边的的交点个数交点个数，用交点分布的，用交点分布的奇偶性奇偶性判别多边形与点的关系。判

8、别多边形与点的关系。判断依据：判断依据：v若交点个数为奇数，则被测点在多边形内部；若交点个若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数（包括数为偶数（包括0 0），则该点在多边形的外部。），则该点在多边形的外部。acbdabdc4.2.1 逐点判断算法一、射线法一、射线法问题：问题：当射线恰好通过多边形的顶点时，怎么判断当射线恰好通过多边形的顶点时，怎么判断？v 射线射线f f过顶点，若将交点计数为过顶点，若将交点计数为2 2，则则f f点在多边形外。点在多边形外。v 但若规定射线过顶点时，计数为但若规定射线过顶点时，计数为1 1，则则e e在多边形内。在多边形内。efef1234

9、5ab4.2.1 逐点判断算法点点a a: 0: 0个交点，在多边形外个交点，在多边形外点点b b: 1: 1个交点，在多边形内个交点，在多边形内点点c c：3 3个交点，在多边形内个交点，在多边形内点点d d: 1: 1个交点，在多边形内个交点，在多边形内点点e e: 2: 2个交点，在多边形外个交点，在多边形外点点f f: 1: 1个交点，在多边形内（剔除重合边）个交点，在多边形内（剔除重合边）f一、射线法一、射线法n措施：措施：v在射线左边的边与该射线相交时交点有效，应计数；而在射在射线左边的边与该射线相交时交点有效，应计数；而在射线右边的边与射线相交时交点无效，不计数。（线右边的边与射

10、线相交时交点无效，不计数。（左闭右开原则左闭右开原则）4.2.1 逐点判断算法二、弧长法二、弧长法n要求要求多边形由有向边组成，即规定沿多边形各边的走向其左侧（或多边形由有向边组成，即规定沿多边形各边的走向其左侧（或右侧）为多边形的内部。右侧）为多边形的内部。n思想思想以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其在单位圆上弧长的代数和。并计算其在单位圆上弧长的代数和。n判断方法判断方法如果代数和为如果代数和为0，则被测点在多边形之外，若代数和为，则被测点在多边形之外，若代数和为2 ，则，则被测点在多边形之内。被测点在多

11、边形之内。n其他其他对于内部有空洞的多边形，只要按照上述规定来定义多边形的对于内部有空洞的多边形，只要按照上述规定来定义多边形的有向边，则可以采用同样的测试方法。有向边，则可以采用同样的测试方法。4.2.1 逐点判断算法二、弧长法二、弧长法点点p在多边形外部在多边形外部点点p在多边形内部在多边形内部4.2.1 逐点判断算法算法实现：算法实现：v用函数用函数insideinside（polygonpolygon，x x，y y）来测试被测点（）来测试被测点（x x，y y）的）的位置；位置；v函数返回函数返回“真真”值，即可对多边形内部的点进行填充。值，即可对多边形内部的点进行填充。算法特点：算

12、法特点：v简单简单v速度慢速度慢v算法割断了像素间的联系，孤立地考察各个像素与多边形的内算法割断了像素间的联系，孤立地考察各个像素与多边形的内外关系，使得绘图窗口内的每一个像素都要一一判别，每次判外关系，使得绘图窗口内的每一个像素都要一一判别，每次判别又需要大量的运算，所以效率很低。别又需要大量的运算，所以效率很低。4.2.2 扫描线填充算法一、区域特点：一、区域特点：v一条扫描线上的像素存在着相关性一条扫描线上的像素存在着相关性v在多边形边处，像素性质才发生变化在多边形边处，像素性质才发生变化v将相邻像素放在一起测试，从而减少测试点的数目将相邻像素放在一起测试，从而减少测试点的数目4.2.2

13、 扫描线填充算法二、基本思想二、基本思想v按扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后按扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后判断扫描线上的哪些部分在区域边界之内，再用要求的颜色显示边判断扫描线上的哪些部分在区域边界之内，再用要求的颜色显示边界内的像素。界内的像素。实现：实现：v依次考察各条扫描线，一条扫描线从左至右与多边形的交点是成依次考察各条扫描线，一条扫描线从左至右与多边形的交点是成对出现的，即对出现的，即a a、b b点，点，c c、d d点之间的像素都位于多边形之内，则点之间的像素都位于多边形之内，则a a、b b为一个区段，为一个区段， c c、d d为

14、一个区段。对这些区段内的像素用指定的颜为一个区段。对这些区段内的像素用指定的颜色进行填充后，就完成了该扫描线的填充工作，再继续下一条扫描色进行填充后，就完成了该扫描线的填充工作，再继续下一条扫描线。线。4.2.2 扫描线填充算法一般多边形的填充过程，对于一条扫描线，步骤为：一般多边形的填充过程，对于一条扫描线，步骤为：v求交点：求交点：计算扫描线与多边形各边的交点（计算扫描线与多边形各边的交点（a a、d d、c c、b b）v交点排序：交点排序：把所有交点按递增顺序进行排序把所有交点按递增顺序进行排序(a(a、b b、c c、d)d)v交点配对：交点配对：第一个交点与第二个交点，第三个交点与

15、第四个交点等，第一个交点与第二个交点，第三个交点与第四个交点等，每对交点就代表扫描线与多边形的一个相交区间每对交点就代表扫描线与多边形的一个相交区间(a a、b) (cb) (c、d)d) )v区间填色：区间填色：把这些相交区间内的象素置成多边形颜色，把相交区间外把这些相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。的象素置成背景色。4.2.2 扫描线填充算法扫描线扫描线2 2 与与p1p1相交，相交，p p1,1,p p1 1,e,e扫描线扫描线7 7 与与p6p6相交，相交，p p6 6,f,g,f,g三、存在问题三、存在问题 交点的个数必须是偶数才能保证填充的正确性。交点的

16、个数必须是偶数才能保证填充的正确性。存在问题：存在问题：当扫描线与多边形的顶点相交时，会出现异常情况。当扫描线与多边形的顶点相交时，会出现异常情况。问题问题1：如何取舍交点，保证交点正确配对？：如何取舍交点，保证交点正确配对？4.2.2 扫描线填充算法v 共享顶点的两条边分别落在扫描线两边，共享顶点的两条边分别落在扫描线两边， 取交点取交点1 1次。次。v 共享顶点的两条边均高于扫描线，共享顶点的两条边均高于扫描线， 取交点取交点2 2次。次。v 共享顶点的两条边均低于扫描线，共享顶点的两条边均低于扫描线， 取交点取交点0 0次。次。解决方法：检查两相邻边在扫描线的哪一侧解决方法：检查两相邻边

17、在扫描线的哪一侧。具体实现：具体实现：只需要检查顶点的两条边的另外两个端点的只需要检查顶点的两条边的另外两个端点的y y值，按这两个值，按这两个y y值值中大于交点中大于交点y y值的个数是值的个数是0 0、1 1、2 2来决定交点是取零个、一个、两个。来决定交点是取零个、一个、两个。4.2.2 扫描线填充算法对左下角为（对左下角为（1 1，1 1），右上），右上角为（角为（3 3，3 3）的正方形填充）的正方形填充存在问题：存在问题：多边形边界上像素的取舍问题。多边形边界上像素的取舍问题。问题问题2：避免填充扩大化？：避免填充扩大化？4.2.2 扫描线填充算法解决方法解决方法：规定落在右：规

18、定落在右/上边界的象素不予填充，而落在左上边界的象素不予填充，而落在左/下下边界的象素予以填充。边界的象素予以填充。具体实现具体实现：对扫描线与多边形的相交区间，对扫描线与多边形的相交区间， 取取“左闭右开左闭右开”，如【，如【2 2，9 9） 问题问题1 1保证了多边形的保证了多边形的“下闭上开下闭上开”4.2.2 扫描线填充算法 为了求出扫描线与多边形边的交点，最简单的方法是将多边形为了求出扫描线与多边形边的交点，最简单的方法是将多边形的所有边放在一个表中的所有边放在一个表中, ,称之为称之为边表边表，在处理每条扫描线时，从表，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描

19、线的交点。这样做的结中顺序取出所有的边，分别求这些边与扫描线的交点。这样做的结果将做一些无益的求交点动作，因为扫描线并不一定与多边形的边果将做一些无益的求交点动作，因为扫描线并不一定与多边形的边相交，扫描线只与部分甚至较少的边相交；因此，在进行扫描线与相交，扫描线只与部分甚至较少的边相交；因此，在进行扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。我们把多边形边求交点时，应只求那些与扫描线相交的边的交点。我们把与当前扫描线相交的边称为与当前扫描线相交的边称为活性边活性边，并把它们按与扫描线交点，并把它们按与扫描线交点 x x 坐标递增的顺序存放在一个链表中，称此链表为坐标递增的顺序

20、存放在一个链表中，称此链表为活性边表活性边表。 四、求交点的方法四、求交点的方法4.2.2 扫描线填充算法四、求交点的方法四、求交点的方法1.边表（边表（et）所以，所以，etet的意义在于为扫描线提供待加入的新边信息。的意义在于为扫描线提供待加入的新边信息。 边的分类表可以这样建立：先按下端点的纵坐标值对所有边作桶分类，再将同一组中的边按下端点x坐标递增的顺序进行排序。 1： p2p1p2p32： p1p63： p3p44：5： p5p6p5p4扫描线y=4.2.2 扫描线填充算法假设当前扫描线与多边形的某一条边的交点坐标为假设当前扫描线与多边形的某一条边的交点坐标为x x，那么下一条，那么

21、下一条扫描线与该边的交点不必从头计算，只要加上一个增量即可。扫描线与该边的交点不必从头计算，只要加上一个增量即可。设边设边abab的斜率为的斜率为m m，若其与扫描线，若其与扫描线y yi i的交点横坐标为的交点横坐标为x xi i，则与扫描线，则与扫描线y yi i1 1的交点的横坐标为：的交点的横坐标为： x xi i1 1x xi i1/m1/m2.活性边表活性边表(aet)4.2.2 扫描线填充算法2.活性边表活性边表 活性边表的结点中至少应为对应边保存如下内容：活性边表的结点中至少应为对应边保存如下内容：ymaxymax：边所交的最高扫描线号；：边所交的最高扫描线号；x x：边与当前

22、扫描线的交点的：边与当前扫描线的交点的x x坐标；坐标；xx：从当前扫描线到下一个扫描线之间的：从当前扫描线到下一个扫描线之间的x x增量；增量； 实际上该数据表示了一条扫描线与某条边的交点，将这些交点链接实际上该数据表示了一条扫描线与某条边的交点，将这些交点链接起来，就可以直接得到要求的所有交点。在填充过程中，为每一条起来，就可以直接得到要求的所有交点。在填充过程中，为每一条扫描线建立相应的活性边表，它表示了该扫描线要求交点的那些边，扫描线建立相应的活性边表，它表示了该扫描线要求交点的那些边，在实用中每一条边的活性边表的信息与上一条边的活性边表的信息在实用中每一条边的活性边表的信息与上一条边

23、的活性边表的信息有继承性，再结合有继承性，再结合etet表使得建立十分方便。表使得建立十分方便。 4.2.2 扫描线填充算法4.2.2 扫描线填充算法五五. .扫描线算法步骤扫描线算法步骤4.2.2 扫描线填充算法六、扫描线算法特点六、扫描线算法特点1.1.数据结构和算法本身要比逐点判断算法复杂数据结构和算法本身要比逐点判断算法复杂2.2.速度比逐点判断算法快得多速度比逐点判断算法快得多u利用边的连贯性来加速交点的计算u利用aet以排除盲目求交u利用扫描线的连贯性以避免逐点判别4.2.3 边缘填充算法求余运算求余运算：假设假设a a为一个给定的正数，则数为一个给定的正数，则数m m的余数定义为

24、的余数定义为a am m，记为，记为mm。当计算机内。当计算机内用用n n位二进制表示位二进制表示m m时，可取时，可取a a2 2n n1 1，易知，易知mmm m，即对，即对m m作偶数次求余运作偶数次求余运算，其结果是算，其结果是m m；而对；而对m m作奇数次求余运算的结果是作奇数次求余运算的结果是mm。这一规律应用到多。这一规律应用到多边形的扫描转换，就称为边形的扫描转换，就称为边缘填充算法边缘填充算法。即假设屏幕上某区域内象素的颜色为即假设屏幕上某区域内象素的颜色为m m，则对该区域内象素颜色作偶数次求，则对该区域内象素颜色作偶数次求余运算后，该区域内象素的颜色保持不变，而做奇数次

25、求余运算后，该区域余运算后，该区域内象素的颜色保持不变，而做奇数次求余运算后，该区域内象素的颜色变为内象素的颜色变为mm。4.2.3 边缘填充算法 设设x x1 1，x x2 2，,x,xn n（n n为偶数）是扫描线为偶数）是扫描线y y与多边形的交点的与多边形的交点的x x坐标序列，则该坐标序列，则该扫描线上位于多边形内部的象素可按以下步骤求得：扫描线上位于多边形内部的象素可按以下步骤求得：（1 1）将当前扫描线）将当前扫描线y y上的所有象素都初始化为颜色上的所有象素都初始化为颜色m m：（2 2）在当前扫描线上，从横坐标为）在当前扫描线上，从横坐标为xixi（i i1 1，2 2，n

26、n）的交点向右求余）的交点向右求余 扫描线扫描线y y上位于多边形内部的象素都经过了奇数次求余运算，颜色为上位于多边形内部的象素都经过了奇数次求余运算，颜色为m;m;而而位于多边形外部的象素都经过了偶数次求余运算，颜色为位于多边形外部的象素都经过了偶数次求余运算，颜色为m m。这种多边形的扫描。这种多边形的扫描转换称为以转换称为以扫描线为中心的边缘填充算法扫描线为中心的边缘填充算法边为中心的边缘填充算法：边为中心的边缘填充算法：（1 1）将所有象素都初始化为颜色）将所有象素都初始化为颜色m m（2 2）对于多边形的所有边，逐边向右求余，也就是计算扫描线与边的交点，）对于多边形的所有边，逐边向右

27、求余，也就是计算扫描线与边的交点，从交点开始向右取余从交点开始向右取余4.2.3 边缘填充算法边缘填充算法特点：边缘填充算法特点：l用求余运算代替排序用求余运算代替排序l数据结构和程序结构简单数据结构和程序结构简单l需要对帧缓存的大量象素反复赋值需要对帧缓存的大量象素反复赋值l运行速度比扫描线算法慢运行速度比扫描线算法慢算法过程算法过程4.3 区域填充4.3.1 区域的表示n区域指已经表示成点阵形式的填充图形，它是象素的集合。区域指已经表示成点阵形式的填充图形，它是象素的集合。n区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到

28、整个区域的过程。区域填充算法要求区域是连通的整个区域的过程。区域填充算法要求区域是连通的n区域建立和定义的方式：区域建立和定义的方式：n内定义区域：区域内部所有象素具有同一种颜色或亮度值，内定义区域：区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有另一种颜色或亮度值。而区域外的所有象素具有另一种颜色或亮度值。n漫水法：将该区域种的全部象素都设置为新值的算法，即填漫水法：将该区域种的全部象素都设置为新值的算法，即填充内定义的区域充内定义的区域n边界定义区域：边界上所有象素均具有特定的颜色或亮度值，边界定义区域：边界上所有象素均具有特定的颜色或亮度值，而在区域内的象素则具有不是新值的

29、某种颜色或亮度值而在区域内的象素则具有不是新值的某种颜色或亮度值n边界填充算法：将边界定义区域中的全部象素值都设置为新边界填充算法：将边界定义区域中的全部象素值都设置为新值的算法。值的算法。4.3.1 区域的表示 区域填充算法要求区域是连通的，只有在连通的区域中，才有可能将种子点的颜区域填充算法要求区域是连通的，只有在连通的区域中，才有可能将种子点的颜色扩展到区域内的其他点。根据相互连通的定义不同，区域可分为：色扩展到区域内的其他点。根据相互连通的定义不同，区域可分为：n4 4连通：连通：n4 4连通内部表示区域：可以从任一一个象素出发，通过上、下、左、右等连通内部表示区域：可以从任一一个象素

30、出发，通过上、下、左、右等4 4个方向的移动，到达另一个象素。个方向的移动，到达另一个象素。n8 8连通连通n8连通内部表示区域：从任一个象素出发，需要通过水平、垂直、连通内部表示区域：从任一个象素出发，需要通过水平、垂直、对角线等对角线等8种方向的移动，到达另一个象素种方向的移动，到达另一个象素边界定义区域示意图边界定义区域示意图内定义区域示意图内定义区域示意图4.3.2 递归填充算法 1.1.漫水法漫水法基本方法基本方法：设（设（x x，y y）为四连通区域内部的一点，）为四连通区域内部的一点，old_colorold_color为区域内部所有象素为区域内部所有象素的原色。现取（的原色。现

31、取（x x，y y）为种子点，要将整个区域填充为新的颜色）为种子点，要将整个区域填充为新的颜色new_colornew_color。递归填充算法：递归填充算法：先判别象素（先判别象素（x,yx,y）的颜色，若它的值等于）的颜色，若它的值等于old_colorold_color，说明该象素位，说明该象素位于该区域内部，则设置该象素的颜色为于该区域内部，则设置该象素的颜色为new_colornew_color，并对与该象素相邻，并对与该象素相邻的上、下、左、右的上、下、左、右4 4个相邻象素作递归填充；否则说明该象素的颜色在个相邻象素作递归填充；否则说明该象素的颜色在区域外或已被填充过，不再进行处

32、理。区域外或已被填充过，不再进行处理。4.3.2 递归填充算法 2.2.边界填充算法边界填充算法与漫水法的基本思想一样，只是在测试与漫水法的基本思想一样，只是在测试（x，y）点的象素是否处在区域之）点的象素是否处在区域之内同时又未被访问过时，包括两部分的内容：内同时又未被访问过时，包括两部分的内容：（1 1）与边界值相比较，以检测此象素是否为该区域的一部分；）与边界值相比较，以检测此象素是否为该区域的一部分；（2 2）与新值相比较，以决定该象素是否已被访问过。）与新值相比较，以决定该象素是否已被访问过。前提条件：前提条件：在初始状态，区域内没有一个象素已设置为新值。但是允许新值等于在初始状态，

33、区域内没有一个象素已设置为新值。但是允许新值等于边界值。边界值。4.3.2 递归填充算法 2 2、边界填充算法、边界填充算法在区域内测试（在区域内测试（x x，y y）点的象素是否在区域之内同时又未被访问过。一般采）点的象素是否在区域之内同时又未被访问过。一般采用堆栈的方法，对边界定义的区域进行填充，基本流程如下：用堆栈的方法，对边界定义的区域进行填充，基本流程如下：种子象素入栈，当栈非空时，执行如下三步操作：种子象素入栈，当栈非空时，执行如下三步操作： （1 1）栈顶象素出栈；）栈顶象素出栈； （2 2）将出栈象素置成多边形色；）将出栈象素置成多边形色； （3 3）按上、下、左、右的顺序检查

34、与出栈象素相邻的四个象素，若其中）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。某个象素不在边界上且未置成多边形色，则把该象素入栈。4.3.2 递归填充算法6754s1932843210 0 1 2 3 4 5例：种子象素为s1s1s172499 94.3.2 递归填充算法6754s132843210 0 1 2 3 4 5例：种子象素为s1s17249 8填充次序：s19 8 2 3 4 5 6 74.3.2 递归填充算法 算法特点：算法特点：（1 1）算法程序简单，表达清楚）算法程序简单，表达清楚（2 2）需要反复递归，其执行

35、效率并不高）需要反复递归，其执行效率并不高（3 3）未考虑象素间的相关性，而是孤立地对一个个象素进行测试）未考虑象素间的相关性，而是孤立地对一个个象素进行测试为了减少递归次数，相继出现改进的算法，最具代表性的是区域填充的为了减少递归次数，相继出现改进的算法，最具代表性的是区域填充的扫描线算法扫描线算法4.3.3 扫描线区域填充算法 利用了象素之间的连贯性，将扫描线上位于区域内部的相邻象素作利用了象素之间的连贯性，将扫描线上位于区域内部的相邻象素作为一个区域来考虑，只选一个象素作为代表进栈，从而极大地减少为一个区域来考虑，只选一个象素作为代表进栈，从而极大地减少了对栈空间的需求，并且显著地提高了

36、执行效率。了对栈空间的需求，并且显著地提高了执行效率。扫描线算法的基本思想扫描线算法的基本思想:首先填充当前扫描线上位于区域内部的一个区段，它的颜色为首先填充当前扫描线上位于区域内部的一个区段，它的颜色为old_colorold_color，现在将，现在将fill_colorfill_color作为区域填充的新颜色；然后确作为区域填充的新颜色；然后确定与这一区段相邻的上、下两条扫描线上位于区域内部的区段，定与这一区段相邻的上、下两条扫描线上位于区域内部的区段，分别将它们右端象素作为种子点保存起来。反复进行这一过程，分别将它们右端象素作为种子点保存起来。反复进行这一过程，直到保存的区段都填充完毕

37、为止。直到保存的区段都填充完毕为止。4.3.3 扫描线区域填充算法 算法步骤：算法步骤：(1)(1)种子象素压入堆栈种子象素压入堆栈(2)(2)从包含种子象素的堆栈中推出区段的种子象素。从包含种子象素的堆栈中推出区段的种子象素。(3)(3)沿着扫描线，对种子象素的左右象素进行填充，直至遇到边界沿着扫描线，对种子象素的左右象素进行填充，直至遇到边界象素为止；标记区段的左、右端点坐标为象素为止；标记区段的左、右端点坐标为x xl l和和x xr r。(4)(4)在区间在区间xxl l，x xr r 中检查与当前扫描线中检查与当前扫描线y y上、下相邻的两条扫描上、下相邻的两条扫描线上的象素。若存在

38、非边界、未填充的象素，则把每一区间的最线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（右象素作为种子点压入堆栈，返回第（2 2）步。）步。（5 5）堆栈为空时结束。）堆栈为空时结束。上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。算法提高了区域填充的效率。4.3.3 扫描线区域填充算法 上图所示是对四连通边界定义区域进行填充的扫描线算法的执行上图所示是对四连通边界定义区域进行填充的扫描线算法的执行过程，其中过程，其中 表示边界象素。表示边界象素。54321

39、4.4 多边形扫描转换与区域填充的区别 二者联系：二者联系：（1 1）都是光栅图形面着色，用于真实感图形显示。可相互转换。都是光栅图形面着色，用于真实感图形显示。可相互转换。（2 2）当已知顶点表示的多边形内一点作为种子点，并用扫描转换）当已知顶点表示的多边形内一点作为种子点，并用扫描转换直线段的算法将多边形的边界表示成八连通区域后，多边形扫描转直线段的算法将多边形的边界表示成八连通区域后，多边形扫描转换问题就可转化为区域填充问题换问题就可转化为区域填充问题（3 3）若已知给定区域是多边形区域，并且通过一定的方法求出它）若已知给定区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充

40、问题便可以转化为多边形扫描转换问题。的顶点坐标，则区域填充问题便可以转化为多边形扫描转换问题。4.4 多边形扫描转换与区域填充的区别 二者差别：二者差别：（1 1）基本思想不同）基本思想不同多边形扫描转换是指将多边形的顶点表示转换成点阵表示的方法，而多边形扫描转换是指将多边形的顶点表示转换成点阵表示的方法，而区域填充只改编了区域的填充颜色，没有改变区域的表示方法。它们区域填充只改编了区域的填充颜色，没有改变区域的表示方法。它们各自应用的场合不同。各自应用的场合不同。(2)(2)对边界的要求不同对边界的要求不同多边形扫描转换的扫描线算法只要求一条扫描线与多边形边界的交点多边形扫描转换的扫描线算法

41、只要求一条扫描线与多边形边界的交点个数为偶数，所以多边形的边界可以不封闭。而区域填充时，为了防个数为偶数，所以多边形的边界可以不封闭。而区域填充时，为了防止递归填充时跨越区域的边界，要求四连通区域的边界是封闭的八连止递归填充时跨越区域的边界，要求四连通区域的边界是封闭的八连通区域，八连通区域的边界为封闭的四连通区域。通区域，八连通区域的边界为封闭的四连通区域。（3 3）基于的条件不同）基于的条件不同在区域填充算法中，要求给定区域内一点作为种子点，然后从这一点在区域填充算法中，要求给定区域内一点作为种子点，然后从这一点根据连通性将新的颜色扩散到整个区域；而扫描转换多边形是从多边根据连通性将新的颜色扩散到整个区域