掃描線多邊形填充算法

關(guān)于掃描線多邊形填充算法第1頁(yè)，共30頁(yè)，2023年，2月20日，星期四1．區(qū)域內(nèi)部點(diǎn)判斷準(zhǔn)則

區(qū)域填充首先判斷一個(gè)像素點(diǎn)是否處于多邊形區(qū)域內(nèi),其判斷準(zhǔn)則如下：從該點(diǎn)向無窮遠(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第2頁(yè)，共30頁(yè)，2023年，2月20日，星期四此時(shí)應(yīng)注意兩點(diǎn)：（1）當(dāng)掃描線與多邊形相交如下情況時(shí):YXAIBEDCF①若兩相鄰邊與掃描線相交于同一點(diǎn)，且兩邊位于掃描線同側(cè)，則視為兩個(gè)交點(diǎn)。如yb：1點(diǎn)向右交點(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第3頁(yè)，共30頁(yè)，2023年，2月20日，星期四（2）當(dāng)掃描線重合多邊形某條邊界水平線時(shí)，如該水平邊線前后兩條邊線是一上一下的，則該水平邊線兩個(gè)端點(diǎn)作為一個(gè)交點(diǎn)，即掃描線與該水平邊界線相交了一次。如下圖yCBXYDCBAE如該水平邊線前后兩條邊線是同為上或同為下的，則將該水平邊線兩個(gè)端點(diǎn)作為交點(diǎn)，即掃描線與該水平邊界線相交了兩次。如yDEyCByDE第4頁(yè)，共30頁(yè)，2023年，2月20日，星期四

2．邊相關(guān)性及邊記錄

很顯然，不能利用區(qū)域內(nèi)部點(diǎn)判別準(zhǔn)則對(duì)顯示平面上每個(gè)點(diǎn)逐個(gè)判別，這樣計(jì)算量太大。事實(shí)上，相對(duì)于一個(gè)給定多邊形區(qū)域來說，顯示平面上每個(gè)像素點(diǎn)內(nèi)外特性是互相關(guān)聯(lián)的。相鄰像素間具有相關(guān)屬性。在實(shí)施多邊形填充時(shí)，利用掃描線相關(guān)性，就無需對(duì)掃描線上所有像素點(diǎn)逐個(gè)地進(jìn)行內(nèi)外特性判斷，只需對(duì)一條掃描線從左到右求出該掃描線與區(qū)域邊界交點(diǎn)，這些交點(diǎn)必將掃描線分成內(nèi)外交替線段，這些交點(diǎn)x值大小依次排列。

第5頁(yè)，共30頁(yè)，2023年，2月20日，星期四XYABCD如上圖，按x從小到大排列為ABCD交點(diǎn)AB間線段上像素點(diǎn)必在區(qū)域內(nèi)。所以關(guān)鍵是求交點(diǎn)。第6頁(yè)，共30頁(yè)，2023年，2月20日，星期四（1）交點(diǎn)計(jì)算

多邊形填充首先需要求出掃描線與邊界的交點(diǎn)，利用邊的相關(guān)性可以簡(jiǎn)單有效地解決這個(gè)問題。當(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)

且x1≠x2

則該邊斜率為m=(y2-y1)/(x2-x1)令掃描線yi與該邊交點(diǎn)為（xi，yi）

掃描線yi＋1與該邊交點(diǎn)（xi＋1，yi＋1）第7頁(yè)，共30頁(yè)，2023年，2月20日，星期四

A(8,2)C(8,8)B(3,7)yi(xi,yi)邊線AB第yi條掃描線與某邊線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)Xi＋1，Yi+1,式中，m是這條邊的斜率。（xi+1,yi+1)邊線AC1/myi+1第8頁(yè)，共30頁(yè)，2023年，2月20日，星期四（2）邊記錄利用邊的這種相關(guān)性，不必算出邊線與各條掃描線的全部交點(diǎn)，只需以邊線為單位，對(duì)每條邊建立一個(gè)邊記錄，其內(nèi)容包括：該邊y的最大值ymax,該邊底端的x坐標(biāo)xi,從一條掃描線到下一條掃描線間的x增量1/m,以及指示下一個(gè)邊記錄地址的指針

7

8

－18

8

0ABACymaxxi1/m

ymaxxi1/m

A(8,2)C(8,8)B(3,7)第9頁(yè)，共30頁(yè)，2023年，2月20日，星期四3．邊表ET和活動(dòng)邊表AET（1）邊表ET（Edge

Table)邊表是一個(gè)包含多邊形全部邊記錄的表，它按y坐標(biāo)（與掃描線一一對(duì)應(yīng)）遞增（或遞減）的順序存放區(qū)域邊界的所有邊。每個(gè)y坐標(biāo)值存放一個(gè)或者說幾個(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)沒有新邊加入時(shí)，表中對(duì)應(yīng)的y坐標(biāo)值處存儲(chǔ)內(nèi)容為空白。ymaxxi1/m第10頁(yè)，共30頁(yè)，2023年，2月20日，星期四注意：在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)。多邊形邊表多邊形邊表邊表ymaxxi1/m

第11頁(yè)，共30頁(yè)，2023年，2月20日，星期四⑵活動(dòng)邊表AET(ActivitiesEdge

Table)

活動(dòng)邊表AET是一個(gè)只與當(dāng)前掃描線相交的邊記錄鏈表。隨著掃描線從一條到另一條的轉(zhuǎn)換，AET表也應(yīng)隨之變動(dòng)，利用

yi+1=yi+1,xi+1=xi+1/m

可以算出AET表中x域中的新值xi。凡是與這一條掃描線相交的任何新邊都加到AET表中，而與之不相交的邊又被從AET表中刪除掉了。下圖列出了多邊形圖在掃描線為4、5、6時(shí)的AET表。AET表中的記錄順序仍是按x增大排序的。第12頁(yè)，共30頁(yè)，2023年，2月20日，星期四4．多邊形區(qū)域填充算法過程（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中，并保持AET鏈中的記錄按x值增大排序。②對(duì)掃描線yi依次成對(duì)取出AET中xi值，并在每對(duì)xi

之間填上所要求的顏色或圖案。③從AET表中刪去yi=ymax的記錄。④對(duì)保留下來的AET中的每個(gè)記錄，用xi+1/m代替xi

，并重新按x遞增排序。⑤使yi+1，以便進(jìn)入下一輪循環(huán)。第13頁(yè)，共30頁(yè)，2023年，2月20日，星期四①開始y＝1，將ET表中y＝1結(jié)點(diǎn)加入至AET表，同時(shí)保持AET鏈中記錄按x增大排序36

-2560.5^AET②由于上例中是6－6，是頂點(diǎn)，所以中間不填像素顏色。③上例由于Ymax＝3和5，所以不必刪去，當(dāng)yi＝3時(shí)，此時(shí)就得將第一個(gè)結(jié)點(diǎn)即（3，6，－2）刪去。④對(duì)保留下來的AET中的每個(gè)記錄，用xi+1/m代替xi，并重新按x遞增排序。如上例變成(實(shí)際求出y=2時(shí)新的交點(diǎn)x坐標(biāo)）：34

-256.50.5^AET第14頁(yè)，共30頁(yè)，2023年，2月20日，星期四⑤使yi+1，以便進(jìn)入下一輪循環(huán)。即y＝2再進(jìn)入以上循環(huán)繼續(xù)：①由y＝2，ET表中是空，所以不需ET表加入AET表②取x＝4和x＝6.5,將4－6.5之間填上像素顏色。③由于y=2,不必刪去結(jié)點(diǎn)。④再改變xi的值為

⑤使yi＝3，重復(fù)繼續(xù)。繼續(xù)：①由y＝3，將ET表中y＝3結(jié)點(diǎn)加入，即②將2－7之間填上像素顏色。③刪去結(jié)點(diǎn)Ymax＝3結(jié)點(diǎn)。32

-2

570.5^AET32

-2570.5^AET62

062

0570.5^AET34

-256.50.5^AET第15頁(yè)，共30頁(yè)，2023年，2月20日，星期四④再改變xi的值為⑤使yi＝4，重復(fù)繼續(xù)。

62

057.50.5^AET第16頁(yè)，共30頁(yè)，2023年，2月20日，星期四P0P1P2P3P4P5舉例演示第17頁(yè)，共30頁(yè)，2023年，2月20日，星期四二、邊填充邊填充算法的基本原理是：（1）對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，即對(duì)多邊形邊界經(jīng)過的像素打上邊標(biāo)志；（2）對(duì)多邊形內(nèi)部進(jìn)行填充。填充時(shí)，對(duì)每條掃描線，依從左到右的順序，逐個(gè)訪問掃描線上的像素，用一個(gè)布爾量來標(biāo)志當(dāng)前點(diǎn)是在多邊形內(nèi)部還是外部（一開始設(shè)布爾量的值為假，當(dāng)碰到設(shè)有邊標(biāo)志的點(diǎn)時(shí)，就把其值取反；對(duì)沒有邊標(biāo)志的點(diǎn)，則其值保持不變）（3）將其布爾量值為“真”的內(nèi)部置為圖形色，把其布爾量的值為“假”的外部點(diǎn)置為底色即可。第18頁(yè)，共30頁(yè)，2023年，2月20日，星期四三、種子填充

1、種子填充基本思路首先假設(shè)在多邊形區(qū)域的內(nèi)部，至少有一個(gè)像素點(diǎn)（稱為種子）是已知的，然后算法開始搜索與種子點(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ì)角線方向上都是連通的。第19頁(yè)，共30頁(yè)，2023年，2月20日，星期四在種子填充算法中，如果允許從四個(gè)方向搜尋下一個(gè)像素點(diǎn)，則該算法稱為四向算法；如果允許從八個(gè)方法搜尋下一個(gè)像素點(diǎn)，則該算法稱為八向算法。一個(gè)八向算法可以用在四連通區(qū)域的填充上，也可用在八連通區(qū)域的填充上；而一個(gè)四向算法只能用于填充四連通區(qū)域。無論是四向算法還是八向算法，它們的填充算法基本思想是相同的。為簡(jiǎn)單起見，下面只討論四向種子填充算法。

第20頁(yè)，共30頁(yè)，2023年，2月20日，星期四2.種子填充算法

基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個(gè)像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對(duì)其進(jìn)行填充。 由于區(qū)域可采用邊界定義和內(nèi)點(diǎn)定義兩種方式，區(qū)域按連通性又可分為四連通區(qū)域和八連通區(qū)域兩類，所以常用的種子填充算法有：邊界表示的四連通區(qū)域種子填充算法內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法邊界表示的八連通區(qū)域種子填充算法內(nèi)點(diǎn)表示的八連通區(qū)域種子填充算法第21頁(yè)，共30頁(yè)，2023年，2月20日，星期四(1)邊界表示的四連通區(qū)域種子填充算法 基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒有被填充過，對(duì)其填充，并重復(fù)上述過程，直到所有像素填充完畢。 可以使用棧結(jié)構(gòu)來實(shí)現(xiàn)該算法，算法的執(zhí)行步驟如下： 種子像素入棧，當(dāng)棧非空時(shí)，重復(fù)執(zhí)行如下三步操作：

1）棧頂像素出棧；

2）將出棧像素置成多邊形填充的顏色；

3）按左、上、右、下的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成多邊形色，則把該像素入棧。第22頁(yè)，共30頁(yè)，2023年，2月20日，星期四邊界填充算法（四連通域）在區(qū)域有一個(gè)像素是已知（種子像素），由此像素從四個(gè)方向遍歷區(qū)域內(nèi)所有像素。（適用于交互繪圖）0123454321用什么方法實(shí)現(xiàn)？注意：棧中種子的次序，當(dāng)前棧頂元素是哪個(gè)？依“左上右下”第23頁(yè)，共30頁(yè)，2023年，2月20日，星期四以邊界表示的四連通區(qū)域種子填充算法(基于遞歸)取(x,y)為種子點(diǎn)VoidBoundaryFill4(intx,inty,intboundarycolor,intnewcolor){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);BoundaryFill4(x,y-1,boundarycolor,newcolor);}}

基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒有被填充過，對(duì)其填充，并重復(fù)上述過程，直到所有像素填充完畢。第24頁(yè)，共30頁(yè)，2023年，2月20日，星期四例：填充如下區(qū)域：堆棧的變化如圖所示。邊界表示的四連通區(qū)域種子填充算法 基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，依“左上右下”順序判斷相鄰像素，若其不是邊界像素且沒有被填充過，對(duì)其填充，并重復(fù)上述過程，直到所有像素填充完畢。 可以使用棧結(jié)構(gòu)來實(shí)現(xiàn)該算法，算法的執(zhí)行步驟如下： 種子像素入棧，當(dāng)棧非空時(shí)，重復(fù)執(zhí)行如下三步操作：

1）棧頂像素出棧；

2）將出棧像素置成多邊形填充的顏色；

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

1）棧頂像素出棧；

2）將出棧像素置成多邊形填充的顏色；

3）按左、上、右、下的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素是區(qū)域內(nèi)的像素，則把該像素入棧。第26頁(yè)，共30頁(yè)，2023年，2月20日，星期四VoidFloodFill4(intx,inty,intoldcolor,intnewcolor){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);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ù)上述過程，直到所有像素填充完畢第27頁(yè)，共30頁(yè)，2023年，2月20日，星期四特點(diǎn)：(1)有些像素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一