光柵圖形的轉(zhuǎn)換與區(qū)域填充(編輯修改稿)
2025-06-18 16:41 本頁面
【文章內(nèi)容簡介】 現(xiàn)奇數(shù)個交點(diǎn)。那么如何保證交點(diǎn)數(shù)為偶數(shù)呢？ 奇點(diǎn)的處理 ? 若奇點(diǎn)做一個交點(diǎn)處理，則情況 A，交點(diǎn)個數(shù)不是偶數(shù)。 ? 若奇點(diǎn)做兩個交點(diǎn)處理，則情況 B，交點(diǎn)個數(shù)不是偶數(shù)。 奇點(diǎn)的處理 ? 多邊形 P的頂點(diǎn)可分為兩類： 極值奇點(diǎn) 和 非極值奇點(diǎn) 。如果 (yi1 yi)(yi+1 yi)≥0 ，則稱頂點(diǎn) Pi為極值點(diǎn)；否則稱 Pi為非極值點(diǎn)。 ? 規(guī)定 ：奇點(diǎn)是極值點(diǎn)時，該點(diǎn)按兩個交點(diǎn)計(jì)算，否則按一個交點(diǎn)計(jì)算。 ? 奇點(diǎn)的預(yù)處理： 奇點(diǎn)的處理 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 算法基本思想：首先取 d=yin。 容易求得掃描線 y=d上的交點(diǎn)序列為xdj1,xdj2,… xdjn ， 這一序列由位于掃描線y=d上的多邊形 P的頂點(diǎn)組成。 由 yin的交點(diǎn)序列 開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形 P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。 所有的邊和掃描線求交，效率很低。因?yàn)橐粭l掃描線往往只和少數(shù)幾條邊相交。 如何判斷多邊形的一條邊與掃描線是否相交？ 與當(dāng)前掃描線相交的邊稱為 活性邊 （ active edge)，把它們按與掃描線交點(diǎn) x坐標(biāo)遞增的順序存入一個鏈表中，稱為 活化邊表 （ AEL, Active edge table)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。 只需對當(dāng)前掃描線的活動邊表作更新，即可得到下一條掃描線的活動邊表。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 ? 如何計(jì)算下一條掃描線與邊的交點(diǎn)？ 直線方程： 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 活化邊表中需要存放的信息： x：當(dāng)前掃描線與邊的交點(diǎn) dx＝ b/a：從當(dāng)前掃描線到下一條掃描線之間的 x增量 ymax：邊所交的最高掃描線 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 增加哪一條邊呢？ 為了方便邊的活化鏈表的更新，建立另一個表邊表，存放在該掃描線第一次出現(xiàn)的邊。 存放的信息： x：掃描線與該邊的初始交點(diǎn) dx： x的增量 ymax：該邊的最大 y值 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由 邊的分類表 ET（ Edge Table）和 活化邊表 AEL（ Active Edge List） 兩部分組成。 表結(jié)構(gòu) ET和 AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個域組成： 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)步驟 邊的分類表 ET是按邊的下端點(diǎn)的 y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的 y坐標(biāo)的值等于 i的邊歸入第 i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按 x值（ x值相等時，按 Δ x的值）遞增的順序排列成行。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 typedef struct {int ymax。 float x,deltax。 Edge *nextEdge。 }Edge。 算法實(shí)現(xiàn)步驟 這樣，當(dāng)建立了邊的分類表 ET后，掃描線算法可按下列步驟進(jìn)行： （ 1）取掃描線縱坐標(biāo) y的初始值為 ET中非空元素的最小序號。 （ 2）將邊的活化鏈表 AEL設(shè)置為空。 （ 3）按從下到上的順序?qū)v坐標(biāo)值為 y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表 ET和邊的活化鏈表都變成空為止。 1）如邊分類表 ET中的第 y類元素非空，則將屬于該類的所有邊從 ET中取出并插入邊的活化鏈表中， AEL中的各邊按照 x值（當(dāng) x值相等時，按 Δ x值）遞增方向排序。 2）若相對于當(dāng)前掃描線，邊的活化鏈表 AEL非空，則將AEL中的邊兩兩依次配對，即 1， 2邊為一對， 3， 4邊為一對，依次類推。每一對邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。 3）將邊的活化鏈表 AEL中滿足 y=ymax的邊刪去。 4）將邊的活化鏈表 AEL剩下的每一條邊的 x域累加 Δ x，即 x:=x+Δ x。 5）將當(dāng)前的掃描線的縱坐標(biāo)值 y累加 1，即 y:=y+1。 算法實(shí)現(xiàn)步驟 掃描線算法 ?特點(diǎn)：算法效率比逐點(diǎn)填充法高很多。 ?缺點(diǎn)：對各種表的維持和排序開銷太大，適合軟件實(shí)現(xiàn)而不適合硬件實(shí)現(xiàn)。 問題：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1