1、4.4 區域填充區域填充 4.4.1 有序邊表填充算法有序邊表填充算法 本節討論如何用一種顏色或圖案來填充一個二本節討論如何用一種顏色或圖案來填充一個二維區域。填充的區域可以是多邊形的，也可以是圓維區域。填充的區域可以是多邊形的，也可以是圓或橢圓的，還可以是帶孔的。區域填充可以分兩步或橢圓的，還可以是帶孔的。區域填充可以分兩步進行，第一步先確定需要填充哪些像素。第二步確進行，第一步先確定需要填充哪些像素。第二步確定用什么顏色值或圖案來填充。定用什么顏色值或圖案來填充。 多邊形區域填充的一種常用方法是按掃描線順多邊形區域填充的一種常用方法是按掃描線順序，計算掃描線與多邊形的相交區間，再用要求的序

2、，計算掃描線與多邊形的相交區間，再用要求的顏色顯示這些區間的像素，即完成填充工作。顏色顯示這些區間的像素，即完成填充工作。A B C DP1P2P3P4P5P62 4 6 8 10 2468Oyx 如圖所示，掃描線如圖所示，掃描線3與與多邊形的邊界線交于四點多邊形的邊界線交于四點A、B、C、D。交點交點(x坐標坐標)序序列為：列為：3、4.5、 6、8.3 把交點從小到大逐對取把交點從小到大逐對取出，構成區間：出，構成區間： 3, 4.5, 6, 8.3。這。這兩個區間落在多邊兩個區間落在多邊形內，該區間內的像素應形內，該區間內的像素應該填充，其他區間不填充。該填充，其他區間不填充。 圖圖 多

3、邊形與掃描線多邊形與掃描線 在多邊形頂點處的交點需要專門處理。在多邊形頂點處的交點需要專門處理。 例如圖所示，掃描線例如圖所示，掃描線2與多邊形相交于與多邊形相交于P6，若，若交點算一個，則求得交點交點算一個，則求得交點( (x坐標坐標) )序列序列3, 6.5, 7.5。這將導致這將導致 3, 6.5區間內的像素被填充，而這個區間區間內的像素被填充，而這個區間的像素是屬于多邊形外部，不需要填充。的像素是屬于多邊形外部，不需要填充。A B C DP1P2P3P4P5P62 4 6 8 10 2468Oyx 為了正確地進行交點取舍，必須對上述兩種情為了正確地進行交點取舍，必須對上述兩種情況區別對

4、待。況區別對待。 具體實現時，只需檢查頂點的兩條邊的另外具體實現時，只需檢查頂點的兩條邊的另外兩個端點的兩個端點的y值。按這兩個值。按這兩個y值中大于交點值中大于交點y值的個值的個數是數是0，1，2來決定是取零個、一個、還是兩個。來決定是取零個、一個、還是兩個。A B C DP1P2P3P4P5P62 4 6 8 10 2468Oyx 例如，掃描線例如，掃描線2交頂點交頂點P6，由于共享該頂點的，由于共享該頂點的兩條邊的另外二個頂點均高于掃描線，故交點兩條邊的另外二個頂點均高于掃描線，故交點P6取取兩次，兩次，則交點序列為則交點序列為：3 3、3、 6.5、 7.5 。即。即3, 3 6.5,

5、 7.5二個區間內的像素被填充二個區間內的像素被填充。 而而掃描線掃描線7與多邊形相交于與多邊形相交于P1，該交點算一個，該交點算一個，則交點序列為：則交點序列為：2, 10，即，即2, 10區間內的像素被填區間內的像素被填充充。 A B C DP1P2P3P4P5P62 4 6 8 10 2468Oyx 由于邊的連貫性，即當某條邊與當前掃描線由于邊的連貫性，即當某條邊與當前掃描線相交時，它很可能也與下一條掃描線相交，為此，相交時，它很可能也與下一條掃描線相交，為此，計算下一條掃描線與同一條邊的交點計算下一條掃描線與同一條邊的交點x值時，只需值時，只需把當前交點把當前交點x值加上一個邊的反斜率

6、即可：值加上一個邊的反斜率即可： xk+1 = xk + 1 / m (m為邊的斜率為邊的斜率) ) A B C DP1P2P3P4P5P62 4 6 8 10 2468Oyx 歸納上述討論，我們可寫出多邊形區域填充的歸納上述討論，我們可寫出多邊形區域填充的步驟為：步驟為： 輸入欲填充多邊形的頂點數及其頂點坐標。輸入欲填充多邊形的頂點數及其頂點坐標。這里，頂點數為實際頂點數加這里，頂點數為實際頂點數加1，最后一個頂點坐，最后一個頂點坐標與第一個頂點坐標相同。標與第一個頂點坐標相同。 計算所有多邊形頂點坐標中計算所有多邊形頂點坐標中y的最大值和最的最大值和最小值，以此作為掃描線的處理范圍。小值，

7、以此作為掃描線的處理范圍。 對處理范圍內的每條掃描線建立有序邊表。對處理范圍內的每條掃描線建立有序邊表。 對處理范圍內的每條掃描線，重復下列步驟：對處理范圍內的每條掃描線，重復下列步驟： A用有序邊表建立當前掃描線的活化邊表；用有序邊表建立當前掃描線的活化邊表； B從活化邊表中依次取出一對交點，對該兩個從活化邊表中依次取出一對交點，對該兩個交點內的像素進行填充；交點內的像素進行填充； C為下一條掃描線更新活化邊表，即增加交點為下一條掃描線更新活化邊表，即增加交點的的x值和刪除不再相交的邊；值和刪除不再相交的邊； D重排活化邊表。重排活化邊表。 有序邊表填充算法的有序邊表填充算法的C語言描述（略

8、）語言描述（略） 4.4.2 邊填充算法邊填充算法 邊填充算法的基本思想是：求每一條掃描線和邊填充算法的基本思想是：求每一條掃描線和多邊形各邊的交點多邊形各邊的交點(x1, y1)，將該掃描線上交點右方，將該掃描線上交點右方的所有像素取補。的所有像素取補。 對多邊形的每條邊作此處理，多邊形的順序隨對多邊形的每條邊作此處理，多邊形的順序隨意。如圖所示，為應用最簡單的邊填充算法填充一意。如圖所示，為應用最簡單的邊填充算法填充一個多邊形的示意圖。個多邊形的示意圖。 P5P4P3P1P2P2 P3P3 P4P4 P5P5 P1圖圖 邊填充算法邊填充算法示意圖示意圖 本算法的優點是簡單，缺點是對于復雜圖

9、形，本算法的優點是簡單，缺點是對于復雜圖形，每一像素可能被訪問多次，輸入每一像素可能被訪問多次，輸入/輸出的量比有序輸出的量比有序邊表算法大得多。邊表算法大得多。 為了減少邊填充算法訪問像素的次數，可引入為了減少邊填充算法訪問像素的次數，可引入柵欄。所謂柵欄指的是一條與掃描線垂直的直線，柵欄。所謂柵欄指的是一條與掃描線垂直的直線，柵欄位置通常取過多邊形頂點、且把多邊形分為左柵欄位置通常取過多邊形頂點、且把多邊形分為左右兩半。右兩半。 柵欄填充法的基本思想是：對于每個掃描線與柵欄填充法的基本思想是：對于每個掃描線與多邊形的交點，就將交點與柵欄之間的像素取補。多邊形的交點，就將交點與柵欄之間的像素

10、取補。若交點位于柵欄左側，則將交點之右至柵欄之左的若交點位于柵欄左側，則將交點之右至柵欄之左的所有像素取補；若交點位于柵欄右邊，則將柵欄之所有像素取補；若交點位于柵欄右邊，則將柵欄之右至交點之左的像素取補。圖右至交點之左的像素取補。圖3.10為柵欄填充法示為柵欄填充法示意圖。意圖。 P5P4P3P1P2P2 P3P4 P5P3 P4P5 P1圖圖 柵欄填充算法示意圖柵欄填充算法示意圖 4.4.3 種子填充算法種子填充算法 種子填充算法則采用不同的原理：填充方法種子填充算法則采用不同的原理：填充方法是從多邊形區域內部的一點開始，由此出發找到是從多邊形區域內部的一點開始，由此出發找到區域內的所有像

11、素。這種填充算法在交互式繪圖區域內的所有像素。這種填充算法在交互式繪圖中很常用。中很常用。 種子填充算法采用的邊界定義是區域邊界上種子填充算法采用的邊界定義是區域邊界上所有像素均具有某個特定的顏色值，區域內部所所有像素均具有某個特定的顏色值，區域內部所有像素均不取這一特定顏色，而邊界外的像素則有像素均不取這一特定顏色，而邊界外的像素則可具有與邊界相同的顏色值。可具有與邊界相同的顏色值。 程序從程序從( (x，y) )開始，先檢測該點的顏色，如果開始，先檢測該點的顏色，如果它與邊界色和填充色均不相同，就用填充色填充該它與邊界色和填充色均不相同，就用填充色填充該點，然后檢測相鄰位置，以確定它們是否

12、是邊界色點，然后檢測相鄰位置，以確定它們是否是邊界色和填充色，若不是，就填充該相鄰點。這個過程延和填充色，若不是，就填充該相鄰點。這個過程延續到已經檢測完區域邊界范圍內的所有像素為止。續到已經檢測完區域邊界范圍內的所有像素為止。 從當前點檢測相鄰像素有兩種方法：四向連從當前點檢測相鄰像素有兩種方法：四向連通和八向連通。四向連通方法指的是從區域上一通和八向連通。四向連通方法指的是從區域上一點出發，可通過四個方向，即上、下、左、右移點出發，可通過四個方向，即上、下、左、右移動的組合，在不越出區域的前提下，到達區域內動的組合，在不越出區域的前提下，到達區域內的任意像素；的任意像素； 4連通 從區域內

13、任意一點出發，可通過上、下、左、從區域內任意一點出發，可通過上、下、左、右四個方向到達區域內的任意象素；右四個方向到達區域內的任意象素； 8連通 從區域內任意一點出發，可通過上、下、左、從區域內任意一點出發，可通過上、下、左、右、左上、左下、右上、右下八個方向到達區右、左上、左下、右上、右下八個方向到達區域內的任意象素。域內的任意象素。 4連通區域和8連通區域 四連通區域 八連通區域 區域的表示方法內點表示 枚舉出區域內部的所有枚舉出區域內部的所有像素像素 內部的所有像素著同一內部的所有像素著同一個顏色個顏色邊界表示 枚舉出邊界上所有的像素枚舉出邊界上所有的像素 邊界上的所有像素著同一顏色邊界

14、上的所有像素著同一顏色 內部像素著與邊界像素不同的顏色內部像素著與邊界像素不同的顏色 八向連通方法指的是區域內每一個像素，可以八向連通方法指的是區域內每一個像素，可以通過左、右、上、下、左上、右上、左下、右下這通過左、右、上、下、左上、右上、左下、右下這八個方向的移動的組合來到達。八個方向的移動的組合來到達。 種子填充算法中允許從四個方向尋找下一像素種子填充算法中允許從四個方向尋找下一像素者，稱為四向算法；允許從八個方向搜索下一像素者，稱為四向算法；允許從八個方向搜索下一像素者，稱為八向算法。八向算法可以填充八向連通區者，稱為八向算法。八向算法可以填充八向連通區域，也可以填充四向連通區域。但四

15、向算法只能填域，也可以填充四向連通區域。但四向算法只能填充四向連通區域，而不能填充八向填充區域。以下充四向連通區域，而不能填充八向填充區域。以下我們只討論四向算法。只要把搜索方向從四個改變我們只討論四向算法。只要把搜索方向從四個改變八個，即可得到八向算法。八個，即可得到八向算法。 下面程序給出了四向連通填充的遞歸算法。下面程序給出了四向連通填充的遞歸算法。void boundaryfill4 (int seedx, int seedy, int fcolor, int bcolor) int current = getpixel (seedx, seedy); if (current != b

16、color) & (current != fcolor) putpixel (seedx, seedy, fcolor);boundaryfill4 (seedx +1, seedy, fcolor, bcolor);boundaryfill4 (seedx 1, seedy, fcolor, bcolor);boundaryfill4 (seedx, seedy +1, fcolor, bcolor);boundaryfill4 (seedx, seedy 1, fcolor, bcolor); void SeedFill (int cnt, POINT *pts, int seed

17、x, int seedy, int fcolor, int bcolor) POINT v1,v2; int i; for (i=0; i cnt 1; i +) v1 = pts i ; v2 = pts i +1; BoundaryMark (v1.x, v1.y, v2.x, v2.y, bcolor); boundaryfill4 (seedx, seedy, fcolor, bcolor); 這種算法的優點是算法簡單，易于實現，也可這種算法的優點是算法簡單，易于實現，也可以填充帶有內孔的平面區域。但是這種算法需要很以填充帶有內孔的平面區域。但是這種算法需要很大的存儲空間以實現棧結構，

18、同一個像素多次入棧大的存儲空間以實現棧結構，同一個像素多次入棧和出棧，所花費的時間也很多。因此后來提出了許和出棧，所花費的時間也很多。因此后來提出了許多改進的算法，如書上的掃描線種子填充算法，鏈多改進的算法，如書上的掃描線種子填充算法，鏈隊列種子填充算法。隊列種子填充算法。 鏈隊列種子填充算法的算法基本思路是：從鏈鏈隊列種子填充算法的算法基本思路是：從鏈隊列中獲得一個像素點，判斷其四連通像素點，若隊列中獲得一個像素點，判斷其四連通像素點，若沒有填充，則填充它，并將它入隊列，如此循環，沒有填充，則填充它，并將它入隊列，如此循環，直到隊列空為止。直到隊列空為止。 4.4.4 圓和橢圓的填充圓和橢圓

19、的填充 上面所討論的多邊形區域的填充原理也可以推上面所討論的多邊形區域的填充原理也可以推廣到圓域的填充。由于圓和橢圓的特殊屬性，即可廣到圓域的填充。由于圓和橢圓的特殊屬性，即可依據任何欲填充的像素點與圓心的距離是否大于或依據任何欲填充的像素點與圓心的距離是否大于或小于半徑來判斷是否在圓外或圓內，或者依據欲填小于半徑來判斷是否在圓外或圓內，或者依據欲填充的像素點與橢圓兩焦點的距離之和是否大于或小充的像素點與橢圓兩焦點的距離之和是否大于或小于橢圓的半徑常數來判斷是否在橢圓外或橢圓內，于橢圓的半徑常數來判斷是否在橢圓外或橢圓內，因此圓和橢圓的填充采用種子填充算法最為簡單，因此圓和橢圓的填充采用種子填

20、充算法最為簡單，并且它不需要先對圓或橢圓邊界進行掃描轉換。并且它不需要先對圓或橢圓邊界進行掃描轉換。 以下是圓的四向連通填充算法的以下是圓的四向連通填充算法的C語言描述。語言描述。void CircleFill4 (int xc, int yc, int r, int seedx, int seedy, int color) int fill = getpixel (seedx, seedy); if (seedx xc) * (seedx xc) + (seedy yc) * (seedy yc) next; while ( p1 ) p2 = p1 next; for ( i = p1 x

21、; i x; i +)if (pattern i % 8 scan % 8 ) putpixel ( i, scan, color ); p1 = p2 next; 上述程序的一個運行結果如圖上述程序的一個運行結果如圖3.12所示。所示。 圖圖3.12 圖案填圖案填充的一個實例充的一個實例 4.4.6 線寬與線型的處理線寬與線型的處理 1、 直線線寬的處理直線線寬的處理 在實際應用中，除了使用單像素寬的線條，還在實際應用中，除了使用單像素寬的線條，還經常使用指定線寬和線型的直線與弧線。欲產生具經常使用指定線寬和線型的直線與弧線。欲產生具有寬度的線，可以順著掃描所生成的單像素線條軌有寬度的線，可

22、以順著掃描所生成的單像素線條軌跡跡, ,移動一把具有一定寬度的移動一把具有一定寬度的“刷子刷子”來獲得。來獲得。“刷刷子子”的形狀可以是一條線段或一個正方形。也可以的形狀可以是一條線段或一個正方形。也可以采用區域填充的辦法間接地產生有寬度的線。采用區域填充的辦法間接地產生有寬度的線。 線刷子的原理最簡單。假設直線斜率在線刷子的原理最簡單。假設直線斜率在1, 1之間，這時可以把刷子置成垂直方向，刷子的中點之間，這時可以把刷子置成垂直方向，刷子的中點對準直線一端點，然后讓刷子中心往直線的另一端對準直線一端點，然后讓刷子中心往直線的另一端移動，即可移動，即可“刷出刷出”具有一定寬度的線。具有一定寬度

23、的線。 當直線斜率不在當直線斜率不在1，1之間時，把刷子置成之間時，把刷子置成水平方向。具體實現線刷子時，只要對直線掃描水平方向。具體實現線刷子時，只要對直線掃描轉換算法的內循環稍作修改。例如，當直線斜率轉換算法的內循環稍作修改。例如，當直線斜率在在1, 1之間時，把每步迭代所得的點的上下方半之間時，把每步迭代所得的點的上下方半線寬之內的像素全部置成直線顏色線寬之內的像素全部置成直線顏色 若線寬為若線寬為5個像素，則把原來的個像素，則把原來的putpixel(x, y，color)語句擴展為下列循環語句：語句擴展為下列循環語句： for(i=-2;i=2;i+) putpixel (x，y+i

24、，color); 圖圖3.22所示為線寬是所示為線寬是5個像素的情形。算法簡個像素的情形。算法簡單、效率高是線刷子的優點。但是，線的始末端單、效率高是線刷子的優點。但是，線的始末端總是水平或垂直的。因此，當線寬較大時，看起總是水平或垂直的。因此，當線寬較大時，看起來很不自然。當比較接近水平的線與比較接近垂來很不自然。當比較接近水平的線與比較接近垂直的線匯合時，匯合處外均將有缺口。如圖直的線匯合時，匯合處外均將有缺口。如圖3.23所示。所示。 圖圖3.22 5個像素寬的線刷子個像素寬的線刷子圖圖3.23 線刷子的缺口線刷子的缺口 線刷子還會使斜線與水平（或垂直）線不一樣線刷子還會使斜線與水平（或

25、垂直）線不一樣粗。對于水平線或垂直線，刷子與線條垂直，因而粗。對于水平線或垂直線，刷子與線條垂直，因而最粗。其粗細與指定線寬相等。而對于最粗。其粗細與指定線寬相等。而對于45斜線，斜線，刷子與線條成刷子與線條成45角，粗細僅為指定線寬的角，粗細僅為指定線寬的0.7倍。倍。 為了生成有寬度的線，還可以用方形的刷子。為了生成有寬度的線，還可以用方形的刷子。把邊寬為指定線寬的正方形的中心沿直線作平行移把邊寬為指定線寬的正方形的中心沿直線作平行移動，即可獲得具有線寬的線條，如圖動，即可獲得具有線寬的線條，如圖3.24所示為用所示為用正方形刷子繪制的具有寬度的線條。比較圖正方形刷子繪制的具有寬度的線條。

26、比較圖3.24與與圖圖3.22可知，用方形刷子所得的線條比用線刷子所可知，用方形刷子所得的線條比用線刷子所繪制的線條要粗一些。繪制的線條要粗一些。線寬為線寬為5個像素的方刷子個像素的方刷子 與線刷子類似，用方刷子繪制的線條始未端也與線刷子類似，用方刷子繪制的線條始未端也是水平或垂直的，且線寬與線條方向有關。與線刷是水平或垂直的，且線寬與線條方向有關。與線刷子的情形相反，對于水平線與垂直線，線寬最小，子的情形相反，對于水平線與垂直線，線寬最小，而對于斜率為而對于斜率為1的線條，線寬最大，為垂直（水的線條，線寬最大，為垂直（水平）線寬度的平）線寬度的1.41倍。倍。 實現正方形刷子最簡單的辦法是，

27、把方形中心實現正方形刷子最簡單的辦法是，把方形中心對準單像素寬的線條上各個像素，并把方形內的像對準單像素寬的線條上各個像素，并把方形內的像素全部置成線條顏色。若線寬為素全部置成線條顏色。若線寬為5，則可把原來的，則可把原來的putpixel (x，y，color)語句改為下列語句組：語句改為下列語句組： for (i = 2; i=2; i+) for (j = 2; j =2; j+) putpixel (x+i, y+j, color); 這種簡單方法將會重復地寫像素。這是因為對這種簡單方法將會重復地寫像素。這是因為對應于相鄰兩像素的方形一般會重疊。為了避免重復應于相鄰兩像素的方形一般會重

28、疊。為了避免重復寫像素，可以采用與活化邊表類似的技術。為每條寫像素，可以采用與活化邊表類似的技術。為每條掃描線建一個表，存放該掃描線與線條的相交區間掃描線建一個表，存放該掃描線與線條的相交區間左右端點位置。在每個像素使用方形刷子時，用該左右端點位置。在每個像素使用方形刷子時，用該方形與各掃描線的相交區間端點坐標去更新原表內方形與各掃描線的相交區間端點坐標去更新原表內端點數據。端點數據。 生成具有寬度的線條還可以采用區域填充的算生成具有寬度的線條還可以采用區域填充的算法。先算出線條各角點，再用直線段把相鄰角點連法。先算出線條各角點，再用直線段把相鄰角點連接起來，最后調用多邊形填充算法把所得的四邊

29、形接起來，最后調用多邊形填充算法把所得的四邊形進行填色，即得到具有寬度的線條。用這種方法還進行填色，即得到具有寬度的線條。用這種方法還可以生成兩端粗細不一樣的線條。可以生成兩端粗細不一樣的線條。 2、 圓弧線寬的處理圓弧線寬的處理 為了生成具有寬度的圓弧，可采用與直線情為了生成具有寬度的圓弧，可采用與直線情形類似的方法，當采用線刷子時，在經過曲線斜形類似的方法，當采用線刷子時，在經過曲線斜率為率為1的點時，必須把線刷子在水平與垂直方的點時，必須把線刷子在水平與垂直方向之間切換。由于線刷子總是置成水平或垂直的，向之間切換。由于線刷子總是置成水平或垂直的，所以在曲線接近水平與垂直的地方，線條更粗一

30、所以在曲線接近水平與垂直的地方，線條更粗一些，而在斜率接近些，而在斜率接近1的點附近，線條更細一些，的點附近，線條更細一些，如圖如圖(a)所示。所示。 當采用正方形刷子時，無需改變刷子方向。只當采用正方形刷子時，無需改變刷子方向。只需順著單像素寬的軌跡，把正方形中心對準軌跡上需順著單像素寬的軌跡，把正方形中心對準軌跡上的像素，把方形內的像素全部用線條顏色填充。的像素，把方形內的像素全部用線條顏色填充。(a)用線刷子繪制的圓弧用線刷子繪制的圓弧圖圖 圓弧的線寬圓弧的線寬 用正方形刷子繪制的曲線條，在接近水平與用正方形刷子繪制的曲線條，在接近水平與垂直的部分最細，而在斜率為全垂直的部分最細，而在斜率為全1的點附近最粗，的點附近最粗，這恰與線刷子情形相反，如圖這恰與線刷子情形相反，如圖(b)所示。所示。 (b)用方刷子繪制的圓弧用方刷子繪制的圓弧3、 線型的處理線型的處理 繪制具有寬度的圓弧線條也可以采用填充的辦繪制具有寬度的圓弧線條也可以采用填充的辦法，先繪制圓弧線條的內邊界和外邊