第五讲 区域填充.ppt

《第五讲 区域填充.ppt》由会员分享，可在线阅读，更多相关《第五讲 区域填充.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机图形学计算机图形学Computer GraphicsComputer Graphics决不要把你们的学习看成是任务，而要把它当作一个决不要把你们的学习看成是任务，而要把它当作一个令人羡慕的机会，为了你们自己的快乐和今后你们所从事令人羡慕的机会，为了你们自己的快乐和今后你们所从事行业的利益，去学习，去了解精神领域上的美，它具有能行业的利益，去学习，去了解精神领域上的美，它具有能让人自由解放的力量。让人自由解放的力量。爱爱因斯坦因斯坦*教学基本要求：教学基本要求：1.1直直线线的生成算法；的生成算法；1.2圆圆的生成算法；的生成算法；1.3区域填充算法；区域填充算法；1.4裁剪算法。裁剪算法

2、。第三章基本图形生成第三章基本图形生成本本章章讨讨论论的的是是如如何何在在光光栅栅扫扫描描显显示示器器上上构构造造直直线线、圆、填充区域等基本二维几何图形（图元）圆、填充区域等基本二维几何图形（图元）在在光光栅栅扫扫描描显显示示器器上上构构造造二二维维图图形形就就是是要要找找出出最最靠靠近近所所描描述述几几何何图图形形的的那那些些像像素素的的坐坐标标，将将其其置置为为规规定的颜色并放入帧缓存。定的颜色并放入帧缓存。在在光光栅栅显显示示平平面面上上，每每个个像像素素具具有有一一定定的的尺尺寸寸，是是显显示示平平面面上上可可被被访访问问的的最最小小单单位位，它它的的坐坐标标x x和和y y只只能是

3、整数能是整数。直直线线的的两两种种常常用用生生成成算算法法：DDADDA算算法法和和BresenhamBresenham算法；圆的常用生成算法：算法；圆的常用生成算法：中点画圆算法中点画圆算法概念回顾概念回顾教学基本要求：教学基本要求：1.1直直线线的生成算法；的生成算法；1.2圆圆的生成算法；的生成算法；1.3区域填充算法；区域填充算法；1.4裁剪算法。裁剪算法。第三章基本图形生成第三章基本图形生成之前介绍的直线和圆都属于之前介绍的直线和圆都属于线划图线划图（线图元）（线图元）区区域域填填充充属属于于面面着着色色（填填充充图图元元），二二维维的的面面着着色色体体现现逼逼真真的的视视觉觉效效果

4、，是三维多边形面着色的基础。果，是三维多边形面着色的基础。表示一个区域的表示一个区域的要素为：要素为：边界边界（闭合区域）（闭合区域）+填充色填充色（灰度或色彩）（灰度或色彩）区域填充即给出一个闭合区域的边界，要求对边界范围区域填充即给出一个闭合区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。内的所有像素单元赋予指定的颜色代码。因此，区域填充算法的一般步骤如下：因此，区域填充算法的一般步骤如下：确定那些像素位于填充图元的内部；确定那些像素位于填充图元的内部；确定以什么颜色填充这些像素；确定以什么颜色填充这些像素；区域填充的含义区域填充的含义点在多边形内的包含性检验点在多边形内的包

5、含性检验检验夹角之和射线法检验交点数检验夹角之和检验夹角之和若夹角和为0，则点p在多边形外若夹角和为360，则点p在多边形内ABCDEPABCDEP夹角如何计算？夹角如何计算？大小：利用余弦定理方向：令当TBP斜率，为顺时针角当T0时，AP斜率BP斜率，为逆时针角zxABPzxBAP射线法检验交点数射线法检验交点数ABCDEPABCDEP交点数交点数=偶数（包括偶数（包括0）点在多边形之外点在多边形之外交点数交点数=奇数奇数点在多边形之内点在多边形之内zx左闭右开左闭右开多边形填充多边形填充边边界界由由闭闭合合的的线线段段（多多边边形形）组组成成，一一般般由由多多边边形形的顶点序列来表示多边形

6、。的顶点序列来表示多边形。种子填充种子填充边界由边界色给出。边界由边界色给出。主要介绍以下两种区域填充方式：主要介绍以下两种区域填充方式：填充条件填充条件多边形的顶点序列多边形的顶点序列(P(Pi i，i=0i=0，1 1，n)n)、填充色。、填充色。多边形内点的判别准则多边形内点的判别准则对对多多边边形形进进行行填填充充，关关键键是是找找出出多多边边形形内内的的像像素素。即即首首要要问问题题是是判判断断一一个个像像素素是是在在多多边边形形内内还还是是多边形外多边形外。多边形填充概述：多边形填充概述：多边形填充概述多边形填充概述012345678987654321P2P1P3P4P5P6多边形

7、内点的判别准则多边形内点的判别准则按按照照扫扫描描线线顺顺序序进进行行扫扫描描，由由于于多多边边形形是是封封闭闭的的，扫扫描描线线与与多多边边形形的的交交点点成成对对出出现现（如如扫扫描描线线y=3,y=7y=3,y=7）。成成对对出出现现的的交点之间的点属于多边形交点之间的点属于多边形内点内点。奇异点奇异点的处理的处理当当扫扫描描线线通通过过多多边边形形的的顶顶点点时时上述准则失效。上述准则失效。存在两种类型的顶点：存在两种类型的顶点：局局部部极极值值点点（P P2 2,P,P4 4,P,P5 5,P,P6 6）看看成两个点成两个点非极值点非极值点（P P1 1,P,P3 3）看成一个点）看

8、成一个点ABCD奇点的处理奇点的处理多边形P的顶点可分为两类：极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)0，则称顶点Pi为极值点；否则称Pi为非极值点。规定：奇点是极值点时，该点按两个交点计算，否则按规定：奇点是极值点时，该点按两个交点计算，否则按一个交点计算。一个交点计算。奇点的预处理：多边形填充概述多边形填充概述012345678987654321P2P1P3P4P5P6多边形填充算法多边形填充算法1 1、扫描线、扫描线y=1y=1；2 2、求求出出该该扫扫描描线线与与多多边边形形的的交交点；点；3 3、将将所所求求交交点点按按x x坐坐标标从从小小到到大大排排列列，将

9、将交交点点成成对对取取出出，作作为为两两个个端端点点，并并填填充充两两端端点点内内的的像素；像素；4 4、扫描线、扫描线y+y+；5 5、重重复复步步骤骤2 24 4，直直到到y yy ymaxmax，扫描结束。，扫描结束。该该算算法法中中每每条条扫扫描描线线都都需需要要对对多多边边形形求求交交，计计算算量量大大，效效率率低低。没没有有利用多边形边的相关性利用多边形边的相关性ABCDvoid FillPolygonPbyP(Polygon*P,int polygonColor)int x,y;for(y=ymin;y=ymax;y+)for(x=xmin;x=xmax;x+)if(IsInsi

10、de(P,x,y)PutPixel(x,y,polygonColor);else PutPixel(x,y,backgroundColor);/*end of FillPolygonPbyP()*/#define MAX 100Typedef struct int PolygonNum;/多边形顶点个数 Point vertexcesMAX /多边形顶点数组 Polygon /多边形结构程序程序多边形填充算法多边形填充算法有序边表填充算法有序边表填充算法边的相关性边的相关性 相邻扫描线上的交点是与多边相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描形的边线相关的。对同一条边，前

11、一条扫描线线y yi i与该边的交点为与该边的交点为x xi i，而后一条扫描线，而后一条扫描线y yi+1i+1=y=yi i+1+1与该边的交点则为与该边的交点则为x xi+1i+1=x=xi i+1/m+1/m，利用这种相关性可以省去大量的求交运算。，利用这种相关性可以省去大量的求交运算。基本思想基本思想：利用多边形边的相关性，采用边表和：利用多边形边的相关性，采用边表和活性边表，减少求交计算量。活性边表，减少求交计算量。多边形填充算法多边形填充算法有序边表填充算法有序边表填充算法边表边表（ETET：Edge TableEdge Table）用来对边（除水平边外）进行登记，建立边的记录。

12、边的记录定义为：用来对边（除水平边外）进行登记，建立边的记录。边的记录定义为：第一项：某边的最大第一项：某边的最大y y值（值（y ymaxmax）。）。注意要进行奇异点处理：对于非极值点应该注意要进行奇异点处理：对于非极值点应该y ymaxmax=y=ymaxmax-1-1。第二项：某边的最小的第二项：某边的最小的y y对应的对应的x x值。值。第三项：某边斜率的倒数：第三项：某边斜率的倒数：1/m1/m。第四项：指针。用来指向同一条扫描线相交的其它边。第四项：指针。用来指向同一条扫描线相交的其它边。如果其它边不存在，则该项置空。如果其它边不存在，则该项置空。多边形填充算法多边形填充算法有序

13、边表填充算法有序边表填充算法活动边表活动边表（AETAET：Active Edge TableActive Edge Table）ET ET表建立以后，就可以开始扫描转换了。对不同的表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个些边线，为此需要建立一个只与当前扫描线相交的边只与当前扫描线相交的边记录链表记录链表，称之为活动边表。，称之为活动边表。有序边表填充算法举例有序边表填充算法举例对下图的

14、多边形利用有序边表填充算法进行处理：对下图的多边形利用有序边表填充算法进行处理：建立建立ETET表表（注意：在做奇异点处理时，当该边最大（注意：在做奇异点处理时，当该边最大y y值对应的顶点为非极值对应的顶点为非极值点时，边记录的第一项：值点时，边记录的第一项：y ymaxmax=y=ymaxmax-1-1。例如：。例如：P P3 3P P4 4边、边、P P3 3P P2 2边、边、P P4 4P P5 5边）边）建立建立AETAET表表（AETAET表的建立过程就是进行填充的过程）表的建立过程就是进行填充的过程）（1 1）合并）合并ETET表（表（2 2）x x递增排序；（递增排序；（3

15、3）实施填充；（）实施填充；（4 4）删除）删除y ymaxmaxy yj j的边；的边；（5 5）修改边记录）修改边记录x xi i=x=xi i+1/m+1/m；（；（6 6）y yj j+1+1进入下一轮循环。进入下一轮循环。有序边表填充算法演示有序边表填充算法演示有序边表填充算法演示.swf有序边表填充算法实现有序边表填充算法实现1 1、根据给定的多边形顶点坐标，建立、根据给定的多边形顶点坐标，建立ET ET 表。表。2 2、AETAET表初始化，每个桶置空。表初始化，每个桶置空。3 3、for(y=yfor(y=yminmin;y=y;y=ymaxmax;y+);y+)合并当前扫描线

16、合并当前扫描线y y的的ETET表；表；将将y y桶中每个记录按桶中每个记录按x x项升序排列；项升序排列；在当前在当前y y值下，将两两记录的值下，将两两记录的x x值之间的像素进行填充；值之间的像素进行填充；删除删除y=yy=ymaxmax的边记录；的边记录；修改边记录修改边记录x=x+1/mx=x+1/m；该算法充分利用多边形的边相关性，使用该算法充分利用多边形的边相关性，使用ET表对多边形的非水表对多边形的非水平边进行登记；用平边进行登记；用AET表的建立和更新来支持填充，大大地减少了表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。求交点的计算量，有效地提高

17、了填充速度。种种子子填填充充是是将将区区域域内内的的一一点点(种种子子)赋赋予予给给定定的的颜颜色色，然然后后将将这这种种颜颜色扩展到整个区域内的过程。色扩展到整个区域内的过程。填充条件填充条件区域内一点的坐标即种子坐标、边界色、填充色。区域内一点的坐标即种子坐标、边界色、填充色。连通方式连通方式种子填充算法要求区域是连通的。种子填充算法要求区域是连通的。四四连连通通：从从区区域域内内一一点点出出发发，可可通通过过四四个个方方向向：上上、下下、左左、右右到到达该区域内部的任意像素。达该区域内部的任意像素。八八连连通通：区区域域内内部部从从一一个个像像素素到到达达另另一一个个像像素素的的移移动动

18、路路径径，除除了了上上、下、左、右四个方向外，还允许沿着对角线方向。下、左、右四个方向外，还允许沿着对角线方向。种子填充概述：种子填充概述：四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fco

19、lor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);24 1 53四连通种子递

20、归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolo

21、r);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);1四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,

22、int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);F

23、ill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);12四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y

24、);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill

25、(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);132四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolo

26、r)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);4132四连通种子递归填充算法四连通种子递归填充算法Void F

27、ill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,f

28、color);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);54132四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fco

29、lor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,f

30、color);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);654132四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点

31、（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,

32、fcolor);Fill(x+1,y,bcolor,fcolor);6574132四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!

33、=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);65741832四连通种子递归填充算法四连通种子递归填充算法Void Fill(in

34、t x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor)

35、;Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);657418329四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolo

36、r)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fco

37、lor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);Fill(x+1,y,bcolor,fcolor);65741108329四连通种子递归填充算法四连通种子递归填充算法Void Fill(int x,int y,int bcolor,int fcolor)Void Fill(int x,int y,int bcolor,int fcolor)int color;int color;color=GetPixel(x,y);/color=GetPixel(x,y);/获得当前点（获得

38、当前点（x,yx,y）的颜色值）的颜色值;if(color!=bcolor)&(color!=fcolor)if(color!=bcolor)&(color!=fcolor)Putpixel(x,y,fcolor);Putpixel(x,y,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y+1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x,y-1,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x-1,y,bcolor,fcolor);Fill(x+1,y,bcol

39、or,fcolor);Fill(x+1,y,bcolor,fcolor);上述算法的缺点：算法效率低，有些像素会多次入栈，需要大量栈空上述算法的缺点：算法效率低，有些像素会多次入栈，需要大量栈空间来存储相邻的点。间来存储相邻的点。扫描线种子填充算法扫描线种子填充算法种子填充算法的一种种子填充算法的一种以扫描线上的以扫描线上的区段区段为单位进行操作。为单位进行操作。所谓区段，就是一条扫描线上相连着的若干内部像素的集合。所谓区段，就是一条扫描线上相连着的若干内部像素的集合。种子像素不再代表一个孤立的像素，而是代表一个尚未填充的区段种子像素不再代表一个孤立的像素，而是代表一个尚未填充的区段基本算法思

40、想基本算法思想首先填充当前扫描线上种子所处的区段，然后确定与首先填充当前扫描线上种子所处的区段，然后确定与这一区段这一区段相邻的相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存并填充起来。反复这个过程，直到所保存的各在，则依次把它们保存并填充起来。反复这个过程，直到所保存的各区段都填充完毕。区段都填充完毕。扫描线种子填充算法演示扫描线种子填充算法演示扫描线种子填充算法演示扫描线种子填充算法演示.swf.swf算法实现算法实现1、初始化堆、初始化堆栈栈。2、种子、种子压压入堆入堆栈栈。3、while

41、（堆（堆栈栈非空）非空）(1)从堆从堆栈弹栈弹出种子像素。出种子像素。(2)如果种子像素尚未填充，如果种子像素尚未填充，则则：a.求出种子区段：求出种子区段：xleft、xright;b.填充整个区段。填充整个区段。c.检查检查相相邻邻的上下的上下扫扫描描线线的的xleftxxright区区间间内内,是否存在需要填是否存在需要填充的新区段，如果存在的充的新区段，如果存在的话话，则则把每个新区段在把每个新区段在xleftxxright范范围围内的内的最右最右边边的像素，作的像素，作为为新的种子像素依次新的种子像素依次压压入堆入堆栈栈。扫描线种子填充算法特点扫描线种子填充算法特点该算法考虑了扫描线

42、上像素的相关性，该算法考虑了扫描线上像素的相关性，种子像素种子像素不再代表不再代表一个孤立的像素，而是一个孤立的像素，而是代表一个尚未填充的区段代表一个尚未填充的区段。进栈时，只将进栈时，只将每个区段选一个像素每个区段选一个像素进栈（每个区段最右端进栈（每个区段最右端的像素），这样解决了占用堆栈空间过多的问题。的像素），这样解决了占用堆栈空间过多的问题。整个区段的填充在种子出栈时完成。整个区段的填充在种子出栈时完成。是这两者有机的结合：一边对尚未填充像素的登记（像素是这两者有机的结合：一边对尚未填充像素的登记（像素进栈），一边进行填充（像素出栈），既可以进栈），一边进行填充（像素出栈），既可以

43、节省堆栈空节省堆栈空间间，又可以实施快速填充。，又可以实施快速填充。今天我们主要学习了今天我们主要学习了：区域填充的概念区域填充的概念有序边表填充算法有序边表填充算法顶点奇异点的处理、边表、活性边表的生成顶点奇异点的处理、边表、活性边表的生成种子填充算法种子填充算法4 4连通、连通、8 8连通、种子递归填充、扫描线种子填充连通、种子递归填充、扫描线种子填充小结小结一、判断题一、判断题1 1、光栅显示器上不可能在任意两个点间画出一条精确直线、光栅显示器上不可能在任意两个点间画出一条精确直线段的原因是：像素坐标只能取整数值。段的原因是：像素坐标只能取整数值。2 2、多边形填充时，处理奇异点规则为：

44、对于局部极值点，、多边形填充时，处理奇异点规则为：对于局部极值点，应看成一个点；对于非极值点，应看成两个点。应看成一个点；对于非极值点，应看成两个点。3 3、扫描线种子填充算法中，种子代表的是它所在的尚未填、扫描线种子填充算法中，种子代表的是它所在的尚未填充的区段。充的区段。随堂练习随堂练习（）（）（）二、多选题二、多选题1 1、多边形填充需要的填充条件、多边形填充需要的填充条件。A.A.多边形内的一点的坐标多边形内的一点的坐标 B.B.边界色边界色 C.C.填充色填充色 D.D.多边形的顶点序列多边形的顶点序列 E.E.背景色背景色 F.F.填充模式填充模式 2 2、矢量图形的描述哪些是正确

45、的、矢量图形的描述哪些是正确的。A.A.可无级放大可无级放大 B.B.放大到一定程度会出现锯齿状放大到一定程度会出现锯齿状 C.C.变换容易变换容易 D.D.不易变换不易变换 E.E.存储容量大存储容量大 F.F.存储容量小存储容量小 随堂练习随堂练习3 3、种子填充需要的填充条件为、种子填充需要的填充条件为。A.A.区域内一点的坐标区域内一点的坐标 B.B.多边形的顶点序列多边形的顶点序列 C.C.边界色边界色 D.D.背景色背景色 E.E.填充色填充色 F.F.填充模式填充模式答案：答案：ACFACF答案：答案：ACEACE答案：答案：DCDC三、主观题三、主观题1 1、用边相关扫描线填充算法，对图用边相关扫描线填充算法，对图中多边形建立中多边形建立ETET、AETAET表。表。随堂练习随堂练习答案：答案：三、主观题三、主观题2 2、用扫描线种子填充算法，写出图用扫描线种子填充算法，写出图中顺序进栈的种子坐标。中顺序进栈的种子坐标。随堂练习随堂练习答案：顺序进栈的种子坐标为：答案：顺序进栈的种子坐标为：（1 1，2 2）（2 2，3 3）（2 2，1 1）（4 4，4 4）