第四講

區域填充計算機圖形學中，多邊形區域有兩種重要的表示方法：頂點表示和點陣表示。所謂頂點表示，即是用多邊形的頂點序列來表示多邊形。這種表示直觀、幾何意義強、占內存少，易于進行幾何變換，但由于它沒有明確指出哪些像素在多邊形內，故不能直接用于區域填充。所謂點陣表示，則是用位于多邊形內的像素集合來刻畫多邊形。這種表示丟失了許多幾何信息，但便于進行填充。根據區域的定義，可以采用不同的填充算法，其中最具代表性的是：適應于頂點表示的掃描線類算法和適應于點陣表示的種子填充類算法。

復雜邊界從內部指定位置開始填充，遞歸填充直至邊界簡單邊界通過掃描線與邊界交點確定填充區域掃描線算法掃描線多邊形區域填充算法基本原理是，待填充區域按Y方向(X方向亦可)掃描線順序掃描生成。具體實現時，首先按掃描線順序，計算掃描線與多邊形的相交區間；再用要求的顏色填充這些區間內的像素，即完成這一條掃描線的填充工作。區間的端點可以通過計算掃描線與多邊形邊界線的交點獲得。對于一條掃描線，多邊形的填充過程可以分為四個步驟：(1)求交：計算掃描線與多邊形各邊的交點；(2)排序：把所有交點按x值遞增順序排序；(3)配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區間；(4)填色：把相交區間內的像素置成多邊形顏色，把相交區間外的像素置成背景色。為了提高速度，假定當前掃描線與多邊形某一條邊的交點的x坐標為xi，則下一條掃描線與該邊的交點不要重新計算，而是通過增加一個增量△x來獲得。具體方法是：設該邊的直線方程為：ax+by+c=0；若y＝yi，x=xi；則當y=yi+1=yi+1時，其中為常數，yiyi+1(xi,yi)交點計算交點數的處理多邊形Pi的頂點可分為兩類：如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點Pi為局部最高點或最低點，按兩個交點計算，否則按一個交點計算。不計算水平邊和掃描線的交點水平邊處理數據結構與實現步驟輸入參數頂點數和頂點坐標數據結構有序邊表活化邊表有序邊表有序邊表的構建按頂點輸入順序依次形成邊，存儲到每條最小Y值所對應的掃描線位置（水平邊除外），相同最小Y值的邊按較低頂點X值的升序排列。有序邊表結構typedef

struct

tEage{int

yUpper;floatxIntersect;floatdxPerScan;struct

tEage*next;}Eage活化邊表把與當前掃描線相交的邊稱為活化邊，并把它們按與掃描線交點X坐標遞增的順序存放在一個鏈表中，形成活化邊表。算法中采用較靈活的數據結構。它由邊的分有序邊表ET（EdgeTable）和邊的活化邊表AEL（ActiveEdgeTable

）兩部分組成。表結構ET和AET中的基本元素為多邊形的邊。邊的結構由以下四個域組成：

ymax

邊的上端點的y坐標；

x在ET中表示邊的下端點的x坐標，在AET中則表示邊與掃描線的交點的坐標；

Δx邊的斜率的倒數；

next指向下一條邊的指針。

表結構舉例：724^P5P178-1^P2P1620^P4P536-2P3P4560.5^P3P2^^^(Ymax,x,Δx,next)

有序邊表活化邊表34-2P3P456.50.5^P3P2掃描線2AET指針620P4P5570.5^P3P2掃描線3AET指針(Ymax,x,Δx,next)36-2P3P4560.5^P3P2掃描線1AET指針620P4P557.50.5^P3P2掃描線4AET指針620P4P578-1^P2P1掃描線5AET指針724P5P178-1^P2P1掃描線6AET指針

voidpolyfill(polygon,color){

for(各條掃描線，標識為i) {

初始化新邊表頭指針NET[i]；把ymin=i的邊放進邊表NET[i]；

}y=最低掃描線號；初始化活性邊表AET為空；

for(各條掃描線i){

把新邊表NET[i]中的邊結點用插入排序法插入AET表，使之按x坐標遞增順序排列；

遍歷AET表，把配對交點區間上的像素(x,y)，用drawpixel(x,y,color)改寫像素顏色值；

遍歷AET表，把ymax=i的結點從AET表中刪除，并把ymax>i結點的x值遞增x；

}}多邊形填充的算法流程掃描線算法特點：算法效率較高。缺點：對各種表的維持和排序開銷太大，適合軟件實現而不適合硬件實現。內外測試目標：鑒別非標準多邊形的內部區域自相交多邊形。方法奇偶規則非零環繞數規則奇偶規則從位置P作不經過頂點的射線計算射線穿過多邊形的邊數奇數為內部點，否則為外部點非零環繞數規則環繞數初始為零；從位置P作不經過頂點的射線；多邊形從右至左穿過射線，加1；多邊形從左至右穿過射線，減1；非零為內部點；舉例：種子填充算法區域：用點陣形式表示的填充圖形，是像素的集合。區域可采用內點表示和邊界表示兩種表示形式。內點表示法，指區域內的所有像素著同一顏色；邊界表示法，則是指區域的邊界點著同一顏色。區域填充算法要求區域是連通的，因為只有在連通區域中，才可能將種子點的顏色擴展到區域內的其它點。區域可分為4向連通區域和8向連通區域。4向連通區域指的是從區域上一點出發，可通過四個方向，即上、下、左、右移動的組合，在不越出區域的前提下，到達區域內的任意像素；8向連通區域指的是從區域內每一像素出發，可通過八個方向，即上、下、左、右、左上、右上、左下、右下這八個方向的移動的組合來到達。

四個方向運動八個方向運動四連通區域八連通區域算法原理：填充區域邊界以一種顏色指定，從區域的一個內部點開始，由內至外繪制直到邊界。適用于單色邊界的填充。四連通的局限性voidFloodFill4(intx,int

y,int

oldcolor,int

newcolor){

if(GetPixel(x,y)==oldcolor) {

SetPixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor);}}設(x,y)為內點表示的4連通區域內的一點，oldcolor為區域的原色，要將整個區域填充為新的顏色newcolor。內點表示的4連通區域的遞歸填充算法:

簡單的種子填充算法voidBoundaryFill4(intx,int

y,int

boundarycolor,int

newcolor){

intcolor; if(color!=newcolor&&color!=boundarycolor) {

SetPixel(x,y,newcolor); BoundaryFill4(x,y+1,boundarycolor,newcolor); BoundaryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor);}}邊界表示的4連通區域的遞歸填充算法:

掃描線種子填充算法簡單種子填充算法原理和程序都很簡單，但由于多次遞歸，費時、費內存，效率不高。為了減少遞歸次數，提高效率可以采用掃描線種子填充算法。算法的基本過程如下：當給定種子點(x,y)時，首先填充種子點所在掃描線上的位于給定區域的一個區段，然后確定與這一區段相連通的上、下兩條掃描線上位于給定區域內的區段，并依次保存下來。反復這個過程，直到填充結束。1234123451234512341234123區域填充的掃描線算法可由下列四個步驟實現：(1)初始化：堆棧置空。將種子點(x，y)入棧；