掃描線多邊形填充算法

1、12021-12-1 我們知道多邊形是常用基本圖形，它是由一組邊圍我們知道多邊形是常用基本圖形，它是由一組邊圍成，封閉區(qū)域，多邊形也可以是凸、凹或是帶空洞。多成，封閉區(qū)域，多邊形也可以是凸、凹或是帶空洞。多邊形區(qū)域填充就是將區(qū)域內(nèi)的像素置成新的顏色值或圖邊形區(qū)域填充就是將區(qū)域內(nèi)的像素置成新的顏色值或圖案。由于任何一個封閉曲線都可以用多邊形來逼近，所案。由于任何一個封閉曲線都可以用多邊形來逼近，所以多邊形填充實用面廣。以多邊形填充實用面廣。 一、多邊形區(qū)域填充一、多邊形區(qū)域填充 3.4.2 掃描線多邊形填充算法掃描線多邊形填充算法演示演示22021-12-11 1區(qū)域內(nèi)部點判斷準則區(qū)域內(nèi)部點判斷

2、準則 區(qū)域填充首先判斷一個像素點是否處于多邊形區(qū)域內(nèi)區(qū)域填充首先判斷一個像素點是否處于多邊形區(qū)域內(nèi), ,其判其判斷準則如下：斷準則如下： 從該點向無窮遠處引出一條射線（也稱掃描線），若射線與從該點向無窮遠處引出一條射線（也稱掃描線），若射線與區(qū)域邊界交點目標數(shù)目為奇數(shù)，則此點在區(qū)域內(nèi)。若射線與區(qū)區(qū)域邊界交點目標數(shù)目為奇數(shù)，則此點在區(qū)域內(nèi)。若射線與區(qū)域邊界交點目標數(shù)目為偶數(shù)，則此點為區(qū)域外點。域邊界交點目標數(shù)目為偶數(shù)，則此點為區(qū)域外點。例如：例如：A A點向右引射線點向右引射線與區(qū)域邊界共與區(qū)域邊界共3 3個交點，為內(nèi)點個交點，為內(nèi)點B B點向右引射線點向右引射線與區(qū)域邊界共與區(qū)域邊界共2 2個

3、交點，為外點個交點，為外點AB32021-12-1此時應(yīng)注意兩點：此時應(yīng)注意兩點：（1 1）當掃描線與多邊形相交如下情況時）當掃描線與多邊形相交如下情況時: :YXAIBEDCF若兩相鄰邊與掃描線相交于同一點，且兩邊位于掃描線同側(cè)若兩相鄰邊與掃描線相交于同一點，且兩邊位于掃描線同側(cè)，則視為兩個交點。，則視為兩個交點。如如y yb b：1 1點向右交點為點向右交點為3 3個（奇數(shù)）是內(nèi)點個（奇數(shù)）是內(nèi)點 3 3點向右交點為點向右交點為4 4個（偶數(shù)）是外點個（偶數(shù)）是外點若兩相鄰邊與掃描線相交于同一點，且兩邊位于掃描線異側(cè)若兩相鄰邊與掃描線相交于同一點，且兩邊位于掃描線異側(cè)，則視為一個交點。，則

4、視為一個交點。如如y ya ay yb b31y ya a42021-12-1（2 2）當掃描線重合多邊形某條邊界水平線時，如該水平）當掃描線重合多邊形某條邊界水平線時，如該水平邊線前后兩條邊線是一上一下的，則該水平邊線兩個端點邊線前后兩條邊線是一上一下的，則該水平邊線兩個端點作為一個交點，即掃描線與該水平邊界線相交了一次。作為一個交點，即掃描線與該水平邊界線相交了一次。 如下圖如下圖yCBXYDCBAE如該水平邊線前后兩條邊線是同為上或同為下的，則將該水平邊如該水平邊線前后兩條邊線是同為上或同為下的，則將該水平邊線兩個端點作為交點，即掃描線與該水平邊界線相交了兩次。如線兩個端點作為交點，即掃

5、描線與該水平邊界線相交了兩次。如yDEyCByDE52021-12-1 2 2邊相關(guān)性及邊記錄邊相關(guān)性及邊記錄 很顯然，不能利用區(qū)域內(nèi)部點判別準則對顯示平面很顯然，不能利用區(qū)域內(nèi)部點判別準則對顯示平面上每個點逐個判別，這樣計算量太大。上每個點逐個判別，這樣計算量太大。 事實上，相對于一個給定多邊形區(qū)域來說，顯示平事實上，相對于一個給定多邊形區(qū)域來說，顯示平面上每個像素點內(nèi)外特性是互相關(guān)聯(lián)的。相鄰像素間具面上每個像素點內(nèi)外特性是互相關(guān)聯(lián)的。相鄰像素間具有相關(guān)屬性。在實施多邊形填充時，利用掃描線相關(guān)性，有相關(guān)屬性。在實施多邊形填充時，利用掃描線相關(guān)性，就無需對掃描線上所有像素點逐個地進行內(nèi)外特性判

6、斷，就無需對掃描線上所有像素點逐個地進行內(nèi)外特性判斷，只需對一條掃描線從左到右求出該掃描線與區(qū)域邊界交只需對一條掃描線從左到右求出該掃描線與區(qū)域邊界交點，這些交點必將掃描線分成內(nèi)外交替線段，這些交點點，這些交點必將掃描線分成內(nèi)外交替線段，這些交點x x值大小依次排列。值大小依次排列。 62021-12-1XYAB CD如上圖，按如上圖，按x x從小到大排列為從小到大排列為A B C DA B C D交點交點ABAB間線段上像素點必在區(qū)域內(nèi)。間線段上像素點必在區(qū)域內(nèi)。所以所以關(guān)鍵是求交點關(guān)鍵是求交點。72021-12-1 （1 1）交點計算）交點計算 多邊形填充首先需要求出掃描線與邊界的交點，利

7、用邊的相關(guān)多邊形填充首先需要求出掃描線與邊界的交點，利用邊的相關(guān)性可以簡單有效地解決這個問題。當一條掃描線性可以簡單有效地解決這個問題。當一條掃描線y yi i 與多邊形的某一與多邊形的某一邊線有交點時，其相鄰掃描線邊線有交點時，其相鄰掃描線y yi+1i+1一般也與該邊線相交（除非一般也與該邊線相交（除非y yi+1i+1超超出了該邊線所在區(qū)間），出了該邊線所在區(qū)間），而且掃描線而且掃描線y yi+1i+1與該邊線的交點，很容易從與該邊線的交點，很容易從前一條掃描線前一條掃描線y yi i與該邊的交點遞推求得。與該邊的交點遞推求得。 設(shè)某條直線邊的方程為設(shè)某條直線邊的方程為 y=mx+by=

8、mx+b 該邊兩個端點坐標為（該邊兩個端點坐標為（x x1 1, ,y y1 1) )、（、（x x2 2, ,y y2 2) ) 且且x x1 1x x2 2 則該邊斜率為則該邊斜率為m=(m=(y y2 2- -y y1 1)/()/(x x2 2- -x x1 1) ) 令掃描線令掃描線y yi i與該邊交點為（與該邊交點為（x xi i，y yi i） 掃描線掃描線y yi i1 1與該邊交點（與該邊交點（x xi i1 1，y yi i1 1）82021-12-1 A(8,2)C(8,8)B(3,7)yi(x xi,i,y yi i)邊線邊線ABAB第第y yi i條掃描線條掃描線與

9、某邊線與某邊線ABAB的的交點是交點是( (x xi i,y,yi i) ) 第第y yi+1i+1條掃描線條掃描線與與ABAB的交點為（的交點為（x xi+1i+1, y, yi+1i+1 ）則第則第y yi+1i+1條掃描線與條掃描線與ABAB的交點為的交點為y yi+1i+1= =y yi i+1, +1, x xi+1i+1= =x xi i+1/m +1/m 即由前一條即由前一條掃描線交點掃描線交點X Xi i，Y Yi i求下一條掃描線交點求下一條掃描線交點X Xi i1 1，Y Yi+1,i+1,式中，式中，m m是這條邊的是這條邊的斜率。斜率。（x xi+1i+1, y, yi

10、+1i+1)邊線邊線ACACmxmbbmxmbymbyxbmxyybmxyiiiiiiiiii/1/)1(/)1(/)()2(1)1(1111 1/myi+192021-12-1（2 2）邊記錄）邊記錄利用邊的這種相關(guān)性，不必算出邊線與各條掃描線的全利用邊的這種相關(guān)性，不必算出邊線與各條掃描線的全部交點，只需以邊線為單位，對每條邊建立一個邊記錄，部交點，只需以邊線為單位，對每條邊建立一個邊記錄，其內(nèi)容包括：其內(nèi)容包括：該邊該邊y y的最大值的最大值y ymax max , ,該邊底端的該邊底端的x x坐標坐標x xi i, ,從一條掃描線到下一條掃描線間的從一條掃描線到下一條掃描線間的x x增

11、量增量1/1/m,m,以及指示以及指示下一個邊記錄地址的指針下一個邊記錄地址的指針 7 8 18 8 0ABACymax xi 1/m ymax xi 1/m A(8,2)C(8,8)B(3,7)102021-12-13 3邊表邊表ETET和活動邊表和活動邊表AET AET （1 1）邊表邊表ET ET （EdgeEdge Table)Table)邊表是一個包含多邊形全部邊記錄的表，它按邊表是一個包含多邊形全部邊記錄的表，它按y y坐標（與掃描線坐標（與掃描線一一對應(yīng)）遞增（或遞減）的順序存放區(qū)域邊界的所有邊。每一一對應(yīng)）遞增（或遞減）的順序存放區(qū)域邊界的所有邊。每個個y y坐標值存放一個或者

12、說幾個邊記錄。當某條掃描線坐標值存放一個或者說幾個邊記錄。當某條掃描線y yi i碰到多碰到多邊形邊界的新邊時（邊形邊界的新邊時（以邊線底端為準以邊線底端為準），則在），則在ETET表中相應(yīng)的表中相應(yīng)的y y坐坐標值處寫入一個邊記錄。當同時有多條邊進入時，則在標值處寫入一個邊記錄。當同時有多條邊進入時，則在ETET表中表中按鏈表結(jié)構(gòu)寫入相應(yīng)數(shù)目的多個記錄，按鏈表結(jié)構(gòu)寫入相應(yīng)數(shù)目的多個記錄，這些記錄是按邊線較低這些記錄是按邊線較低端點的端點的x x值增加的順序排列值增加的順序排列。當沒有新邊加入時，表中對應(yīng)的。當沒有新邊加入時，表中對應(yīng)的y y坐標值處存儲內(nèi)容為空白。坐標值處存儲內(nèi)容為空白。圖4

13、.40 多邊形圖4.40 多邊形P P1 1P P5 5P P4 4P P3 3P P2 2O O1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 81 12 23 34 45 56 67 7 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6 - -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?ymax xi 1/m 112

14、021-12-1注意：注意：在在ETET表中：與表中：與x x軸平行的邊不計入。多邊形的頂點軸平行的邊不計入。多邊形的頂點分為兩大類：一類是局部極值點，如下圖中的分為兩大類：一類是局部極值點，如下圖中的P P1 1、P P3 3；另一類另一類是非極值點，如下圖中的是非極值點，如下圖中的P P2 2、P P4 4、P P5 5。當掃描線與第一類頂點當掃描線與第一類頂點相遇時，應(yīng)看作兩個點；當掃描線與第二類頂點相遇時，應(yīng)相遇時，應(yīng)看作兩個點；當掃描線與第二類頂點相遇時，應(yīng)視為一個點。視為一個點。 7 7 2 24 4 7 7 8 8- -1 1 6 6 2 20 0 3 3 6 6 - -2 25

15、 5 6 6 0 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?圖圖4 4. .4 40 0 多多邊邊形形P P1 1P P5 5P P4 4P P3 3P P2 2O O1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 81 12 23 34 45 56 67 7 多邊形邊表多邊形邊表多邊形邊表邊表多邊形邊表邊表ymax xi 1/m 122021-12-1活動邊表活動邊表

16、AET(Activities EdgeAET(Activities Edge Table)Table) 活動邊表活動邊表AETAET是一個只與當前掃描線相交的邊記錄鏈表是一個只與當前掃描線相交的邊記錄鏈表。隨著。隨著掃描線從一條到另一條的轉(zhuǎn)換，掃描線從一條到另一條的轉(zhuǎn)換，AETAET表也應(yīng)隨之變動，利用表也應(yīng)隨之變動，利用 y yi+1i+1= =y yi i+1, +1, x xi+1i+1= =x xi i+1/m+1/m 可以算出可以算出AETAET表中表中x x域中的新值域中的新值x xi i。凡是與這一條掃描線相交的凡是與這一條掃描線相交的任何新邊都加到任何新邊都加到AETAET表中

17、，而與之不相交的邊又被從表中，而與之不相交的邊又被從AETAET表中刪除表中刪除掉了。下圖列出了多邊形圖在掃描線為掉了。下圖列出了多邊形圖在掃描線為4 4、5 5、6 6時的時的AETAET表。表。AETAET表表中的記錄順序仍是按中的記錄順序仍是按x x增大排序的。增大排序的。 6 62 20 0P P4 4P P5 5A AE ET T指指針針5 5 7 7. .5 5 0 0. .5 5 P P3 3P P2 2掃掃描描線線 4 46 62 20 0P P4 4P P5 5A AE ET T指指針針7 78 8- -1 1 P P2 2P P1 1掃掃描描線線 5 57 72 24 4P

18、 P5 5P P1 1A AE ET T指指針針7 77 7- -1 1 P P2 2P P1 1掃掃描描線線 6 6圖圖4 4. .4 42 2 活活動動邊邊表表圖圖 4 4. .4 40 0 多多 邊邊 形形P P 1 1P P 5 5P P 4 4P P 3 3P P 2 2O O 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 81 12 23 34 45 56 67 7132021-12-14 4多邊形區(qū)域填充算法過程多邊形區(qū)域填充算法過程 （1 1）根據(jù)給出的頂點坐標數(shù)據(jù)，按）根據(jù)給出的頂點坐標數(shù)據(jù)，按y y遞增順序建立遞增順序建立ETET表表（2 2）根據(jù)）根據(jù)AET

19、AET指針，使之為空。指針，使之為空。（3 3）使）使y=Yy=Yminmin （Y Yminmin為頂點坐標中最小為頂點坐標中最小y y值）。值）。（4 4）反復(fù)做下述各步，直至）反復(fù)做下述各步，直至y=Yy=Ymaxmax（頂點坐標中頂點坐標中y y的最的最大值）或大值）或ETET與與AETAET為空：為空： 將將ETET表加入到表加入到AETAET中，并保持中，并保持AETAET鏈中的記錄按鏈中的記錄按x x值值 增大排序。增大排序。 對掃描線對掃描線y yi i依次成對取出依次成對取出AETAET中中x xi i值，并在每對值，并在每對x xi i 之間填上所要求的顏色或圖案。之間填上

20、所要求的顏色或圖案。 從從AETAET表中刪去表中刪去y yi i=y=ymaxmax的記錄。的記錄。 對保留下來的對保留下來的AETAET中的每個記錄，用中的每個記錄，用x xi i+1/m+1/m代替代替x xi i ，并重新按并重新按x x遞增排序。遞增排序。 使使y yi i+1+1，以便進入下一輪循環(huán)。以便進入下一輪循環(huán)。142021-12-1P1P5P4P3P2O123456781234567圖4.40 多邊形開始開始y y1 1，將將ETET表中表中y y1 1結(jié)點加入至結(jié)點加入至AETAET表，同時保持表，同時保持AETAET鏈中記錄按鏈中記錄按x x增大排增大排序序3 6 -

21、25 6 0.5 AET由于上例中是由于上例中是6 66 6，是頂點，是頂點，所以中間不填像素顏色。所以中間不填像素顏色。上例由于上例由于Y Ymaxmax3 3和和5 5，所以不必刪去，當，所以不必刪去，當y yi i3 3時，此時時，此時就得將第一個結(jié)點即（就得將第一個結(jié)點即（3 3，6 6，2 2）刪去。）刪去。對保留下來的對保留下來的AETAET中的每個記錄，用中的每個記錄，用x xi i+1/m+1/m代替代替x xi i，并重新按并重新按x x遞增排序。如上例變成遞增排序。如上例變成( (實際求出實際求出y=2y=2時新的交點時新的交點x x坐標）：坐標）：3 4 -2 5 6.5

22、 0.5 AET 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6- -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?152021-12-1使使y yi i+1+1，以便進入下一輪循環(huán)。即以便進入下一輪循環(huán)。即y y2 2再進入以上循環(huán)再進入以上循環(huán)繼續(xù)：由繼續(xù)：由y y2 2，ETET表中是空，所以不需表中是空，所以不需ETET表加

23、入表加入AETAET表表 取取x x4 4和和x x6.5,6.5,將將4 46.56.5之間填上像素顏色之間填上像素顏色。 由于由于y=2,y=2,不必刪去結(jié)點。不必刪去結(jié)點。 再改變再改變x xi i的值為的值為 使使y yi i 3 3，重復(fù)繼續(xù)。繼續(xù)：由重復(fù)繼續(xù)。繼續(xù)：由y y3 3，將將ETET表中表中y y3 3結(jié)點加入，即結(jié)點加入，即 將將2 27 7之間填上像素顏色之間填上像素顏色。 刪去結(jié)點刪去結(jié)點Y Ymaxmax3 3 結(jié)點。結(jié)點。3 2 -2 5 7 0.5 AET3 2 -25 7 0.5 AET6 2 06 2 05 7 0.5 AETP1P5P4P3P2O1234

24、56781234567圖4.40 多邊形 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6 - -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?3 4 -2 5 6.5 0.5 AET162021-12-1 再改變再改變x xi i的值為的值為 使使y yi i 4 4，重復(fù)繼續(xù)。重復(fù)繼續(xù)。 6 2 05 7.5 0.5 AETP1P

25、5P4P3P2O123456781234567圖4.40 多邊形 7 72 24 4 7 78 8- -1 1 6 62 20 0 3 36 6- -2 25 56 60 0. .5 5 1 15 54 43 32 26 67 7P P5 5P P1 1P P2 2P P1 1P P4 4P P5 5P P3 3P P4 4P P3 3P P2 2? ? 4 4. .4 41 1 ? ? ? ? ? ? ? ? ? ? ? ?172021-12-1P0P1P2P3P4P5舉例舉例演示演示182021-12-1二、二、 邊填充邊填充 邊填充算法的基本原理是：邊填充算法的基本原理是：（1 1）對多

26、邊形的每條邊進行直線掃描轉(zhuǎn)換，即對多邊形邊）對多邊形的每條邊進行直線掃描轉(zhuǎn)換，即對多邊形邊界經(jīng)過的像素打上邊標志；界經(jīng)過的像素打上邊標志；（2 2）對多邊形內(nèi)部進行填充。填充時，對每條掃描線，依）對多邊形內(nèi)部進行填充。填充時，對每條掃描線，依從左到右的順序，逐個訪問掃描線上的像素，用一個布爾量從左到右的順序，逐個訪問掃描線上的像素，用一個布爾量來標志當前點是在多邊形內(nèi)部還是外部（一開始設(shè)布爾量的來標志當前點是在多邊形內(nèi)部還是外部（一開始設(shè)布爾量的值為假，當碰到設(shè)有邊標志的點時，就把其值取反；對沒有值為假，當碰到設(shè)有邊標志的點時，就把其值取反；對沒有邊標志的點，則其值保持不變）邊標志的點，則其值

27、保持不變）（3 3）將其布爾量值為）將其布爾量值為“真真”的內(nèi)部置為圖形色，把其布爾的內(nèi)部置為圖形色，把其布爾量的值為量的值為“假假”的外部點置為底色即可。的外部點置為底色即可。 192021-12-1三、三、 種子填充種子填充 1 1、種子填充基本思路、種子填充基本思路 首先假設(shè)在多邊形區(qū)域的內(nèi)部，至少有一個像素點（稱為種子）首先假設(shè)在多邊形區(qū)域的內(nèi)部，至少有一個像素點（稱為種子）是已知的，然后算法開始搜索與種子點相鄰且位于區(qū)域內(nèi)的其它像是已知的，然后算法開始搜索與種子點相鄰且位于區(qū)域內(nèi)的其它像素。如果相鄰點不在區(qū)域內(nèi)，那么到達區(qū)域的邊界；如果相鄰點位素。如果相鄰點不在區(qū)域內(nèi)，那么到達區(qū)域的

28、邊界；如果相鄰點位于區(qū)域內(nèi)，那么這一點就成為新的種子點，然后繼續(xù)遞歸地搜索下于區(qū)域內(nèi)，那么這一點就成為新的種子點，然后繼續(xù)遞歸地搜索下去。去。 區(qū)域的連通情況可以分為四連通和八連通兩種區(qū)域的連通情況可以分為四連通和八連通兩種四連通區(qū)域：各像素在水平和垂直四個方向上是連通的四連通區(qū)域：各像素在水平和垂直四個方向上是連通的. .八連通區(qū)域八連通區(qū)域：各像素在水平、垂直以及四個對角線方向上都是連通的。：各像素在水平、垂直以及四個對角線方向上都是連通的。 202021-12-1 在種子填充算法中，如果允許從四個方向搜尋下一在種子填充算法中，如果允許從四個方向搜尋下一個像素點，則該算法稱為四向算法；如果

29、允許從八個方個像素點，則該算法稱為四向算法；如果允許從八個方法搜尋下一個像素點，則該算法稱為八向算法。法搜尋下一個像素點，則該算法稱為八向算法。 一個八向算法可以用在四連通區(qū)域的填充上，也可一個八向算法可以用在四連通區(qū)域的填充上，也可用在八連通區(qū)域的填充上；而一個四向算法只能用于填用在八連通區(qū)域的填充上；而一個四向算法只能用于填充四連通區(qū)域。充四連通區(qū)域。 無論是四向算法還是八向算法，它們的填充算法基無論是四向算法還是八向算法，它們的填充算法基本思想是相同的。為簡單起見，下面只討論四向種子填本思想是相同的。為簡單起見，下面只討論四向種子填充算法。充算法。 212021-12-1種子填充算法種子

30、填充算法基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個像素是已基本思想：假設(shè)在多邊形區(qū)域內(nèi)部至少有一個像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對其進行填充。他像素，并對其進行填充。由于區(qū)域可采用邊界定義和內(nèi)點定義兩種方式，區(qū)域按由于區(qū)域可采用邊界定義和內(nèi)點定義兩種方式，區(qū)域按連通性又可分為四連通區(qū)域和八連通區(qū)域兩類，所以常用的連通性又可分為四連通區(qū)域和八連通區(qū)域兩類，所以常用的種子填充算法有：種子填充算法有： 邊界表示的四連通區(qū)域種子填充算法邊界表示的四連通區(qū)域種子填充算法 內(nèi)點表示的四連通區(qū)域種子填充算法內(nèi)點表示的四

31、連通區(qū)域種子填充算法 邊界表示的八連通區(qū)域種子填充算法邊界表示的八連通區(qū)域種子填充算法 內(nèi)點表示的八連通區(qū)域種子填充算法內(nèi)點表示的八連通區(qū)域種子填充算法222021-12-1232021-12-1邊界填充算法（四連通域）邊界填充算法（四連通域） 在區(qū)域有一個像素是已知（在區(qū)域有一個像素是已知（種子像素種子像素），由此像素），由此像素從從四個方向四個方向遍歷區(qū)域內(nèi)所有像素。（適用于交互繪圖）遍歷區(qū)域內(nèi)所有像素。（適用于交互繪圖）0 1 2 3 4 54321用什么方法實現(xiàn)？用什么方法實現(xiàn)？注意：242021-12-1取取(x,y)為種子點為種子點Void BoundaryFill4(int x,

32、int y ,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, newcol

33、or); BoundaryFill4(x,y-1, boundarycolor, newcolor); 252021-12-1262021-12-1272021-12-1Void 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,

34、 oldcolor, newcolor); FloodFill4(x+1,y, oldcolor, newcolor); FloodFill4(x,y-1, oldcolor, newcolor); 取取(x,y)為種子點為種子點282021-12-1種子填充法種子填充法292021-12-1上述簡單種子填充算法操作過程非常簡單，卻要進行深上述簡單種子填充算法操作過程非常簡單，卻要進行深度的遞歸，這不僅要花費許多時間，降低了算法的效率度的遞歸，這不僅要花費許多時間，降低了算法的效率，而且還要花費許多空間要構(gòu)造堆棧結(jié)構(gòu)。因此出現(xiàn)了，而且還要花費許多空間要構(gòu)造堆棧結(jié)構(gòu)。因此出現(xiàn)了改進的掃描線種子填

35、充算法。改進的掃描線種子填充算法。(3)(3)掃描線種子填充算法掃描線種子填充算法 掃描線種子填充算法適用于邊界定義的四連通區(qū)域。區(qū)域掃描線種子填充算法適用于邊界定義的四連通區(qū)域。區(qū)域可凹可凸，還可以包括一個或多個孔。在邊界定義區(qū)域外或與可凹可凸，還可以包括一個或多個孔。在邊界定義區(qū)域外或與其鄰接的區(qū)域中像素的值或顏色不同于填充區(qū)域或多邊形的值其鄰接的區(qū)域中像素的值或顏色不同于填充區(qū)域或多邊形的值或顏色?；蝾伾?。 算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當前掃描線上的該段區(qū)間；然后確定與這條掃描線上一組相鄰元素），填充當前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進行這個過程，直到所保