区域填充即给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色，本节中我们就以此为例讨论区域填充算法。
多边形填色即给出一个多边形的边界，要求对多边形边界范围的所有象素单元赋予指定的色代码。要完成这个任务，一个首要的问题，是判断一个象素是在多边形内还是外。数学上提供的方法是“扫描交点的奇偶数判断”法：
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处，因为光栅化后，使得扫描线通过交点的个数发生变化而同样导致填色错误。因此，原始的奇偶判断方法需要加以周密地改善，才能成为计算机中实用的填色算法。
填色算法分为两大类：
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)右顶点
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);
}
}