第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充(編輯修改稿)
2024-08-28 13:31 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 動(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)的邊。 存放的信息： x：掃描線與該邊的初始交點(diǎn) dx： x的增量 ymax：該邊的最大 y值 即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表 ET（ Edge Table）和邊的活化鏈表 AEL（ Active Edge List） 兩部分組成。 表結(jié)構(gòu) ET和 AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成： ymax 邊的上端點(diǎn)的 y坐標(biāo)； x 在 ET中表示邊的下端點(diǎn)的 x坐標(biāo)，在AEL中則表示邊與掃描線的交點(diǎn)的坐標(biāo)； Δx 邊的斜率的倒數(shù)； next 指向下一條邊的指針。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 邊的分類表 ET是按邊的下端點(diǎn)的 y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的 y坐標(biāo)的值等于 i的邊歸入第 i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按 x值（ x值相等時(shí)，按 Δx的值）遞增的順序排列成行。 邊表 7 2 4 ^ P5 P1 7 8 1 ^ P2 P1 6 2 0 ^ P4 P5 3 6 2 P3 P4 5 6 ^ P3 P2 ^ ^ ^ (Ymax, x,Δx, next) 活動(dòng)邊表的例子 3 4 2 P3 P4 5 ^ P3 P2 掃描線 2 AET指針 6 2 0 P4 P5 5 7 ^ P3 P2 掃描線 3 AET指針 (Ymax, x,Δx, next) 3 6 2 P3 P4 5 6 ^ P3 P2 掃描線 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)。 （ 2）將邊的活化鏈表 AEL設(shè)置為空。 （ 3）按從下到上的順序?qū)v坐標(biāo)值為 y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表 ET和邊的活化鏈表都變成空為止。 算法實(shí)現(xiàn)步驟 1）如邊分類表 ET中的第 y類元素非空，則將屬于該類的所有邊從 ET中取出并插入邊的活化鏈表中， AEL中的各邊按照 x值（當(dāng) x值相等時(shí)，按 Δx值）遞增方向排序。 2）若相對(duì)于當(dāng)前掃描線，邊的活化鏈表 AEL非空，則將AEL中的邊兩兩依次配對(duì)，即 1， 2邊為一對(duì)， 3， 4邊為一對(duì)，依次類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。 3）將邊的活化鏈表 AEL中滿足 y=ymax的邊刪去。 4）將邊的活化鏈表 AEL剩下的每一條邊的 x域累加 Δx，即 x:=x+Δx。 5）將當(dāng)前的掃描線的縱坐標(biāo)值 y累加 1，即 y:=y+1。 掃描線算法 ? 特點(diǎn)：算法效率較高。 ? 缺點(diǎn)：對(duì)各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。 掃描線算法 問(wèn)題： 如何處理多邊形的水平邊？ 如何修改掃描線算法，使它能處理邊自交的多邊形？ 1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過(guò)的象素作一個(gè)邊界標(biāo)志。 。對(duì)每條
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1