区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色，本节中我们就以此为例讨论区域填充算法。
多边形填色即给出一个多边形的边界，要求对多边形边界范围的所有象素单元赋予指定的色代码。要完成这个任务，一个首要的问题，是判断一个象素是在多边形内还是外。数学上提供的方法是“扫描交点的奇偶数判断”法：
1、将多边形画在纸上。
2、用
一根水平扫描线自左而右通过多边形而与多边形之边界相交。扫描线与边界相交奇次数后进入该多边形，相交偶次数后走出该多边形。图2.3.1示出这类情况：
扫描线与多边形相交四点。相交a点之后入多边形；交b点（第2交点）之后出多边形；交c点（第3交点）之后又入多边形；交d点（第4交点）之后又出多边
形。
上述方
法似乎能完满地解决问题，但事实并非如此，因为直线在光栅化后变成了占有单位空间的离散点。图2.3.1中的A点处和B、C处，在光栅化后变成图
2.3.2所示的情况。此时，使用上述判断法则，在A、B、C处发现错判现象。在A处，扫描线通过一点后以为入多边形，其实此时已出多边形。结果是在A点
之后的扫描线段上全都错误地填上色。在B和C处，因为光栅化后，使得扫描线通过交点的个数发生变化而同样导致填色错误。因此，原始的奇偶判断方法需要加以
周密地改善，才能成为计算机中实用的填色算法。
图2.3.1
图2.3.2
填色算法分为两大类：
1、扫描线填色（Scan-Line Filling）算法。这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。
2、种子填色（Seed Filling）算法。这类算法建立在多边形边边界的图象形式数据之上，并还需提供多边形界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于程序填色。
区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充可以分两步走，第一步先确定需要填充那些象素，第二步确定用
什么颜色来填充。区域填充中最常用的是多边形填色。
填
色算法分为两大类： 1、扫描线填色（Scan-Line
Filling）算法。这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。 2、种子填色（Seed
Filling）算法。这类算法建立在多边形边边界的图象形式数据之上，并还需提供多边形界内一点的坐标。所以，它一般只能用于人机交互填色，而难以用于
程序填色。
1>.扫描线填色算法
扫描线填色算法的基本思想是：
用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。
一、算法的基本思想
多边形以n, x_array, y_array形式给出，其中x_array，y_array中存放着多边形的n个顶点的x, y坐标。扫描线填色算法的基本思想是：
用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。
上述基本思想中，有几个问题需要解决或改善。它们是：
1. 左、右顶点处理 当以1, 2, 3的次序画多边形外框时，多边形的左顶点和右顶点如图2.3.3 (a)、(b)所示的顶点2。它们具有性质：
左顶点2：y1<y2<y3
右顶点2：y1>y2>y3
其中y1, y2, y3是三个相邻的顶点的y坐标。
(a)左顶点 (b)右顶点
图2.3.3
当扫描线与多边形的每个顶点相交时，会同时产生2个交点，这是因为一个顶点同属于多边形之两条边的端点。这时，如果所交的顶点是左顶点或右顶点，填色就会因奇偶计数出错而出现错误。因此，对多边形的所有左、右顶点作如下处理；
左、右顶点的入边（以该顶点为终点的那条边），即1, 2边之终点删去。即：
对于左顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（
,y2-1）；
对于右顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（
,y2+1）；
其中m=
，即入边之斜率。
对于多边形的上顶点（y2>y1 & y2>y3）或下顶点（y2<y1 & y2<y3），奇偶记数保持正确，因此不必修改，保持相邻边原状不变。
2. 水平边处理 水平边（y1=y2）与水平扫描线重合法求交点。因此，将水平边画出后删去，不参加求交及求交以后的操作。
3. 扫描线与边的求交点方法采用递归算法 边（x1, y1）（x2, y2）与扫描线i+1的交点为：
（当交点不为x1, y1时）
否则，交点为x1, y1。
由上式可知，求交点只须做两个简单的减法。
4.
减少求交计算，采用活性边表
对于一根扫描线而言，与之相交的边只占多边形全部边的一部分。因此，在基本算法思想中，每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改善。活
性边表（Active List of
Side）的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前的扫描线不相交的边的集合。后者不必予以求交，这样就提高了算法的效
率。
(a) (b)在scan1的情况
图2.3.4 活性边表及其指针的表示
活性边表的构成方法是：
1）
将经过左、右顶点处理及剔除水平边后的多边形之各边按照max y值排序，存入一个线性表中。表中每一个元素代表一根边。第一个元素是max
y值最大的边，最后一个元素是max y值最小的边。图2.3.4
(a)中的多边形所形成的线性表如（b）所示。其中F点和B点的y值相等，且为全部多边形的max y的最大值。因此FG, FE, AB,
BC等四边排在表之首。而C点的y值>E点的y值，所以CH排在DE前面，余类推。在max y值相等的边之间，按任意次序排列。
2）
在上述线性表上加入两个指针first和last，即形成活性边表。这两个指针之间是与当前扫描线相交的边的集合和已经处理完（即扫描完）的边的集合。这
两者的区分方法是在处理完的边上加上记号：?
y=0。在last指针以后的是尚未与当前扫描线相交的，在first指针以前的是已经处理完了的边。对于图2.3.4
(a)中扫描线scan1的情况下，图2.3.4 (b)中列出first,
last的位置。如果扫描线由上而下移到了scan2的位置，则活性边表的first应指向AB，last应指向CH。每根扫描线只须与位于first,
last之间的，而且? y? 0的边求交即可。这就缩小了求交的范围。
3）活性边表中每个元素的内容包括：
·边的max y值，记为y_top；
·与当前扫描线相交点的x坐标值，记为x_int；
·边的y方向当前总长。初始值为y2-y1。记为? y；
·边的斜率倒数：
，记为x_change_per_scan。
4）活性边在每根扫描线扫描之后刷新。刷新的内容有2项：
·调整first和last指针字间的参加求交的边元素之值：? y=? y-1; x_int = x_int - x_change_per_scan;
·调整first和last指针，以便让新边进入激活范围，处理完的边退出激活范围：
当first所指边的? y=0时，first=first+1；
当last所指的下一条边的y_top? 下一扫描线的y值时，last=last+1。
二、扫描线填色程序
程序2.3.1示出扫描线填色算法的程序。主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共count个）的x和y坐标。它调用8个子程序，彼此的调用关系如图2.3.5所示。各子程序的功能为：
图2.3.5 fill_area的程序结构
typedef struct {
int y_top;
float x_int;
int delta_y;
floaat x_change_per_scan;
} EACH_ENTRY;
EACH_ENTRY SIDES[MAX_POINT];
int x[MAX_POINT], y[MAX_POINT];
int side_count, first_s, last_s, scan, bottomscan, x_int_count, r;
fill_area(count, x, y)
int count, x[ ], y[ ];
{
sort_on_bigger_y(count);
first_s=1;
last_s=1;
for (scan=sides[1].y_top; scan>bottomscan ?; scan - -)
{
up date_first_and_last(count, scan);
process_x_intersections(scan, first_s, last_s);
draw_lines (scan, x_int_count, first_s);
update-_sides_list ( );
}
}
void put_in_sides_list(entry, x1, y1, x2, y2, next_y);
int entry, x1, y1, x2, y2, next_y;
{
int maxy;
float x2_temp, x_change_temp;
x_change_temp = (float) (x2-x1) / (float) (y2-y1);
x2_temp =x2; /*以下为退缩一点操作. */
if ((y2>y1) && (y2<next_y)) {
y2 - - ;
x2_temp - = x_change_temp;
}
else {
if ((y2<y1) && (y2 >next_y)) {
y2++;
x2_temp+=x_change_temp;
}
}
/* 以下为插入活性表操作. */
maxy = (y1 > y2)? y1: y2;
while (( entry >1) && (maxy > sides [entry -1]. y_top))
{
sides[entry]=sides [entry ?];
entry - -;
}
sides[entry]. y_top=maxy;
sides[entry]. delta_y =abs(y2-y1)+1;
if (y1>y2)
sides[entry]. x_int =x1;
else{
sides[entry].x_int=x2_temp;
sides[entry]. x_change_per_scan=x_change_temp;
}
void sort_on_bigger_y(n)
int n;
{
int k, x1, y1;
side_count=0;
y1=y[n];
x1=x[n];
bottomscan=y[n];
for (k=1; k<n+1; k++)
{
if (y1 ! =y[k]) {
side_count ++;
put_in_sides_list(side_count, x1, y1, x[k], y[k]);
}
else {
move ((short)x1, (short)y1);
line((short)x[k], (short)y1, status);
}
if (y[k] <bottomscan) bottomscan=y[k];
y1=y[k]; x1=x[k];
}
}
void update_first_and_last(count, scan)
int count, scan;
{
while((sides[last_s+1]. y_top>=scan) && (last_s <count)) last_s ++;
while(sides[first_s]. delta_y = = 0) first_s ++;
}
void swap(x, y)
EACH_ENTRY x, y;
{
int i_temp;
float f_temp;
i_temp=x.y_top; x.y_top=y.y_top; y.y_top=i_temp;
f_temp=x.x_int; x.x_int=y.x_int; y.x_int=f_temp;
i_temp=x.delta_y; x.delta=y.delta_y; y.delta_y=i_temp;
f_temp=x.x_change_per_scan; x. x_change_per_scan=y. x_change_per_scan; y.x.
change_per_scan=f_temp;
}
void sort_on_x(entry, first_s)
int entry, first_s;
{
while((entry > first_s) && (sides[entry]. x_int < sides[entry-1]. x_int))
{
swap (sides[entry], sides[entry-1]);
entry - -;
}
}
void process_x_intersections(scan, first_s, last_s)
int scan, first_s, last_s;
{
int k;
x_int_cout=0;
for(k=first_s; k<last_s+1; k++)
{
if(sides[k]. delta_y >0) {
x_int_count ++;
sort_on_x(k, first_s);
}
}
}
void draw_lines(scan, x_int_count, index)
int scan, x_int_count, index;
{
int k, x, x1, x2;
for (k=1; k< (int) (x_int_count/2+1.5); k++)
{
while(sides[index]. delta_y = = 0) index ++;
x1=(int)(sides[index]. x_int +0.5);
index ++;
while(sides[index].delta_y = = 0) index ++;
x2 = (int) (sides [index]. x_int +0.5);
move((short)x1, (short)scan);
line((short)x2, (short)scan, status);
index ++;
}
}
void update_sides_list( )
{
int k;
for (k=first_s; k<last_s +1; k++)
{
if(sides[k].delta_y >0)
{
sides[k].delta_y - -;
sides[k]. x_int - = sides[k]. x_change_per_scan;
}
}
}
程序2.3.1 扫描线填色程序
1、sort_on_bigger_y子程序的主要功能是按照输入的多边形，建立起活性边表。操作步骤是：对每条边加以判断：如非水平边则调用put_in_side_list子程序放入活性边来；如是水平边则直接画出。
2、put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，在该边的位置中填入数据。
3、update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围。
4、
process_x_intersections子程序的主要功能是对活性边表中的激活边（即位于first和last之间的，并且? y?
0的边）按照x_int的大小排序。操作步骤是：从first到last，对每一根? y?
0的边，调用sort_on_x子程序排入活性边表中合适位置。
5、
sort_on_x子程序主要功能是将一条边side[entry]，在活性边表的first到entry之间按x_int的大小插入合适位置。操作步骤
是：检查位于entry的边的x_int是否小于位置entry-1的边的x_int，如是，调用swap子程序交换两条边的彼此位置。
6、swap子程序的主要功能是交换活性边表中两条相邻位置边的彼此位置。
7、draw_lines子程序的主要功能是在一条扫描线位于多边形内的部分，填上指定的色彩。操作步骤是：在活性边表的激活边范围内，依次取出Δy¹ 0两边的x_int，作为两个端点（x1, scan），(x2, scan)，画一条水平线。
8、update_sides_list子程序的主要功能是刷新活性边表内激活边的值：Δy=Dy-1
x_int=x_int_x_chang_per_scan；2>种子填色算法
种子填色又称边界填色（Boundary Filling）。它的功能是：给出多边形光栅化后的边界位置及边界色代码boundary，以及多边形之内的一点x, y位置，要求将
种子填色又称边界填色（Boundary Filling）。它的功能是：给出多边形光栅化后的边界位置及边界色代码boundary，以及多边形之内的一点x, y位置，要求将颜色color填满多边形。
通
常采用的填法有两种：四邻法（4-connected）和八邻法。四邻法是已知x,
y（图2.3.6(a)的黑色象素）是多边形内的一点，据此向上下左右四个方向测试（图2.3.6(a)中打勾的象素）、填色、扩散。四邻法的缺点是有时
不能通过狭窄区域，因而不能填满多边形。如图2.3.6(b)所示，左下角方形中的种子（打点的象素）不能扩散到右上角的方形中，因为采用四邻法通不过中
间的狭窄区域。八邻法是已知x, y（图2.3.6
(c)中黑色的象素）为多边形内的一点，即种子，据此可向周围的八个方向（图2.3.6(c)中打勾的象素）测试、填色、扩散。八邻法的缺点是有时要填出
多边形的边界。如图2.3.6(d)所示的边界，按八邻法就会将色彩涂出多边形。由于填不满往往比涂出更易于补救，因此四邻法比八邻法用的更普通。
四邻法种子填色基本程序如程序2.3.2所示。这种程序书写简洁，但运行效率不高，因为包含有多余的判断。在它的基础上可以写出各种改进的算法[8]。
void seed_filling (x, y, fill_color, boundary_color)
int x, y, fill_color, boundary_color;
{
int c;
c=inquire_color(x, y);
if((c< > boundary_color) && (c< > fill_color))
{
set_pixel(x, y, fill_color);
seed_filling(x+1, y, fill_color, boundary_color);
seed_filling(x-1, y, fill_color, boundary_color);
seed_filling(x, y+1, fill_color, boundary_color);
seed_filling(x, y-1, fill_color, boundary_color);
}
}
程序2.3.2 四邻法种子填色程序
图2.3.6 四邻法和八邻法种子
-
四邻法
-
四邻法不能填满此多边形
-
八邻法
-
八邻法会涂出此多边形
颜色color填满多边形。