程。
.
2
4）区域的建立（定义）方式： ①内定区域：在所定义的区域内所有的像素具有相 同的属性（如颜色等）。 （内部定义方式） ②边界定义区域：以区域的内外属性来划分，区域 内的像素和边界上的像素可具有不同的属性。 （外界定义方式）
.
3
5）连通性：分为四向连通和八向连通。
①四连通：各像素在水平、垂直的上、下、左、 右四个方向上是连通的。
准备工作： typedef struct { int x,y;} seed; typedef struct { seed s[6400];int top;} seedstack;
.
10
VC++程序实现
.
11Βιβλιοθήκη 以直接利用函数的递归调用来实现.设（x,y）为内点表示的4连通区域内的一点， oldcolor为区域的原色，要将整个区域填充为新 的颜色newcolor。
出发，沿当前扫描线向左、右两个方向填充，直 到非内部。分别标记区段的左、右端点坐标为xl 和xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与 当前扫描线y上、下相邻的两条扫描线上的象素。 若存在非边界、未填充的象素，则把每一区间的 最右象素作为种子点压入堆栈，返回第（2）步。
{ int color= Getpixel(x,y); if(color!=newcolor && color!=boundarycolor) { drawpixel(x,y,newcolor); BoundaryFill4 (x,y+1, boundarycolor,newcolor); BoundaryFill4 (x,y-1, boundarycolor,newcolor); BoundaryFill4 (x-1,y, boundarycolor,newcolor); BoundaryFill4 (x+1,y, boundarycolor,newcolor); }
效率低的原因是没有考虑各象素之间的联系，孤立地考
察象素与区域的关系，使得几十万甚至几百万个象素都要一一 判别，每次判别又要多次求交点，需要做大量的乘除运算，花 费很多时间。
.
6
如何判断点在多边形的内或外？ （包含性检查的方法）
1）射线法； 2）累计角度法； 3）编码法； 4）……..
这些内容在本书第八章几何造型中有 专门介绍。
FloodFill4(x,y-1,oldcolor,newcolor);
FloodFill4(x-1,y,oldcolor,newcolor);
FloodFill4(x+1,y,oldcolor,newcolor);
}
}
.
12
边界表示的4连通区域的递归填充算法:
void BoundaryFill4(int x,int y,int boundarycolor,int newcolor)
上述算法对于每一个待填充区段，只需压栈一次；而在递
归算法中，每个象素都需要压栈。因此，扫描线填充算法提
高了区域填充的效率。
.
14
扫描线区域填充算法 可由下列四个步骤实现：
(1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，
y），以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）
D
False when x D
.
5
取矩形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);
上述算法原理简单、实用，但效率低；
1）深度递归的种子填充算法
2）扫描线种子填充算法
.
9
1）深度递归的种子填充算法(漫水法）
从已知种子点出发，每填充一点，在其周围寻找 新种子点，重复进行，直到再无未填充的点为止。
针对内点表示的4连通区域的递归填充具体步骤: 1.种子入栈. 2.当栈非空时,进行下面的操作,否则结束. 3.栈顶元素出栈,如果是未填充的内部点,则将其填充. 继续考察与其连通的点,若是未填充的内部点,则该点 入栈.返回2.
} 对于内点表示和边界表示的8连通区域的填充，只要
将上述相应代码中递归填充相邻的4个象素增加到递归填 充8个象素即可。
.
13
2）扫描线种子填充算法
▪ 种子填充的递归算法原理和程序都很简单，但由 于多次递归，费时、费内存，效率不高。为了减 少递归次数，提高效率可以采用采用扫描线算法。
▪ 算法的基本过程如下：当给定种子点(x,y)时，首 先填充种子点所在扫描线上的位于给定区域的一 个区段，然后确定与这一区段相连通的上、下两 条扫描线上位于给定区域内的区段，确定新种子 点，并依次保存下来。反复这个过程，直到填充 结束。
内点表示的4连通区域的递归填充算法:
void FloodFill4(int x,int y,int oldcolor,int newcolor)
{ if(getpixel(x,y)==oldcolor)
{ drawpixel(x,y,newcolor);
FloodFill4(x,y+1,oldcolor,newcolor);
第四讲 区域填充
1. 有关概念 2. 逐点判断填充算法 3. 种子填充算法 4. 区域填充图案 5. 扫描线多边形填充算法 6. 边填充算法
.
1
1. 有关概念
1) 区域：一组相邻而且又相连的像素，而且具有 相同属性的封闭区域。 2）种类：①单域 ②复合域
3) 区域填充：以某种属性对整个区域进行设置的过
.
7
这里以射线法为例进行说明：
过被检测点任作一条射线,求其与边界的交点, 若交点数为偶数,则该点在边界之外,否则在边界 之内。
当射线经过顶点时,可通过”左开右闭”,或” 上开下闭”进行处理。
P
P
.
8
3.种子填充算法
种子填充算法假设在多边形内有一象素已知，由此出 发利用连通性找到区域内的所有象素，并进行填充。
②八连通：各像素在上、下、左、右以及四个对 角线方向都是连通的。
.
4
2.逐点判断填充算法
区域填充的基本(初级)方法:逐点判断填充算法
➢ 逐点判断绘图窗口内的每一个像素； ➢ 若在区域的内部：用指定的属性设置该点； ➢ 否则不予处理；
设有如下函数：
True when x D
Inside(D,x,y)=