【正文】 掃描線 2 AET指針 活動(dòng)邊表的例子 6 2 0 P4 P5 5 ^ P3 P2 掃描線 4 AET指針 6 2 0 P4 P5 7 8 1 ^ P2 P1 掃描線 5 AET指針 7 2 4 P5 P1 7 8 1 ^ P2 P1 掃描線 6 AET指針 算法實(shí)現(xiàn)步驟 這樣，當(dāng)建立了邊的分類表 ET后，掃描線算法可按下列步驟進(jìn)行： （ 1）取掃描線縱坐標(biāo) y的初始值為 ET中非空元素的最小序號(hào)。 由 yin的交點(diǎn)序列 開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形 P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。若多邊形 P的邊 Pr1Pr與掃描線 y=e,y=d都相交，則交點(diǎn)序列中對(duì)應(yīng)元素 xer,xdr滿足下列關(guān)系： xer= xdr + 1/mr (1) 其中 mr為邊 Pr1Pr的斜率。 掃描線算法 掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。 ? 點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。 y=yik+1 y=yik 區(qū)域的連貫性 根據(jù)這些性質(zhì)，實(shí)際上只需知道該長(zhǎng)方形區(qū)域內(nèi)任一梯形內(nèi)一點(diǎn)關(guān)于多邊形 P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于 P的內(nèi)外關(guān)系 。 ?以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形 P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。 直線方程： ax+by+c = 0 當(dāng)前交點(diǎn)坐標(biāo)： (xi, yi) 下一交點(diǎn)坐標(biāo)： (xi+1,yi+1) xi+1= ((byi+1)c)/a = ((byi+1)c)/a =xib/a=xi+1/mi 活動(dòng)邊表中需要存放的信息： x：當(dāng)前掃描線與邊的交點(diǎn) dx＝ b/a：從當(dāng)前掃描線到下一條掃描線之間的 x增量 ymax：邊所交的最高掃描線 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 ? 為了方便邊的活化鏈表的更新，建立另一個(gè)表邊表，存放在該掃描線第一次出現(xiàn)的邊。 4）將邊的活化鏈表 AEL剩下的每一條邊的 x域累加 Δx，即 x:=x+Δx。 } } 邊界標(biāo)志算法 ? 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同， ? 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。 (color != newColor)) { PutPixel(x,y,newColor)。 (4)并確定新的種子點(diǎn)：在區(qū)間 [xl， xr]中檢查與當(dāng)前掃描線 y上、下相鄰的兩條掃描線上的象素。 ? 后者：區(qū)域內(nèi)種子點(diǎn)。 (2)出棧：若?？談t結(jié)束。 } }/*end of FloodFill4() */ 種子填充算法 – 邊界表示的 4連通區(qū)域 void BoundaryFill4(int x,int y,int boundaryColor,int newColor) { int color。 { 對(duì)多邊形 polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE。 算法實(shí)現(xiàn)步驟 1）如邊分類表 ET中的第 y類元素非空，則將屬于該類的所有邊從 ET中取出并插入邊的活化鏈表中， AEL中的各邊按照 x值（當(dāng) x值相等時(shí)，按 Δx值）遞增方向排序。 如何判斷多邊形的一條邊與掃描線是否相交？ 與當(dāng)前掃描線相交的邊稱為活性邊（ active edge)，把它們按與掃描線交點(diǎn) x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表 （ AEL, Active edge table)。 y=e y=d 邊的連貫性 特別是當(dāng)存在某一個(gè)整數(shù) k,0≤k≤n 1,使得 yike, dyik+1 成立時(shí)，則由區(qū)域的連貫性可知 d的交點(diǎn)序列和 e的交點(diǎn)序列之間有以下