多边形的扫描转换与区域填充课件.pptx

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

4.1多邊形的掃描轉換與區域填充

多邊形有兩種重要的表示方法：頂點表示和點陣表示。

多邊形的掃描轉換:把多邊形的頂點表示轉換為點陣表示。

區域可採用內點表示和邊界表示兩種表示形式。

區域填充:指先將區域的一點賦予指定的顏色，然後將該顏色擴展到整個區域的過程。

多邊形分為凸多邊形、凹多邊形、含內環的多邊形。

4.1.1多邊形的掃描轉換

掃描線演算法

基本思想：

按掃描線順序，計算掃描線與多邊形的相交區間，再用要求的顏色顯示這些區間的象素，即完成填充工作。

對於一條掃描線填充過程可以分為四個步驟：

（1）求交（2）排序

（3）配對（4）填色

判斷任意點是否在多邊形內

演算法思想

從該點（x,y）向（—∞,y）引直線，並計算該線與多邊形的交點數n(自左向右算起)

if(n%2==0)

{則（x,y）在多邊形外}

else

{則（x,y）在多邊形內}

掃描線與多邊形的頂點或邊界相交時，必須正確的交點的取捨。只需檢查頂點的兩條邊的另外兩個端點的y值。按這兩個y值中大於交點y值的個數是0,1,2來決定。

實際上將多邊形的每條邊與所有掃描線都求交點沒有必要的。因為可能大多數掃描線與多邊形根本不相交。為了提高演算法效率，應只處理與多邊形相交的那些掃描線，同時，交點的計算可以通過增量法來實現

掃描線填色法

一個多邊形與若干掃描線

數據結構

活性邊表(AET)：把與當前掃描線相交的邊稱為活性邊，並把它們按與掃描線交點x座標遞增的順序存放在一個鏈表中

結點內容

x：當前掃描線與邊的交點座標

△x：從當前掃描線到下一條掃描線間x的增量

ymax：該邊所交的最高掃描線號ymax

新邊表（NET）：

存放在該掃描線第一次出現的邊。若某邊的較低端點為ymin，則該邊就放在掃描線ymin的新邊表中

上圖所示各條掃描線的新邊表NET

假定當前掃描線與多邊形某一條邊的交點的x座標為x，則下一條掃描線與該邊的交點不要重計算，只要加一個增量△x。

設該邊的直線方程為：ax+by+c=0；

若y＝yi，x=xi；則當y=yi+1時，

其中為常數

F

D

C

E

A

B

9

7

5

3

1

2

4

6

8

多邊形掃描轉換

演算法過程(偽代碼)

voidpolyfill(polygon,color)

intcolor;多邊形polygon;

{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表中刪除，並把ymaxi結點的x值遞增x；

若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；

}

}/*polyfill*/

邊界標誌演算法

基本思想：

幀緩衝器中對多邊形的每條邊進行直線掃描轉換，亦即對多邊形邊界所經過的象素打上標誌。

然後再採用和掃描線演算法類似的方法將位於多邊形內的各個區段著上所需顏色。

使用一個布爾量inside來指示當前點是否在多邊形內的狀態。

演算法過程

voidedgemark_fill(polydef,color)

多邊形定義polydef；intcolor;

{對多邊形polydef每條邊進行直線掃描轉換；

inside=FALSE;

for(每條與多邊形polydef相交的掃描線y)

for(掃描線上每個象素x)

{if(象素x被打上邊標誌)

inside=!(inside);

if(inside！=FALSE)

drawpixel(x,y,color);

elsedrawpixel(x,y,background);

}

}

用軟體實現時，掃描線演算法與邊界標誌演算法的執行速度幾乎相同，

但由於邊