多邊形的轉(zhuǎn)換ppt課件-在線瀏覽
2025-06-15 23:54本頁面
【正文】 邊形 P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于 P的內(nèi)外關(guān)系 。 若掃描線 y=e與多邊形 P的Pi1Pi相交，則記其交點(diǎn)的橫坐標(biāo)為 xei。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)： 掃描線的連貫性 掃描線的連貫性 1）設(shè) L是偶數(shù)。 以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。 設(shè)位于掃描線 y=d上的交點(diǎn)序列為 xdj1,xdj2,xdj3,… ,xdjk 現(xiàn)在來討論掃描線 d， e交點(diǎn)序列之間的關(guān)系。 邊的連貫性 y=e y=d 邊的連貫性 于是，可利用 d的交點(diǎn)序列計(jì)算 e的交點(diǎn)序列，即先運(yùn)用遞推關(guān)系式 (1)求得與掃描線 y=e和 y=d都相交的所有多邊形上的交點(diǎn) xer,再求得與掃描線 y=d不相交但與掃描線 y=e相交的所有邊PqPq+1上的交點(diǎn) xeq。 y=e y=d 邊的連貫性 特別是當(dāng)存在某一個(gè)整數(shù) k,0≤k≤n 1,使得 yike, dyik+1 成立時(shí)，則由區(qū)域的連貫性可知 d的交點(diǎn)序列和 e的交點(diǎn)序列之間有以下關(guān)系： 1）兩序列元素的個(gè)數(shù)相等，如上圖所示。 以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。 ?以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實(shí)：每一條掃描線與多邊形 P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)。那么如果保證交點(diǎn)數(shù)為偶數(shù)呢？ 奇點(diǎn)的處理 奇點(diǎn)的處理 ? 若奇點(diǎn)做一個(gè)交點(diǎn)處理，則情況 A，交點(diǎn)個(gè)數(shù)不是偶數(shù)。 奇點(diǎn)的處理 ? 多邊形 P的頂點(diǎn)可分為兩類：極值奇點(diǎn)和非極值奇點(diǎn)。 ? 規(guī)定：奇點(diǎn)是非極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。 容易求得掃描線 y=d上的交點(diǎn)序列為xdj1,xdj2,… xdjn ， 這一序列由位于掃描線y=d上的多邊形 P的頂點(diǎn)組成。 數(shù)據(jù)結(jié)構(gòu)與實(shí)現(xiàn)步驟 所有的邊和掃描線求交，效率很低。 如何判斷多邊形的一條邊與掃描線是否相交？ 與當(dāng)前掃描線相交的邊稱為活性邊（ active edge)，把它們按與掃描線交點(diǎn) x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表 （ AEL, Active edge table)。 只需對(duì)當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。 直線方程： 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)的邊。它由邊的分類表 ET（ Edge Table）和邊的活化鏈表 AEL（ Active Edge List） 兩部分組成。邊的結(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 指向下一條邊的指針。下端點(diǎn)的 y坐標(biāo)的值等于 i的邊歸入第 i類。同一類中，各邊按 x值（ x值相等時(shí)，按 Δ x的值）遞增的順序排列成行。 （ 2）將邊的活化鏈表 AEL設(shè)置為空。 算法實(shí)現(xiàn)步驟 1）如邊分類表 ET中的第 y類元素非空，則將屬于該類的所有邊從 ET中取出并插入邊的活化鏈表中， AEL中的各邊按照 x值（當(dāng) x值相等時(shí)，按 Δ x值）遞增方向排序。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。 4）將邊的活化鏈表 AEL剩下的每一條邊的 x域累加 Δ x，即 x:=x+Δ x。 掃描線算法 ? 特點(diǎn)：算法效率較
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1