算法系列之十二：多邊形區域填充算法－－幾種邊標誌填充算法

時間 2021-01-08

四、邊界標誌填充算法

在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個閉合區域，填充是逐行進行的，即用掃描線逐行對多邊形求交，在交點對之間填充。邊界標誌填充算法就是在逐行處理時，利用邊界或邊界顏色作爲標誌來進行填充的。準確地說，邊界標誌填充算法不是指某種具體的填充算法，而是一類利用掃描線連貫性思想的填充算法的總稱。這類算法有很多種，本篇就介紹幾種。

首先介紹一種以邊爲中心的邊緣填充算法，這種邊界標誌算法的基本思想是：對於每一條掃描線和每一條多邊形邊的交點(xi，yi)，將該掃描線上交點右方的所有象素取補，依次對多邊形的每條邊作此處理，直到最終完成填充。這裏要介紹一下取補的定義，假設某點的顏色是M，則對該點的顏色取補得到M’ = A – M，A是一個很大的數字，至少要比所有合法的顏色值大。根據取補的定義，如果對光柵位圖某區域已經標記爲M的顏色值做偶數次取補運算，該區域顏色不變；而做奇數次取補運算，則該區域顏色變爲值爲M’的顏色。算法可以簡單描述爲兩個步驟：

1、將繪圖窗口的背景色置爲M’顏色；

2、對多邊形的每一條非水平邊，從該邊上的每個象素開始向右求餘；

算法的處理過程如圖（12）所示，左邊是多邊形的形狀，右邊分別是對每條邊處理完成後填充區域的顏況，初始背景顏色是M’，經過處理後，需要填充的區域是奇數次取補，最終的顏色是要填充的正確值M，非填充區域經過偶數次取補，仍然是背景色M’：

圖（12）邊緣填充算法的處理過程

算法的實現非常簡單，對於光柵位圖的展示，我們仍然採用前文所用的方法，用數字矩陣表示一塊光柵位圖區域，矩陣的每個位置表示一個像素點，用0－9表示顏色值。本算法示例用9表示最大值A，0表示無效的區域，合法的顏色值就是1－8。

87void EdgeCenterMarkFill(const Polygon& py, int color)
88{
89 std::vector<EDGE3> et;
90
91 InitScanLineEdgesTable(et, py);//初始化邊表
92
93 FillBackground(A - color); //對整個填充區域背景顏色取補
94 for_each(et.begin(), et.end(), EdgeScanMarkColor);//依次處理每一條邊
95}

76void EdgeScanMarkColor(EDGE3& e)
77{
78 for(int y = e.ymax; y >= e.ymin; y--)
79 {
80 int x = ROUND_INT(e.xi);
81 ComplementScanLineColor(x, MAX_X_CORD, y);
82
83 e.xi -= e.dx;
84 }
85}

這個算法非常簡單，所有的函數實現也很簡單，InitScanLineEdgesTable()函數前面已經介紹過，FillBackground()函數將填充背景初始化爲要填充顏色的取補顏色，EdgeScanMarkColor()函數負責對每條非水平邊進行處理，逐條掃描線進行顏色取補，ComplementScanLineColor()函數負責對y掃描線上[x1, x2]區間的點的顏色值取補。

以上以邊爲中心的填充算法的優點是簡單，缺點是對於複雜多邊形，每一象素可能被訪問多次（多次取補），效率不高。考慮對此算法改進，人們提出了柵欄填充算法。柵欄填充算法的基本思想是：經過多邊形的某個頂點，在多邊形內部建立一個與掃描線垂直的「柵欄」，當掃描線與多邊形邊有交點，就將交點與柵欄之間的象素取補。若交點位於柵欄左邊，則將交點之右，柵欄之左的所有象素取補；若交點位於柵欄右邊，則將柵欄之右，交點之左的象素取補。

仍以圖（12）所示的多邊形爲例，假設經過P4點建立一條柵欄，則改進的柵欄填充算法處理過程就如圖（13）所示：

圖（13）柵欄填充算法的處理過程

柵欄填充算法的實現和以邊爲中心的邊緣填充算法類似，只是對每條邊的掃描線取補處理的範圍控制有區別，算法需要指定一個「柵欄」：

115void EdgeFenceMarkFill(const Polygon& py, int fence, int color)
116{
117 std::vector<EDGE3> et;
118
119 InitScanLineEdgesTable(et, py);//初始化邊表
120
121 FillBackground(A - color); //對整個填充區域背景顏色取補
122 for_each(et.begin(), et.end(), 
123 std::bind2nd(std::ptr_fun(FenceScanMarkColor), fence));//依次處理每一條邊
124}

97void FenceScanMarkColor(EDGE3 e, int fence)
98{
for(int y = e.ymax; y >= e.ymin; y--)
{
int x = ROUND_INT(e.xi);
if(x > fence)
{
ComplementScanLineColor(fence, x, y);
}
else
{
ComplementScanLineColor(x, fence - 1, y);
}
110
e.xi -= e.dx;
}
113}

注意FenceScanMarkColor()函數和EdgeScanMarkColor()函數的區別，就是這點區別使得柵欄填充算法主動減少了很多像素被訪問的次數，而多邊形之外的像素也不會被多餘處理，效率提高了不少。

柵欄填充算法只是減少了被重複訪問的象素的數目，但仍有一些象素會被重複訪問。從圖（13）中很容易看出這一點。下面介紹的邊標誌算法利用掃描線的連貫性，對每個像素只訪問一次即可完成多邊形區域的填充。邊標誌算法的思想是設置一個標誌，沿着掃描線從左到右訪問多邊形所在區域的像素的時候，用這個標誌標識是否掃描到了多邊形的邊界。如果碰到邊界（邊界用特殊的顏色標識），則改變標識狀態，接下來根據標識狀態決定掃描到的像素點是否要填充成指定顏色。

在實施邊標誌填充算法通常先求出多邊形所在圖像區域的最小包圍盒，以便縮小掃描範圍，加快填充速度。完整的填充算法如下：

5void EdgeMarkFill(int xmin, int xmax, int ymin, int ymax, 
int boundarycolor, int color)
7{
int flag = -1;
for(int y = ymin; y <= ymax; y++)
{
flag = -1;
for(int x = xmin; x <= xmax; x++)
{
if(GetPixelColor(x, y) == boundarycolor)
{
flag = -flag;
}
if(flag == 1)
{
SetPixelColor(x, y, color);
}
}
}
24}

可以看到該算法思想簡單，實現容易。算法既不需要初始化邊表、求交點、交點排序等額外操作，也不需要使用鏈表、堆棧等數據結構。不過，邊標誌算法雖然簡單，但是使用時對邊界的處理要格外小心，否則很容易出錯。比如上下頂點之類的局部極值點，會造成標誌的奇偶計數不匹配，填充時會出現「抽絲」現象，也就是掃描線上不該填充的區段被填上色，而應該填充的區段卻沒有填上色。再比如邊界像素點重複的問題，多邊形的邊界是利用直線的生成算法依次畫出的，當掃描線遇到斜率小於1的邊時，容易產生重複的邊界點，如圖（14）所示，引起標誌的無序改變，從而造成填充錯誤。

圖（14）斜率小於1的邊的光柵掃描轉換問題

至此，本文完整介紹了8中常見的多邊形區域填充算法，拖拖沓沓寫了一個多月，總算完成了，居然有將近30頁，總計13000多字（24000多可見字符），畢業以後就沒寫過這麼長的文檔了，感慨一下。本文給出的示例代碼都是爲了演示，基於可讀性而設計的，大家在實際的圖形處理軟件中看到的算法實現可能和本文的示例算法「大相徑庭」，但是基本原理都是一樣的。

參考資料：

【1】計算幾何：算法設計與分析周培德清華大學出版社 2005年

【2】計算幾何：算法與應用德貝爾赫（鄧俊輝譯）清華大學出版社 2005年

【3】計算機圖形學孫家廣、楊常貴清華大學出版社 1995年