區域填充即給出一個區域的邊界，要求對邊界范圍內的所有象素單元賦予指定的顏色代碼。區域填充中最常用的是多邊形填色，本節中我們就以此為例討論區域填充算法。
多邊形填色即給出一個多邊形的邊界，要求對多邊形邊界范圍的所有象素單元賦予指定的色代碼。要完成這個任務，一個首要的問題，是判斷一個象素是在多邊形內還是外。數學上提供的方法是“掃描交點的奇偶數判斷”法：
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子程序的主要功能是在一條掃描線位于多邊形內的部分，填上指定的色彩。操作步驟是：在活性邊表的激活邊范圍內，依次取出Δy1 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填滿多邊形。