3.4 多邊形的掃描轉換及區域填充

3.4.1 多邊形的掃描轉換

多邊形是指由首尾相接的直線段組成的封閉圖形。形成的這個封閉區域是多邊形的內部，封閉區域外側是多邊形的外部，多邊形的頂點即由直線段的端點組成，組成多邊形邊的直線段之間不能發生交叉現象。根據形狀特點，多邊形可以分為下面三種類型：

（1）凸多邊形

凸多邊形指任意兩個頂點的連線都在多邊形內部的多邊形，如圖3.4-1（a）所示。

（2）凹多邊形

凹多邊形指任意兩個頂點的連線有不在多邊形內部的多邊形，如圖3.4-1（b）所示。

（3）帶內環的多邊形

帶內環的多邊形指多邊形內部還嵌套有多邊形，如圖3.4-1（c）所示。這時的多邊形內部是指最外側的多邊形和嵌套的多邊形之間的區域，如果有多個嵌套的多邊形，則要求嵌套的多邊形之間不能交叉，也不能再嵌套。嵌套的多邊形又稱為內環，最外側的多邊形稱為外環。

計算機中多邊形的表示方法有兩種。

（1）頂點表示法

用多邊形的頂點序列來表示多邊形，如圖3.4-2所示。頂點表示法的特點是直觀、幾何意義強，易于圖形變換，而且占用內存較少，但是不能區分多邊形的內外部。

（2）點陣表示法

用位于多邊形內部的像素點集來表示多邊形，如圖3.4-3所示。點陣表示法的特點是可以明確多邊形的內部區域，并將內部區域的像素點顯示成要求的顏色，但是缺少多邊形頂點的幾何信息。

多邊形的掃描轉換就是把多邊形從頂點表示轉換為點陣表示。多邊形的掃描轉換又稱為多邊形的區域填充，即從多邊形的頂點信息出發，求出多邊形的內部區域的像素點，并用要求的顏色顯示出來。

掃描線算法是一種常用的多邊形區域填充算法，其基本原理是按掃描順序，計算每條掃描線與多邊形的相交區間，再用要求的顏色顯示這些區間的像素，即完成填充工作。區間的端點可以通過計算掃描線與多邊形邊界線的交點獲得，如圖3.4-4所示。

掃描線算法的核心：須按x的遞增順序排列掃描線與多邊形邊線的交點序列，并形成區間。算法步驟如下。

（1）確定多邊形所占有的最大掃描線數：得到頂點的最小和最大y值（ymin和ymax）。

（2）從y＝ymin到y＝ymax每次用一條掃描線進行填充。

（3）對一條掃描線填充的過程可分為四個步驟。

①求交：計算掃描線與多邊形各個邊的交點。

②排序：將所有交點按x值的遞增順序排序。

③交點配對：將交點按遞增順序兩兩配成區間對，例如第一點和第二點、第三點和第四點分別組成區間對。交點對之間構成的區間就是多邊形內部的像素點。

④區間填色：將區間對內的像素點設置成要求的顏色。

掃描線算法的原理簡單，實施時需要提高算法的準確度和填充效率。算法準確度主要是指當掃描線通過多邊形的頂點時，由于頂點是相鄰兩個邊的共有點，那么同一個交點會計算兩次，這時會存在交點數的取舍問題。如圖3.4-5所示，當y＝1，5，7，8，9，12時，會通過多邊形的頂點，頂點即交點，只有取合適的交點數，才能正確形成區間對。

解決方法是，若共享頂點的兩條邊分別在掃描線的兩側，則交點只算一個；若共享頂點的兩條邊在掃描線的同一側，這時交點記為零個或兩個。可以通過檢查共享頂點的兩條邊的另外兩個端點的y值，按這兩個y值中大于交點y值的個數來決定交點數取0、1或者2。若共享頂點的兩條邊分別在掃描線的兩側，在代碼中編程時，可以通過將每條邊的ymax減少一個單位，或者將ymin增加一個單位，實現只計算一個交點，如圖3.4-6所示。

在應用程序中實現多邊形掃描轉換時，首先需要構造多邊形。根據多邊形的類型，多邊形的結構類如下：

通過鼠標拾取屏幕點，并連接前后點和首尾相接，獲得多邊形的外環和內環，利用多邊形數組得到多組多邊形，如圖3.4-7所示。

上述的多邊形掃描轉換算法函數代碼參考如下：

在上述的掃描線多邊形填充算法中，需要求掃描線和多邊形邊的交點，并對交點進行排序，其中掃描線和多邊形邊的交點即為水平線和線段的交點，函數代碼如下：

交點x值排序函數代碼如下：

利用上述算法對圖3.4-7所示的多邊形進行掃描轉換，效果如圖3.4-8所示。

由于掃描線填充算法的時間主要花費在計算掃描線與多邊形各邊的求交運算上，因此提高多邊形填充效率的方法是減少與多邊形求交點的邊數和降低求交工作量，在處理一條掃描線時，僅對和當前掃描線相交的有效邊上點組成的區間對進行填充。為此，可以通過構造邊表來表示和掃描線對應的有效邊。方法如下。

（1）構造一個多邊形的邊表（ET），這個邊表按照每個邊的最小y值的增量進行排序。如果邊的最小y值相等，則按照x的增量排序，如果x值也相等，則按照每條邊的直線斜率k的倒數的增量排序。

（2）當沿著掃描線yscan進行掃描時，從邊表中順序取出最小y值和掃描線y相等的邊，組成有效邊表（AET），并對有效邊表按照（1）的方式進行排序。然后按照x的增量順序組成兩兩區間對，并對區間進行填充。

（3）每一個有效邊的x值修改為，最小y值修改為y＝ymin＝ymin+1。

（4）令掃描線yscan＝yscan+1，然后判斷有效邊表中每個邊的最大y值，如果ymax＜yscan，說明該邊不再和掃描線相交，則將該邊從有效邊表中刪除，然后，轉入（2）。

（5）當有效邊表中有效邊的數量為空的時候，說明已經處理到多邊形最大y值，掃描轉換結束。

上述的有效邊表掃描線算法，對于每一個掃描線，只處理掃描線通過的邊，在求交點時，是利用遞推公式計算的，因此掃描效率更高。

在構造每條邊的信息時，需要包括：該邊當前最小y值、當前對應的x值、該邊最大y值以及該邊斜率的倒數。當該邊為特殊位置直線水平線時，斜率倒數為無窮大，為了準確記錄邊的信息，此時還應該記錄該邊另外一個頂點的x值信息；如果斜率倒數不為無窮大，則另一個頂點的x值可不必記錄。因此，構造邊結構如下：

對應的邊類為：

圖3.4-9所示為一多邊形以及根據上述方法構造的邊表。

在邊表中，由于斜率倒數沒有無窮大的情況，因此邊表中的x另這一列不用登記。其中，在構造直線P2P3的節點時，在最大頂點即（1，7）處，由于共享該頂點的多邊形另外一條邊即P1P2分布在掃描線y＝7的另外一側，考慮交點的取舍為題，將該直線的ymax減少一個單位，即節點值為邊表值的第一行：

當掃描線y＝1時，從邊表中取出有效邊，通過排序組成有效邊表，將有效邊表中的邊的x值兩兩構成區間對填充，然后修改有效邊的值：，如圖3.4-10所示。如果ymax＜ymin，則該邊已經處理完，不再為有效邊，將其從有效邊表中刪除。

以此類推，當掃描線y＝2時，首先判斷邊表中是否存在有效邊。如有，則取出插入現有的有效邊表中，并排序，同樣將有效邊表中的邊的x值兩兩構成區間對，填充，然后修改有效邊的值：，判斷是否ymax＜ymin的情況，如圖3.4-11所示。

循環執行上述操作，當ymax＜ymin時，從有效邊表中刪除已經處理完的邊，例如，y＝5時，將P3P4以及P4P5兩個邊從有效邊表中刪除，當y＝7時，將P1P2邊從邊表中取出，插入有效邊表并排序，開始填充，并重復上述的修改邊的值以及判斷操作。當邊表中的所有邊都已經取出，而且有效邊表也成為空表，說明所有邊都已經處理，此時多邊形內部全部填充完畢，掃描轉換結束，如圖3.4-12所示。

上述的有效邊表多邊形掃描轉換算法函數代碼參考如下：

函數中在構造多邊形邊表和有效邊表時，都需要對插入邊進行排序，函數代碼如下：

執行應用程序即可實現填充。在應用程序中，可以設計一個非模式對話框，來選擇不同的掃描轉換算法，實現多邊形填充，效果如圖3.4-13所示。

除了上述的掃描線算法外，多邊形掃描轉換算法還有邊緣填充法、柵欄填充法以及邊界標志法等。

邊緣填充算法的基本思想：按任意順序處理多邊形的每條邊。處理時，先求出該邊與掃描線的交點，再對掃描線上交點右方的所有像素顏色取反。邊緣填充算法思路簡單，但對于復雜圖形，每一像素可能被訪問多次。

柵欄填充算法是借助柵欄的原理來實現的，柵欄指的是一條通過多邊形頂點且與掃描線垂直的直線，它把多邊形分為兩半。算法基本思想：按任意順序處理多邊形的每一條邊，當處理每條邊與掃描線的交點時，將交點與柵欄之間的像素取反。這種算法盡管減少了被重復訪問像素的數目，但仍有一些像素被重復訪問。

邊界標志算法的基本思想：先用特殊的顏色在幀緩存中將多邊形的邊界勾畫出來，然后將著色的像素點依x坐標遞增的順序配對，再把每一對像素構成的區間置為填充色。邊界標志算法分為兩個步驟：打標記；填充。當用軟件實現本算法時，速度與改進的有效邊表算法相當，但本算法用硬件實現后速度會有很大提高。

限于篇幅，本書對這些算法不再詳述。

3.4.2 區域填充

這里的區域指已經表示成點陣形式的填充圖形，它是像素的集合。區域可采用內點表示和邊界表示兩種表示形式。區域填充指先將區域的一點賦予指定的顏色，然后將該顏色擴展到整個區域的過程。

區域填充分為兩類：多邊形的掃描轉換與種子填充。兩者的前提條件不同，前者需提供多邊形各頂點的坐標及填充色或圖案；后者則要求給出邊界顏色特征及區域內的一個點（稱為種子點）的坐標。多邊形的掃描轉換主要是通過確定穿越區域的掃描線的覆蓋區間來填充，種子填充是從給定的位置開始涂描直到指定的邊界條件為止。

區域填充要求區域是連通的。區域連通有四向連通區域和八向連通區域兩種，如圖3.4-14所示。四向連通區域指的是從區域上一點出發，通過上、下、左、右移動，即可到達區域內的任意像素；八向連通區域除了四向連通區域的四個方向外，還需要通過左上、右上、左下、右下這四個方向，才能到達區域內的任意位置。

一般來說，八向連通算法可以填充四向連通區域，而四向連通算法有時不能填充八向連通區域。例如，八向連通填充算法能夠正確填充圖3.4-15所示的區域內部，而四向連通填充算法只能完成該區域的部分填充。

在編程時，上面的連通算法可以通過遞歸函數的方式實現。例如八向連通算法的遞歸函數的代碼參考如下：

上述遞歸算法簡單，但是效率不高，區域內每一個像素都引起一次遞歸，有些像素會多次重復遞歸判斷。這樣不但降低了算法效率，而且占用了很大的內存空間，費時費內存，在實際實現時，當圖像相對比較復雜時會存在內存溢出的現象。

遞歸算法的一種改進方法是掃描線種子填充算法，其基本過程如下：當給定種子點（x，y）時，首先分別向左和向右兩個方向填充種子點所在掃描線上的位于給定區域的一個區段，同時記下這個區段的范圍［xLeft，xRight］，然后確定與這一區段相連通的上、下兩條掃描線上位于給定區域內的區段，并依次保存下來。反復進行這個過程，直到填充結束。

掃描線種子填充算法可由下列四個步驟實現。

（1）初始化一個空的棧用于存放種子點，將種子點（x，y）入棧。

（2）判斷棧是否為空，如果棧為空則結束算法，否則取出棧頂元素作為當前掃描線的種子點（x，y），y是當前的掃描線。

（3）從種子點（x，y）出發，沿當前掃描線向左、右兩個方向填充，直到邊界。分別標記區段的左、右端點坐標為xLeft和xRight。

（4）分別檢查與當前掃描線相鄰的y－1和y+1兩條掃描線在區間［xLeft，xRight］中的像素，從xLeft開始向xRight方向搜索，若存在非邊界且未填充的像素點，則找出這些相鄰的像素點中最右邊的一個，并將其作為種子點壓入棧中，然后返回第（2）步。

上述掃描線種子填充算法，可以實現在已知區域的邊界像素顏色或者已知區域內部的顏色這兩種情況下，將區域內部用新的顏色填充。下面是已知區域內部顏色的填充函數參考代碼，對于已知區域邊界像素顏色的情況，只需將函數中判斷區域內部顏色的代碼改成判斷區域邊界顏色的代碼即可。

其中，在一條掃描線上填充當前區段的函數代碼如下：

處理相鄰兩條掃描線，并獲得新種子入棧的函數代碼如下：