第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充-文庫吧
2025-07-17 13:31 本頁面
【正文】 掃描線的連貫性 掃描線的連貫性 1）設(shè) L是偶數(shù)。 2）在該掃描線上，只有區(qū)段(xeik,xeik+1） ,k=1,3,5,… ,L1位于多邊形 P內(nèi)，其余區(qū)段都在 P外。 以上性質(zhì)稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。 設(shè) d為一整數(shù)，并且 d=e1,并且 yi0≥d≥y in。 設(shè)位于掃描線 y=d上的交點序列為 xdj1,xdj2,xdj3,… ,xdjk 現(xiàn)在來討論掃描線 d， e交點序列之間的關(guān)系。若多邊形 P的邊 Pr1Pr與掃描線 y=e,y=d都相交，則交點序列中對應(yīng)元素 xer,xdr滿足下列關(guān)系： xer= xdr + 1/mr (1) 其中 mr為邊 Pr1Pr的斜率。 邊的連貫性 y=e y=d 邊的連貫性 于是，可利用 d的交點序列計算 e的交點序列，即先運用遞推關(guān)系式 (1)求得與掃描線 y=e和 y=d都相交的所有多邊形上的交點 xer,再求得與掃描線 y=d不相交但與掃描線 y=e相交的所有邊PqPq+1上的交點 xeq。如果 P的頂點的坐標(biāo)是整數(shù)，那么 xeq=xq或 xeq=xq+1,然后把這兩部分按遞增的順序排列，即可得 e的交點序列。 y=e y=d 邊的連貫性 特別是當(dāng)存在某一個整數(shù) k,0≤k≤n 1,使得 yike, dyik+1 成立時，則由區(qū)域的連貫性可知 d的交點序列和 e的交點序列之間有以下關(guān)系： 1）兩序列元素的個數(shù)相等，如上圖所示。 2）點 (xeir,e)與 (xdjr,d)位于多邊形 P的同一邊上，于是 xeir= xdjr + 1/kjr (2) 這樣，運用遞推關(guān)系式 (2)可直接由 d的交點序列和 e的獲得 e的交點序列。 以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在相鄰兩掃描線上的反映。 ?當(dāng)掃描線與多邊形 P的交點是 P的頂點時，則稱該交點為奇點。 ?以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實：每一條掃描線與多邊形 P的邊界的交點個數(shù)都是偶數(shù)。但是如果把每一奇點簡單地計為一個交點或者簡單地計為兩個交點，都可能出現(xiàn)奇數(shù)個交點。那么如果保證交點數(shù)為偶數(shù)呢？ 奇點的處理 奇點的處理 ? 若奇點做一個交點處理，則情況 A，交點個數(shù)不是偶數(shù)。 ? 若奇點做兩個交點處理，則情況 B，交點個數(shù)不是偶數(shù)。 奇點的處理 ? 多邊形 P的頂點可分為兩類：極值奇點和非極值奇點。如果 (yi1 yi)(yi+1 yi)≥0 ，則稱頂點 Pi為極值點；否則稱 Pi為非極值點。 ? 規(guī)定：奇點是非極值點時，該點按兩個交點計算，否則按一個交點計算。 數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟 算法基本思想：首先取 d=yin。 容易求得掃描線 y=d上的交點序列為xdj1,xdj2,… xdjn ， 這一序列由位于掃描線y=d上的多邊形 P的頂點組成。 由 yin的交點序列 開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形 P內(nèi)的區(qū)段，并表示成點陣形式。 數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟 所有的邊和掃描線求交，效率很低。因為一條掃描線往往只和少數(shù)幾條邊相交。 如何判斷多邊形的一條邊與掃描線是否相交？ 與當(dāng)前掃描線相交的邊稱為活性邊（ active edge)，把它們按與掃描線交點 x坐標(biāo)遞增的順序存入一個鏈表中，邊的活化鏈表 （ AEL, Active edge table)。它記錄了多邊形邊沿掃描線的交點序列。 只需對當(dāng)前掃描線的活動邊表作更新，即可得到下一條掃描線的活動邊表。 數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟 ? 如何計算下一條掃描線與邊的交點。 直線方程： ax+by+c = 0 當(dāng)前交點坐標(biāo)： (xi, yi) 下一交點坐標(biāo)： (xi+1,yi+1) xi+1= ((byi+1)c)/a = ((byi+1)c)/a =xib/a=xi+1/mi 活
物理相關(guān)推薦
鄂ICP備17016276號-1