掃描線多邊形填充算法

1、關(guān)于掃描線多邊形填充算法第一張，PPT共三十頁(yè)，創(chuàng)作于2022年6月1區(qū)域內(nèi)部點(diǎn)判斷準(zhǔn)則 區(qū)域填充首先判斷一個(gè)像素點(diǎn)是否處于多邊形區(qū)域內(nèi),其判斷準(zhǔn)則如下： 從該點(diǎn)向無(wú)窮遠(yuǎn)處引出一條射線（也稱掃描線），若射線與區(qū)域邊界交點(diǎn)目標(biāo)數(shù)目為奇數(shù)，則此點(diǎn)在區(qū)域內(nèi)。若射線與區(qū)域邊界交點(diǎn)目標(biāo)數(shù)目為偶數(shù)，則此點(diǎn)為區(qū)域外點(diǎn)。例如：A點(diǎn)向右引射線與區(qū)域邊界共3個(gè)交點(diǎn)，為內(nèi)點(diǎn)B點(diǎn)向右引射線與區(qū)域邊界共2個(gè)交點(diǎn)，為外點(diǎn)AB第二張，PPT共三十頁(yè)，創(chuàng)作于2022年6月此時(shí)應(yīng)注意兩點(diǎn)：（1）當(dāng)掃描線與多邊形相交如下情況時(shí):YXAIBEDCF若兩相鄰邊與掃描線相交于同一點(diǎn)，且兩邊位于掃描線同側(cè)，則視為兩個(gè)交點(diǎn)。如yb：1點(diǎn)向

2、右交點(diǎn)為3個(gè)（奇數(shù)）是內(nèi)點(diǎn) 3點(diǎn)向右交點(diǎn)為4個(gè)（偶數(shù)）是外點(diǎn)若兩相鄰邊與掃描線相交于同一點(diǎn)，且兩邊位于掃描線異側(cè)，則視為一個(gè)交點(diǎn)。如yayb31ya第三張，PPT共三十頁(yè)，創(chuàng)作于2022年6月（2）當(dāng)掃描線重合多邊形某條邊界水平線時(shí)，如該水平邊線前后兩條邊線是一上一下的，則該水平邊線兩個(gè)端點(diǎn)作為一個(gè)交點(diǎn)，即掃描線與該水平邊界線相交了一次。 如下圖yCBXYDCBAE如該水平邊線前后兩條邊線是同為上或同為下的，則將該水平邊線兩個(gè)端點(diǎn)作為交點(diǎn)，即掃描線與該水平邊界線相交了兩次。如yDEyCByDE第四張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 2邊相關(guān)性及邊記錄 很顯然，不能利用區(qū)域內(nèi)部點(diǎn)判別準(zhǔn)則對(duì)

3、顯示平面上每個(gè)點(diǎn)逐個(gè)判別，這樣計(jì)算量太大。 事實(shí)上，相對(duì)于一個(gè)給定多邊形區(qū)域來(lái)說(shuō)，顯示平面上每個(gè)像素點(diǎn)內(nèi)外特性是互相關(guān)聯(lián)的。相鄰像素間具有相關(guān)屬性。在實(shí)施多邊形填充時(shí)，利用掃描線相關(guān)性，就無(wú)需對(duì)掃描線上所有像素點(diǎn)逐個(gè)地進(jìn)行內(nèi)外特性判斷，只需對(duì)一條掃描線從左到右求出該掃描線與區(qū)域邊界交點(diǎn)，這些交點(diǎn)必將掃描線分成內(nèi)外交替線段，這些交點(diǎn)x值大小依次排列。 第五張，PPT共三十頁(yè)，創(chuàng)作于2022年6月XYABCD如上圖，按x從小到大排列為A B C D交點(diǎn)AB間線段上像素點(diǎn)必在區(qū)域內(nèi)。所以關(guān)鍵是求交點(diǎn)。第六張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 （1）交點(diǎn)計(jì)算 多邊形填充首先需要求出掃描線與邊界的交

4、點(diǎn)，利用邊的相關(guān)性可以簡(jiǎn)單有效地解決這個(gè)問(wèn)題。當(dāng)一條掃描線yi 與多邊形的某一邊線有交點(diǎn)時(shí)，其相鄰掃描線yi+1一般也與該邊線相交（除非yi+1超出了該邊線所在區(qū)間），而且掃描線yi+1與該邊線的交點(diǎn)，很容易從前一條掃描線yi與該邊的交點(diǎn)遞推求得。 設(shè)某條直線邊的方程為 y=mx+b 該邊兩個(gè)端點(diǎn)坐標(biāo)為（x1,y1)、（x2,y2) 且x1x2 則該邊斜率為m=(y2-y1)/(x2-x1) 令掃描線yi與該邊交點(diǎn)為（xi，yi） 掃描線yi1與該邊交點(diǎn)（xi1，yi1）第七張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 A(8,2)C(8,8)B(3,7)yi(xi,yi)邊線AB第yi條掃描線與

5、某邊線AB的交點(diǎn)是(xi,yi) 第yi+1條掃描線與AB的交點(diǎn)為（xi+1, yi+1 ）則第yi+1條掃描線與AB的交點(diǎn)為yi+1=yi+1, xi+1=xi+1/m 即由前一條掃描線交點(diǎn)Xi，Yi求下一條掃描線交點(diǎn)Xi1，Yi+1,式中，m是這條邊的斜率。（xi+1, yi+1)邊線AC1/myi+1第八張，PPT共三十頁(yè)，創(chuàng)作于2022年6月（2）邊記錄利用邊的這種相關(guān)性，不必算出邊線與各條掃描線的全部交點(diǎn)，只需以邊線為單位，對(duì)每條邊建立一個(gè)邊記錄，其內(nèi)容包括：該邊y的最大值ymax ,該邊底端的x坐標(biāo)xi,從一條掃描線到下一條掃描線間的x增量1/m,以及指示下一個(gè)邊記錄地址的指針 7

6、 8 18 8 0ABACymax xi 1/m ymax xi 1/m A(8,2)C(8,8)B(3,7)第九張，PPT共三十頁(yè)，創(chuàng)作于2022年6月3邊表ET和活動(dòng)邊表AET （1）邊表ET （Edge Table)邊表是一個(gè)包含多邊形全部邊記錄的表，它按y坐標(biāo)（與掃描線一一對(duì)應(yīng)）遞增（或遞減）的順序存放區(qū)域邊界的所有邊。每個(gè)y坐標(biāo)值存放一個(gè)或者說(shuō)幾個(gè)邊記錄。當(dāng)某條掃描線yi碰到多邊形邊界的新邊時(shí)（以邊線底端為準(zhǔn)），則在ET表中相應(yīng)的y坐標(biāo)值處寫入一個(gè)邊記錄。當(dāng)同時(shí)有多條邊進(jìn)入時(shí)，則在ET表中按鏈表結(jié)構(gòu)寫入相應(yīng)數(shù)目的多個(gè)記錄，這些記錄是按邊線較低端點(diǎn)的x值增加的順序排列。當(dāng)沒(méi)有新邊加入時(shí)

7、，表中對(duì)應(yīng)的y坐標(biāo)值處存儲(chǔ)內(nèi)容為空白。ymax xi 1/m 第十張，PPT共三十頁(yè)，創(chuàng)作于2022年6月注意：在ET表中：與x軸平行的邊不計(jì)入。多邊形的頂點(diǎn)分為兩大類：一類是局部極值點(diǎn)，如下圖中的P1、P3；另一類是非極值點(diǎn)，如下圖中的P2、P4、P5。當(dāng)掃描線與第一類頂點(diǎn)相遇時(shí)，應(yīng)看作兩個(gè)點(diǎn)；當(dāng)掃描線與第二類頂點(diǎn)相遇時(shí)，應(yīng)視為一個(gè)點(diǎn)。 多邊形邊表多邊形邊表邊表ymax xi 1/m 第十一張，PPT共三十頁(yè)，創(chuàng)作于2022年6月活動(dòng)邊表AET(Activities Edge Table) 活動(dòng)邊表AET是一個(gè)只與當(dāng)前掃描線相交的邊記錄鏈表。隨著掃描線從一條到另一條的轉(zhuǎn)換，AET表也應(yīng)隨之變

8、動(dòng)，利用 yi+1=yi+1, xi+1=xi+1/m 可以算出AET表中x域中的新值xi。凡是與這一條掃描線相交的任何新邊都加到AET表中，而與之不相交的邊又被從AET表中刪除掉了。下圖列出了多邊形圖在掃描線為4、5、6時(shí)的AET表。AET表中的記錄順序仍是按x增大排序的。 第十二張，PPT共三十頁(yè)，創(chuàng)作于2022年6月4多邊形區(qū)域填充算法過(guò)程 （1）根據(jù)給出的頂點(diǎn)坐標(biāo)數(shù)據(jù)，按y遞增順序建立ET表（2）根據(jù)AET指針，使之為空。（3）使y=Ymin （Ymin為頂點(diǎn)坐標(biāo)中最小y值）。（4）反復(fù)做下述各步，直至y=Ymax（頂點(diǎn)坐標(biāo)中y的最大值）或ET與AET為空： 將ET表加入到AET中，并

9、保持AET鏈中的記錄按x值 增大排序。 對(duì)掃描線yi依次成對(duì)取出AET中xi值，并在每對(duì)xi 之間填上所要求的顏色或圖案。 從AET表中刪去yi=ymax的記錄。 對(duì)保留下來(lái)的AET中的每個(gè)記錄，用xi+1/m代替xi ，并重新按x遞增排序。 使yi+1，以便進(jìn)入下一輪循環(huán)。第十三張，PPT共三十頁(yè)，創(chuàng)作于2022年6月開(kāi)始y1，將ET表中y1結(jié)點(diǎn)加入至AET表，同時(shí)保持AET鏈中記錄按x增大排序3 6 -25 6 0.5 AET由于上例中是66，是頂點(diǎn)，所以中間不填像素顏色。上例由于Ymax3和5，所以不必刪去，當(dāng)yi3時(shí)，此時(shí)就得將第一個(gè)結(jié)點(diǎn)即（3，6，2）刪去。對(duì)保留下來(lái)的AET中的每個(gè)

10、記錄，用xi+1/m代替xi，并重新按x遞增排序。如上例變成(實(shí)際求出y=2時(shí)新的交點(diǎn)x坐標(biāo)）：3 4 -2 5 6.5 0.5 AET第十四張，PPT共三十頁(yè)，創(chuàng)作于2022年6月使yi+1，以便進(jìn)入下一輪循環(huán)。即y2再進(jìn)入以上循環(huán)繼續(xù)：由y2，ET表中是空，所以不需ET表加入AET表 取x4和x6.5,將46.5之間填上像素顏色。 由于y=2,不必刪去結(jié)點(diǎn)。 再改變xi的值為 使yi 3，重復(fù)繼續(xù)。繼續(xù)：由y3，將ET表中y3結(jié)點(diǎn)加入，即 將27之間填上像素顏色。 刪去結(jié)點(diǎn)Ymax3 結(jié)點(diǎn)。3 2 -2 5 7 0.5 AET3 2 -25 7 0.5 AET6 2 06 2 05 7 0

11、.5 AET3 4 -2 5 6.5 0.5 AET第十五張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 再改變xi的值為 使yi 4，重復(fù)繼續(xù)。 6 2 05 7.5 0.5 AET第十六張，PPT共三十頁(yè)，創(chuàng)作于2022年6月P0P1P2P3P4P5舉例演示第十七張，PPT共三十頁(yè)，創(chuàng)作于2022年6月二、 邊填充 邊填充算法的基本原理是：（1）對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，即對(duì)多邊形邊界經(jīng)過(guò)的像素打上邊標(biāo)志；（2）對(duì)多邊形內(nèi)部進(jìn)行填充。填充時(shí)，對(duì)每條掃描線，依從左到右的順序，逐個(gè)訪問(wèn)掃描線上的像素，用一個(gè)布爾量來(lái)標(biāo)志當(dāng)前點(diǎn)是在多邊形內(nèi)部還是外部（一開(kāi)始設(shè)布爾量的值為假，當(dāng)碰到設(shè)有邊標(biāo)志的點(diǎn)

12、時(shí)，就把其值取反；對(duì)沒(méi)有邊標(biāo)志的點(diǎn)，則其值保持不變）（3）將其布爾量值為“真”的內(nèi)部置為圖形色，把其布爾量的值為“假”的外部點(diǎn)置為底色即可。 第十八張，PPT共三十頁(yè)，創(chuàng)作于2022年6月三、 種子填充 1、種子填充基本思路 首先假設(shè)在多邊形區(qū)域的內(nèi)部，至少有一個(gè)像素點(diǎn)（稱為種子）是已知的，然后算法開(kāi)始搜索與種子點(diǎn)相鄰且位于區(qū)域內(nèi)的其它像素。如果相鄰點(diǎn)不在區(qū)域內(nèi)，那么到達(dá)區(qū)域的邊界；如果相鄰點(diǎn)位于區(qū)域內(nèi)，那么這一點(diǎn)就成為新的種子點(diǎn)，然后繼續(xù)遞歸地搜索下去。 區(qū)域的連通情況可以分為四連通和八連通兩種四連通區(qū)域：各像素在水平和垂直四個(gè)方向上是連通的.八連通區(qū)域：各像素在水平、垂直以及四個(gè)對(duì)角線方向

13、上都是連通的。 第十九張，PPT共三十頁(yè)，創(chuàng)作于2022年6月 在種子填充算法中，如果允許從四個(gè)方向搜尋下一個(gè)像素點(diǎn)，則該算法稱為四向算法；如果允許從八個(gè)方法搜尋下一個(gè)像素點(diǎn)，則該算法稱為八向算法。 一個(gè)八向算法可以用在四連通區(qū)域的填充上，也可用在八連通區(qū)域的填充上；而一個(gè)四向算法只能用于填充四連通區(qū)域。 無(wú)論是四向算法還是八向算法，它們的填充算法基本思想是相同的。為簡(jiǎn)單起見(jiàn)，下面只討論四向種子填充算法。 第二十張，PPT共三十頁(yè)，創(chuàng)作于2022年6月2. 種子填充算法基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個(gè)像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對(duì)其進(jìn)行填充。由

14、于區(qū)域可采用邊界定義和內(nèi)點(diǎn)定義兩種方式，區(qū)域按連通性又可分為四連通區(qū)域和八連通區(qū)域兩類，所以常用的種子填充算法有：邊界表示的四連通區(qū)域種子填充算法內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法邊界表示的八連通區(qū)域種子填充算法內(nèi)點(diǎn)表示的八連通區(qū)域種子填充算法第二十一張，PPT共三十頁(yè)，創(chuàng)作于2022年6月(1)邊界表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒(méi)有被填充過(guò)，對(duì)其填充，并重復(fù)上述過(guò)程，直到所有像素填充完畢?？梢允褂脳＝Y(jié)構(gòu)來(lái)實(shí)現(xiàn)該算法，算法的執(zhí)行步驟如下：種子像素入棧，當(dāng)棧非空時(shí)，重復(fù)執(zhí)行如下三步操作： 1）棧頂像素出棧；

15、2）將出棧像素置成多邊形填充的顏色； 3）按左、上、右、下的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成多邊形色，則把該像素入棧。第二十二張，PPT共三十頁(yè)，創(chuàng)作于2022年6月邊界填充算法（四連通域） 在區(qū)域有一個(gè)像素是已知（種子像素），由此像素從四個(gè)方向遍歷區(qū)域內(nèi)所有像素。（適用于交互繪圖）0 1 2 3 4 54321用什么方法實(shí)現(xiàn)？注意：棧中種子的次序，當(dāng)前棧頂元素是哪個(gè)？依“左上右下”第二十三張，PPT共三十頁(yè)，創(chuàng)作于2022年6月以邊界表示的四連通區(qū)域種子填充算法 (基于遞歸)取(x,y)為種子點(diǎn)Void BoundaryFill4(int x,int y ,

16、int boundarycolor,int newcolor) if(getpixel(x,y)!= boundarycolor & getpixel(x,y)!= newcolor) /* getpixel(x,y)取屏幕上像素(x,y)的顏色*/ putpixel(x,y,newcolor);/著色 BoundaryFill4(x-1,y, boundarycolor, newcolor); BoundaryFill4(x,y+1, boundarycolor, newcolor); BoundaryFill4(x+1,y, boundarycolor, newcolor); Bounda

17、ryFill4(x,y-1, boundarycolor, newcolor); 基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒(méi)有被填充過(guò)，對(duì)其填充，并重復(fù)上述過(guò)程，直到所有像素填充完畢。第二十四張，PPT共三十頁(yè)，創(chuàng)作于2022年6月例：填充如下區(qū)域：堆棧的變化如圖所示。邊界表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒(méi)有被填充過(guò)，對(duì)其填充，并重復(fù)上述過(guò)程，直到所有像素填充完畢?？梢允褂脳＝Y(jié)構(gòu)來(lái)實(shí)現(xiàn)該算法，算法的執(zhí)行步驟如下：種子像素入棧，當(dāng)棧非空時(shí)，重復(fù)執(zhí)行如下三步操

18、作： 1）棧頂像素出棧； 2）將出棧像素置成多邊形填充的顏色； 3）按左、上、右、下的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成多邊形色，則把該像素入棧。第二十五張，PPT共三十頁(yè)，創(chuàng)作于2022年6月(2)內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，如果是區(qū)域內(nèi)的像素，則對(duì)其填充，并重復(fù)上述過(guò)程，直到所有像素填充完畢。它也常稱為漫水法。可以使用棧結(jié)構(gòu)來(lái)實(shí)現(xiàn)該算法，算法的執(zhí)行步驟如下：種子像素入棧，當(dāng)棧非空時(shí)，重復(fù)執(zhí)行如下三步操作： 1）棧頂像素出棧； 2）將出棧像素置成多邊形填充的顏色； 3）按左、上、右、

19、下的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素是區(qū)域內(nèi)的像素，則把該像素入棧。第二十六張，PPT共三十頁(yè)，創(chuàng)作于2022年6月Void FloodFill4(int x,int y ,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /* getpixel(x,y)取屏幕上像素(x,y)的顏色, oldcolor為區(qū)域的原色*/ putpixel(x,y,newcolor);/著色 FloodFill4(x-1,y, oldcolor, newcolor); FloodFill4(x,y+1, oldcolor, newcolor

20、); FloodFill4(x+1,y, oldcolor, newcolor); FloodFill4(x,y-1, oldcolor, newcolor); 內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法(基于遞歸)取(x,y)為種子點(diǎn)基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，如果是區(qū)域內(nèi)的像素，則對(duì)其填充，并重復(fù)上述過(guò)程，直到所有像素填充完畢第二十七張，PPT共三十頁(yè)，創(chuàng)作于2022年6月特點(diǎn)：(1) 有些像素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2) 遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一像素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。 改進(jìn)算法，減少遞歸次數(shù)，提高效率。 方法之一使用掃描線填充算法；種子填充法第二十八張，PPT共三十頁(yè)，創(chuàng)作于2022年6月上述簡(jiǎn)單種子填充算法操作過(guò)程非常簡(jiǎn)