光柵圖形的轉(zhuǎn)換與區(qū)域填充-在線瀏覽
2025-07-16 16:41本頁面
【正文】 究的重要內(nèi)容。 掃描線算法 設多邊形 P的頂點 Pi=(xi,yi),i=0,1, … ,n，又設yi0,yi1,… yin是各頂點 Pi的坐標 yi的遞減數(shù)列，即yik≥y ik+1,0≤k≤n ，當 yik≥y ik+1,0≤k≤n 1時，屏幕上位于 y=yik和 y=yik+1兩條掃描線之間的長方形區(qū)域 被多邊形 P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質(zhì)： 區(qū)域的連貫性 1）梯形的兩底邊分別在 y=yik和 y=yik+1兩條掃描線上，腰在多邊形 P的邊上或在顯示屏幕的邊界上。 3）兩類梯形在長方形區(qū)域 {yik,yik+1}內(nèi)相間的排列，即相鄰的兩梯形必有一個在多邊形 P內(nèi)，另一個在 P外。 區(qū)域的連貫性 設 e為一整數(shù)， yi0≥e≥y in。 現(xiàn)設 xei1,xei2,xei3,… ,xeil 是該掃描線與 P的邊界各交點橫坐標的遞增序列，稱此序列為 交點序列 。 2）在該掃描線上，只有區(qū)段（ xeik,xeik+1） ,k=1,3,5,… ,l1位于多邊形 P內(nèi)，其余區(qū)段都在 P外。 掃描線的連貫性 設 d為一整數(shù)，并且 d=e1,并且 yi0≥d≥y in。若多邊形 P的邊 Pr1Pr與掃描線 y=e,y=d都相交，則交點序列中對應元素 xer,xdr滿足下列關(guān)系： xer= xdr + 1/mr (1) 其中 mr為邊 Pr1Pr的斜率。如果 P的頂點的坐標是整數(shù)，那么 xeq=xq或 xeq=xq+1,然后把這兩部分按遞增的順序排列，即可得 e的交點序列。 2）點 (xeir,e)與 (xdjr,d)位于多邊形 P的同一邊上，于是 xeir= xdjr + 1/kjr (2) 這樣，運用遞推關(guān)系式 (2)可直接由 d的交點序列獲得 e的交點序列。 邊的連貫性 ?當掃描線與多邊形 P的交點是 P的頂點時，則稱該交點為奇點。但是如果把每一奇點簡單地計為一個交點或者簡單地計為兩個交點，都可能出現(xiàn)奇數(shù)個交點。 ? 若奇點做兩個交點處理，則情況 B，交點個數(shù)不是偶數(shù)。如果 (yi1 yi)(yi+1 yi)≥0 ，則稱頂點 Pi為極值點；否則稱 Pi為非極值點。 ? 奇點的預處理： 奇點的處理 數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟 算法基本思想：首先取 d=yin。 由 yin的交點序列 開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形 P內(nèi)的區(qū)段，并表示成點陣形式。因為一條掃描線往往只和少數(shù)幾條邊相交。它記錄了多邊形邊沿掃描線的交點序列。 數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟 ? 如何計算下一條掃描線與邊的交點？ 直線方程： ax+by+c = 0 當前交點坐標： (xi, yi) 下一交點坐標： (xi+1,yi+1) xi+1= ((byi+1)c)/a = ((byi+1)c)/a =xib/a 活化邊表中需要存放的信息： x：當前掃描線與邊的交點 dx＝ b/a：從當前掃描線到下一條掃描線之間的 x增量 ymax：邊所交的最高掃描線 數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)步驟 增加哪一條邊呢？ 為了方便邊的活化鏈表的更新，建立另一個表邊表，存放在該掃描線第一次出現(xiàn)的邊。它由 邊的分類表 ET（ Edge Table）和 活化邊表 AEL（ Active Edge List） 兩部分組成。邊的結(jié)構(gòu)由以下四個域組成： ymax 邊的上端點的 y坐標； x 在 ET中表示邊的下端點的 x坐標，在AEL中則表示邊與掃描線的交點的坐標； Δ x 邊的斜率的倒數(shù)； next 指向下一條邊的指針。下端點的 y坐標的值等于 i的邊歸入第 i類。同一類中，各邊按 x值（ x值相等時，按 Δ x的值）遞增的順序排列成行。 float x,deltax。 }Edge。 （ 2）將邊的活化鏈表 AEL設置為空。 1）如邊分類表 ET中的第 y類元素非空，則將屬于該類的所有邊從 ET中取出并插入邊的活化鏈表中， AEL中的各邊按照 x值（當 x值相等時，按 Δ x值）遞增方向排序。每一對邊與當前掃描線的交點所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點（象素）按多邊形屬性著色。 4）將邊的活化鏈表 AEL剩下的每一條邊的 x域累加 Δ x，即 x:=x+Δ x。 算法實現(xiàn)步驟 掃描線算法 ?特點：算法效率比逐點填充法高很多。 問題： ?如何修改掃描線算法，使它能處理邊自交的多邊形？ 掃描線算法 邊緣填充算法 ? 求余運算 ：假定 A為一個正整數(shù)，則
教學課件相關(guān)推薦
鄂ICP備17016276號-1