扫描线多边形填充算法

1、12022-3-3 我们知道多边形是常用基本图形，它是由一组边围我们知道多边形是常用基本图形，它是由一组边围成，封闭区域，多边形也可以是凸、凹或是带空洞。多成，封闭区域，多边形也可以是凸、凹或是带空洞。多边形区域填充就是将区域内的像素置成新的颜色值或图边形区域填充就是将区域内的像素置成新的颜色值或图案。由于任何一个封闭曲线都可以用多边形来逼近，所案。由于任何一个封闭曲线都可以用多边形来逼近，所以多边形填充实用面广。以多边形填充实用面广。 一、多边形区域填充一、多边形区域填充 3.4.2 扫描线多边形填充算法扫描线多边形填充算法演示演示22022-3-31 1区域内部点判断准则区域内部点判断准则

2、 区域填充首先判断一个像素点是否处于多边形区域内区域填充首先判断一个像素点是否处于多边形区域内, ,其判其判断准则如下：断准则如下： 从该点向无穷远处引出一条射线（也称扫描线），若射线与从该点向无穷远处引出一条射线（也称扫描线），若射线与区域边界交点目标数目为奇数，则此点在区域内。若射线与区区域边界交点目标数目为奇数，则此点在区域内。若射线与区域边界交点目标数目为偶数，则此点为区域外点。域边界交点目标数目为偶数，则此点为区域外点。例如：例如：A A点向右引射线点向右引射线与区域边界共与区域边界共3 3个交点，为内点个交点，为内点B B点向右引射线点向右引射线与区域边界共与区域边界共2 2个交点

3、，为外点个交点，为外点AB32022-3-3此时应注意两点：此时应注意两点：（1 1）当扫描线与多边形相交如下情况时）当扫描线与多边形相交如下情况时: :YXAIBEDCF若两相邻边与扫描线相交于同一点，且两边位于扫描线同侧若两相邻边与扫描线相交于同一点，且两边位于扫描线同侧，则视为两个交点。，则视为两个交点。如如y yb b：1 1点向右交点为点向右交点为3 3个（奇数）是内点个（奇数）是内点 3 3点向右交点为点向右交点为4 4个（偶数）是外点个（偶数）是外点若两相邻边与扫描线相交于同一点，且两边位于扫描线异侧若两相邻边与扫描线相交于同一点，且两边位于扫描线异侧，则视为一个交点。，则视为一

4、个交点。如如y ya ay yb b31y ya a42022-3-3（2 2）当扫描线重合多边形某条边界水平线时，如该水平）当扫描线重合多边形某条边界水平线时，如该水平边线前后两条边线是一上一下的，则该水平边线两个端点边线前后两条边线是一上一下的，则该水平边线两个端点作为一个交点，即扫描线与该水平边界线相交了一次。作为一个交点，即扫描线与该水平边界线相交了一次。 如下图如下图yCBXYDCBAE如该水平边线前后两条边线是同为上或同为下的，则将该水平边如该水平边线前后两条边线是同为上或同为下的，则将该水平边线两个端点作为交点，即扫描线与该水平边界线相交了两次。如线两个端点作为交点，即扫描线与该

5、水平边界线相交了两次。如yDEyCByDE52022-3-3 2 2边相关性及边记录边相关性及边记录 很显然，不能利用区域内部点判别准则对显示平面很显然，不能利用区域内部点判别准则对显示平面上每个点逐个判别，这样计算量太大。上每个点逐个判别，这样计算量太大。 事实上，相对于一个给定多边形区域来说，显示平事实上，相对于一个给定多边形区域来说，显示平面上每个像素点内外特性是互相关联的。相邻像素间具面上每个像素点内外特性是互相关联的。相邻像素间具有相关属性。在实施多边形填充时，利用扫描线相关性，有相关属性。在实施多边形填充时，利用扫描线相关性，就无需对扫描线上所有像素点逐个地进行内外特性判断，就无需

6、对扫描线上所有像素点逐个地进行内外特性判断，只需对一条扫描线从左到右求出该扫描线与区域边界交只需对一条扫描线从左到右求出该扫描线与区域边界交点，这些交点必将扫描线分成内外交替线段，这些交点点，这些交点必将扫描线分成内外交替线段，这些交点x x值大小依次排列。值大小依次排列。 62022-3-3XYAB CD如上图，按如上图，按x x从小到大排列为从小到大排列为A B C DA B C D交点交点ABAB间线段上像素点必在区域内。间线段上像素点必在区域内。所以所以关键是求交点关键是求交点。72022-3-3 （1 1）交点计算）交点计算 多边形填充首先需要求出扫描线与边界的交点，利用边的相关多边

7、形填充首先需要求出扫描线与边界的交点，利用边的相关性可以简单有效地解决这个问题。当一条扫描线性可以简单有效地解决这个问题。当一条扫描线y yi i 与多边形的某一与多边形的某一边线有交点时，其相邻扫描线边线有交点时，其相邻扫描线y yi+1i+1一般也与该边线相交（除非一般也与该边线相交（除非y yi+1i+1超超出了该边线所在区间），出了该边线所在区间），而且扫描线而且扫描线y yi+1i+1与该边线的交点，很容易从与该边线的交点，很容易从前一条扫描线前一条扫描线y yi i与该边的交点递推求得。与该边的交点递推求得。 设某条直线边的方程为设某条直线边的方程为 y=mx+by=mx+b 该边

8、两个端点坐标为（该边两个端点坐标为（x x1 1, ,y y1 1) )、（、（x x2 2, ,y y2 2) ) 且且x x1 1x x2 2 则该边斜率为则该边斜率为m=(m=(y y2 2- -y y1 1)/()/(x x2 2- -x x1 1) ) 令扫描线令扫描线y yi i与该边交点为（与该边交点为（x xi i，y yi i） 扫描线扫描线y yi i1 1与该边交点（与该边交点（x xi i1 1，y yi i1 1）82022-3-3 A(8,2)C(8,8)B(3,7)yi(x xi,i,y yi i)边线边线ABAB第第y yi i条扫描线条扫描线与某边线与某边线A

9、BAB的的交点是交点是( (x xi i,y,yi i) ) 第第y yi+1i+1条扫描线条扫描线与与ABAB的交点为（的交点为（x xi+1i+1, y, yi+1i+1 ）则第则第y yi+1i+1条扫描线与条扫描线与ABAB的交点为的交点为y yi+1i+1= =y yi i+1, +1, x xi+1i+1= =x xi i+1/m +1/m 即由前一条即由前一条扫描线交点扫描线交点X Xi i，Y Yi i求下一条扫描线交点求下一条扫描线交点X Xi i1 1，Y Yi+1,i+1,式中，式中，m m是这条边的是这条边的斜率。斜率。（x xi+1i+1, y, yi+1i+1)边线

10、边线ACACmxmbbmxmbymbyxbmxyybmxyiiiiiiiiii/1/)1(/)1(/)()2(1)1(1111 1/myi+192022-3-3（2 2）边记录）边记录利用边的这种相关性，不必算出边线与各条扫描线的全利用边的这种相关性，不必算出边线与各条扫描线的全部交点，只需以边线为单位，对每条边建立一个边记录，部交点，只需以边线为单位，对每条边建立一个边记录，其内容包括：其内容包括：该边该边y y的最大值的最大值y ymax max , ,该边底端的该边底端的x x坐标坐标x xi i, ,从一条扫描线到下一条扫描线间的从一条扫描线到下一条扫描线间的x x增量增量1/1/m,

11、m,以及指示以及指示下一个边记录地址的指针下一个边记录地址的指针 7 8 18 8 0ABACymax xi 1/m ymax xi 1/m A(8,2)C(8,8)B(3,7)102022-3-33 3边表边表ETET和活动边表和活动边表AET AET （1 1）边表边表ET ET （EdgeEdge Table)Table)边表是一个包含多边形全部边记录的表，它按边表是一个包含多边形全部边记录的表，它按y y坐标（与扫描线坐标（与扫描线一一对应）递增（或递减）的顺序存放区域边界的所有边。每一一对应）递增（或递减）的顺序存放区域边界的所有边。每个个y y坐标值存放一个或者说几个边记录。当某条

12、扫描线坐标值存放一个或者说几个边记录。当某条扫描线y yi i碰到多碰到多边形边界的新边时（边形边界的新边时（以边线底端为准以边线底端为准），则在），则在ETET表中相应的表中相应的y y坐坐标值处写入一个边记录。当同时有多条边进入时，则在标值处写入一个边记录。当同时有多条边进入时，则在ETET表中表中按链表结构写入相应数目的多个记录，按链表结构写入相应数目的多个记录，这些记录是按边线较低这些记录是按边线较低端点的端点的x x值增加的顺序排列值增加的顺序排列。当没有新边加入时，表中对应的。当没有新边加入时，表中对应的y y坐标值处存储内容为空白。坐标值处存储内容为空白。图图4 4. .4 40

13、 0 多多边边形形P P1 1P P5 5P P4 4P P3 3P P2 2O O1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 81 12 23 34 45 56 67 7 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6- -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?ymax xi 1/m 112022-3-3注

14、意：注意：在在ETET表中：与表中：与x x轴平行的边不计入。多边形的顶点轴平行的边不计入。多边形的顶点分为两大类：一类是局部极值点，如下图中的分为两大类：一类是局部极值点，如下图中的P P1 1、P P3 3；另一类另一类是非极值点，如下图中的是非极值点，如下图中的P P2 2、P P4 4、P P5 5。当扫描线与第一类顶点当扫描线与第一类顶点相遇时，应看作两个点；当扫描线与第二类顶点相遇时，应相遇时，应看作两个点；当扫描线与第二类顶点相遇时，应视为一个点。视为一个点。 7 7 2 24 4 7 7 8 8- -1 1 6 6 2 20 0 3 3 6 6 - -2 25 5 6 6 0

15、0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?图图4 4. .4 40 0 多多边边形形P P1 1P P5 5P P4 4P P3 3P P2 2O O1 12 23 34 45 56 67 78 81 12 23 34 45 56 67 7 多边形边表多边形边表多边形边表边表多边形边表边表ymax xi 1/m 122022-3-3活动边表活动边表AET(Activities Ed

16、geAET(Activities Edge Table)Table) 活动边表活动边表AETAET是一个只与当前扫描线相交的边记录链表是一个只与当前扫描线相交的边记录链表。随着。随着扫描线从一条到另一条的转换，扫描线从一条到另一条的转换，AETAET表也应随之变动，利用表也应随之变动，利用 y yi+1i+1= =y yi i+1, +1, x xi+1i+1= =x xi i+1/m+1/m 可以算出可以算出AETAET表中表中x x域中的新值域中的新值x xi i。凡是与这一条扫描线相交的凡是与这一条扫描线相交的任何新边都加到任何新边都加到AETAET表中，而与之不相交的边又被从表中，而与

17、之不相交的边又被从AETAET表中删除表中删除掉了。下图列出了多边形图在扫描线为掉了。下图列出了多边形图在扫描线为4 4、5 5、6 6时的时的AETAET表。表。AETAET表表中的记录顺序仍是按中的记录顺序仍是按x x增大排序的。增大排序的。 6 62 20 0P P4 4P P5 5A AE ET T指指针针5 5 7 7. .5 5 0 0. .5 5 P P3 3P P2 2扫扫描描线线 4 46 62 20 0P P4 4P P5 5A AE ET T指指针针7 78 8- -1 1 P P2 2P P1 1扫扫描描线线 5 57 72 24 4P P5 5P P1 1A AE E

18、T T指指针针7 77 7- -1 1 P P2 2P P1 1扫扫描描线线 6 6图图4 4. .4 42 2 活活动动边边表表图图 4 4. .4 40 0 多多 边边 形形P P 1 1P P 5 5P P 4 4P P 3 3P P 2 2O O 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 81 12 23 34 45 56 67 7132022-3-34 4多边形区域填充算法过程多边形区域填充算法过程 （1 1）根据给出的顶点坐标数据，按）根据给出的顶点坐标数据，按y y递增顺序建立递增顺序建立ETET表表（2 2）根据）根据AETAET指针，使之为空。指针，使之为空

19、。（3 3）使）使y=Yy=Yminmin （Y Yminmin为顶点坐标中最小为顶点坐标中最小y y值）。值）。（4 4）反复做下述各步，直至）反复做下述各步，直至y=Yy=Ymaxmax（顶点坐标中顶点坐标中y y的最的最大值）或大值）或ETET与与AETAET为空：为空： 将将ETET表加入到表加入到AETAET中，并保持中，并保持AETAET链中的记录按链中的记录按x x值值 增大排序。增大排序。 对扫描线对扫描线y yi i依次成对取出依次成对取出AETAET中中x xi i值，并在每对值，并在每对x xi i 之间填上所要求的颜色或图案。之间填上所要求的颜色或图案。 从从AETAE

20、T表中删去表中删去y yi i=y=ymaxmax的记录。的记录。 对保留下来的对保留下来的AETAET中的每个记录，用中的每个记录，用x xi i+1/m+1/m代替代替x xi i ，并重新按并重新按x x递增排序。递增排序。 使使y yi i+1+1，以便进入下一轮循环。以便进入下一轮循环。142022-3-3P1P5P4P3P2O123456781234567图4.40 多边形开始开始y y1 1，将将ETET表中表中y y1 1结点加入至结点加入至AETAET表，同时保持表，同时保持AETAET链中记录按链中记录按x x增大排增大排序序3 6 -25 6 0.5 AET由于上例中是由

21、于上例中是6 66 6，是顶点，是顶点，所以中间不填像素颜色。所以中间不填像素颜色。上例由于上例由于Y Ymaxmax3 3和和5 5，所以不必删去，当，所以不必删去，当y yi i3 3时，此时时，此时就得将第一个结点即（就得将第一个结点即（3 3，6 6，2 2）删去。）删去。对保留下来的对保留下来的AETAET中的每个记录，用中的每个记录，用x xi i+1/m+1/m代替代替x xi i，并重新按并重新按x x递增排序。如上例变成递增排序。如上例变成( (实际求出实际求出y=2y=2时新的交点时新的交点x x坐标）：坐标）：3 4 -2 5 6.5 0.5 AET 7 72 24 4

22、7 78 8- -1 1 6 62 20 0 3 36 6- -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5 P P1 1P P2 2 P P1 1P P4 4 P P5 5P P3 3 P P4 4P P3 3 P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?152022-3-3使使y yi i+1+1，以便进入下一轮循环。即以便进入下一轮循环。即y y2 2再进入以上循环再进入以上循环继续：由继续：由y y2 2，ETET表中是空，所以不需表中是空，所以不需ETET表加入表加入AETAET表表 取取

23、x x4 4和和x x6.5,6.5,将将4 46.56.5之间填上像素颜色之间填上像素颜色。 由于由于y=2,y=2,不必删去结点。不必删去结点。 再改变再改变x xi i的值为的值为 使使y yi i 3 3，重复继续。继续：由重复继续。继续：由y y3 3，将将ETET表中表中y y3 3结点加入，即结点加入，即 将将2 27 7之间填上像素颜色之间填上像素颜色。 删去结点删去结点Y Ymaxmax3 3 结点。结点。3 2 -2 5 7 0.5 AET3 2 -25 7 0.5 AET6 2 06 2 05 7 0.5 AETP1P5P4P3P2O123456781234567图4.4

24、0 多边形 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6 - -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?3 4 -2 5 6.5 0.5 AET162022-3-3 再改变再改变x xi i的值为的值为 使使y yi i 4 4，重复继续。重复继续。 6 2 05 7.5 0.5 AETP1P5P4P3P2O12345678

25、1234567图4.40 多边形 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6- -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5 P P1 1P P2 2 P P1 1P P4 4 P P5 5P P3 3 P P4 4P P3 3 P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?172022-3-3P0P1P2P3P4P5举例举例演示演示182022-3-3二、二、 边填充边填充 边填充算法的基本原理是：边填充算法的基本原理是：（1 1）对多边形的每条边进行直线扫描转

26、换，即对多边形边）对多边形的每条边进行直线扫描转换，即对多边形边界经过的像素打上边标志；界经过的像素打上边标志；（2 2）对多边形内部进行填充。填充时，对每条扫描线，依）对多边形内部进行填充。填充时，对每条扫描线，依从左到右的顺序，逐个访问扫描线上的像素，用一个布尔量从左到右的顺序，逐个访问扫描线上的像素，用一个布尔量来标志当前点是在多边形内部还是外部（一开始设布尔量的来标志当前点是在多边形内部还是外部（一开始设布尔量的值为假，当碰到设有边标志的点时，就把其值取反；对没有值为假，当碰到设有边标志的点时，就把其值取反；对没有边标志的点，则其值保持不变）边标志的点，则其值保持不变）（3 3）将其布

27、尔量值为）将其布尔量值为“真真”的内部置为图形色，把其布尔的内部置为图形色，把其布尔量的值为量的值为“假假”的外部点置为底色即可。的外部点置为底色即可。 192022-3-3三、三、 种子填充种子填充 1 1、种子填充基本思路、种子填充基本思路 首先假设在多边形区域的内部，至少有一个像素点（称为种子）首先假设在多边形区域的内部，至少有一个像素点（称为种子）是已知的，然后算法开始搜索与种子点相邻且位于区域内的其它像是已知的，然后算法开始搜索与种子点相邻且位于区域内的其它像素。如果相邻点不在区域内，那么到达区域的边界；如果相邻点位素。如果相邻点不在区域内，那么到达区域的边界；如果相邻点位于区域内，

28、那么这一点就成为新的种子点，然后继续递归地搜索下于区域内，那么这一点就成为新的种子点，然后继续递归地搜索下去。去。 区域的连通情况可以分为四连通和八连通两种区域的连通情况可以分为四连通和八连通两种四连通区域：各像素在水平和垂直四个方向上是连通的四连通区域：各像素在水平和垂直四个方向上是连通的. .八连通区域八连通区域：各像素在水平、垂直以及四个对角线方向上都是连通的。：各像素在水平、垂直以及四个对角线方向上都是连通的。 202022-3-3 在种子填充算法中，如果允许从四个方向搜寻下一在种子填充算法中，如果允许从四个方向搜寻下一个像素点，则该算法称为四向算法；如果允许从八个方个像素点，则该算法

29、称为四向算法；如果允许从八个方法搜寻下一个像素点，则该算法称为八向算法。法搜寻下一个像素点，则该算法称为八向算法。 一个八向算法可以用在四连通区域的填充上，也可一个八向算法可以用在四连通区域的填充上，也可用在八连通区域的填充上；而一个四向算法只能用于填用在八连通区域的填充上；而一个四向算法只能用于填充四连通区域。充四连通区域。 无论是四向算法还是八向算法，它们的填充算法基无论是四向算法还是八向算法，它们的填充算法基本思想是相同的。为简单起见，下面只讨论四向种子填本思想是相同的。为简单起见，下面只讨论四向种子填充算法。充算法。 212022-3-3222022-3-3232022-3-3边界填充

30、算法（四连通域）边界填充算法（四连通域） 在区域有一个像素是已知（在区域有一个像素是已知（种子像素种子像素），由此像素），由此像素从从四个方向四个方向遍历区域内所有像素。（适用于交互绘图）遍历区域内所有像素。（适用于交互绘图）0 1 2 3 4 54321用什么方法实现？用什么方法实现？注意：242022-3-3取取(x,y)为种子点为种子点Void BoundaryFill4(int x,int y ,int boundarycolor,int newcolor) if(getpixel(x,y)!= boundarycolor & getpixel(x,y)!= newcolor)

31、 /* getpixel(x,y)取屏幕上像素(x,y)的颜色*/ putpixel(x,y,newcolor);/着色 BoundaryFill4(x-1,y, boundarycolor, newcolor); BoundaryFill4(x,y+1, boundarycolor, newcolor); BoundaryFill4(x+1,y, boundarycolor, newcolor); BoundaryFill4(x,y-1, boundarycolor, newcolor); 252022-3-3262022-3-3272022-3-3Void FloodFill4(int x

32、,int y ,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /* getpixel(x,y)取屏幕上像素(x,y)的颜色, oldcolor为区域的原色*/ putpixel(x,y,newcolor);/着色 FloodFill4(x-1,y, oldcolor, newcolor); FloodFill4(x,y+1, oldcolor, newcolor); FloodFill4(x+1,y, oldcolor, newcolor); FloodFill4(x,y-1, oldcolor, newcolor); 取取(x,y

33、)为种子点为种子点282022-3-3种子填充法种子填充法292022-3-3上述简单种子填充算法操作过程非常简单，却要进行深上述简单种子填充算法操作过程非常简单，却要进行深度的递归，这不仅要花费许多时间，降低了算法的效率度的递归，这不仅要花费许多时间，降低了算法的效率，而且还要花费许多空间要构造堆栈结构。因此出现了，而且还要花费许多空间要构造堆栈结构。因此出现了改进的扫描线种子填充算法。改进的扫描线种子填充算法。(3)(3)扫描线种子填充算法扫描线种子填充算法 扫描线种子填充算法适用于边界定义的四连通区域。区域扫描线种子填充算法适用于边界定义的四连通区域。区域可凹可凸，还可以包括一个或多个孔

34、。在边界定义区域外或与可凹可凸，还可以包括一个或多个孔。在边界定义区域外或与其邻接的区域中像素的值或颜色不同于填充区域或多边形的值其邻接的区域中像素的值或颜色不同于填充区域或多边形的值或颜色。或颜色。 算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一算法思想：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。反复进行这个过程，直到所保存的每个