多邊形圖形的環(huán)狀掃描線種子填充算法

邱國(guó)清

（閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000）

多邊形圖形的環(huán)狀掃描線種子填充算法

邱國(guó)清

（閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000）

遞歸種子填充算法在對(duì)多邊形區(qū)域填充時(shí)存在一個(gè)點(diǎn)多次進(jìn)出堆棧且占用大量存儲(chǔ)空間，只適合于細(xì)小區(qū)域填充.為此，基于Morton碼原理提出一種改進(jìn)算法.首先，將填充胚的行列值轉(zhuǎn)換成十進(jìn)制Morton碼，其次將每個(gè)填充胚的值與堆棧中的種子點(diǎn)Morton碼一一匹配，避免堆棧中出現(xiàn)重復(fù)點(diǎn)，最后采用環(huán)狀掃描線方式按順時(shí)針或逆時(shí)針方向?qū)Χ噙呅螀^(qū)域進(jìn)行掃描填充.經(jīng)過實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證，改進(jìn)算法能節(jié)省較多的存儲(chǔ)空間，避免一個(gè)點(diǎn)反復(fù)多次進(jìn)出堆棧.

Morton碼；環(huán)狀掃描線；遞歸種子算法；堆棧；填充胚

0 引言

區(qū)域填充算法是指給出一個(gè)區(qū)域的邊界，在邊界范圍內(nèi)對(duì)所有像素單元賦予指定的顏色代碼［1］，傳統(tǒng)的種子填充算法，無論是簡(jiǎn)單種子填充算法還是掃描線種子填充算法，總免不了要將已經(jīng)填充過的像素點(diǎn)進(jìn)行再次或多次重復(fù)判斷［2］，這會(huì)占用非常大的存儲(chǔ)空間和堆棧的溢出.種子填充算法是利用棧結(jié)構(gòu)的搜索算法［3］，改進(jìn)后的遞歸種子填充算法對(duì)原算法中的堆棧結(jié)構(gòu)進(jìn)行合理的修改，在保存種子點(diǎn)的行列值的同時(shí)也保留行列值所對(duì)應(yīng)的十進(jìn)制Morton編碼［4］，對(duì)于每一個(gè)種子點(diǎn)只有唯一的編碼，當(dāng)新的種子點(diǎn)進(jìn)入堆棧，先將行列值轉(zhuǎn)換成相應(yīng)的編碼，再搜索堆棧，檢索是否存在相同的編碼，避免一個(gè)點(diǎn)多次反復(fù)進(jìn)入.改進(jìn)后的算法采用環(huán)狀掃描線的方式依順時(shí)針或逆時(shí)針進(jìn)行掃描填充，如圖1所示，優(yōu)點(diǎn)在于能完整地搜索到區(qū)域內(nèi)每個(gè)內(nèi)點(diǎn)，算法容易實(shí)現(xiàn)，同時(shí)十進(jìn)制Morton編碼可以確保每個(gè)內(nèi)點(diǎn)都有唯一的編碼值，有利于比較，避免出現(xiàn)同一個(gè)點(diǎn)多次進(jìn)出堆棧.

1 遞歸種子填充改進(jìn)算法

1.1 基本思路

每次找到一個(gè)新的填充胚時(shí)，將填充胚放入堆棧，同時(shí)記錄該填充胚的行列值并一起壓入堆棧，當(dāng)再次找到新的填充胚時(shí)，進(jìn)入堆棧前先搜索匹配是否存在與該填充胚具有相同行列值的填充胚，如存在則該填充胚不再重復(fù)進(jìn)入堆棧，否則壓入堆棧，這樣避免一個(gè)點(diǎn)重復(fù)進(jìn)入堆棧，避免堆棧溢出.同時(shí)為了節(jié)省存儲(chǔ)空間，在連續(xù)經(jīng)過兩次填充胚填充后，堆棧中僅需保留連續(xù)兩次循環(huán)產(chǎn)生的填充胚和對(duì)應(yīng)的行列值，之前循環(huán)產(chǎn)生的填充胚可以刪除，例如，當(dāng)填充胚完成第3次擴(kuò)散與填充后，只保留第2次和第3次循環(huán)產(chǎn)生的填充胚，第1次循環(huán)產(chǎn)生的填充胚對(duì)應(yīng)的行列值可以全部刪除，以此類推，堆棧中始終保留最近連續(xù)兩次循環(huán)產(chǎn)生的填充胚及對(duì)應(yīng)行列值，這樣就可以極大節(jié)省存儲(chǔ)空間.

圖1 環(huán)狀掃描線示意圖

1.2 遞歸種子填充改進(jìn)算法的具體步驟

從當(dāng)前點(diǎn)檢測(cè)相鄰像素有4連同和8連同兩種方法【5】.改進(jìn)的遞歸種子填充算法以4連同為例.

第1步，從給定的種子填充胚出發(fā)，向上、下、左、右4個(gè)方向中任意選定一個(gè)且按順時(shí)針或逆時(shí)針環(huán)狀掃描進(jìn)行擴(kuò)散與填充，當(dāng)4個(gè)方向都被填充一次則表明第一次填充胚擴(kuò)散填充完成，然后將種子點(diǎn)及行列值和新得到的填充胚及行列值轉(zhuǎn)換成十進(jìn)制的Morton編碼放入堆棧中，同時(shí)將邊界點(diǎn)的行列值也轉(zhuǎn)換成十進(jìn)制的Morton編碼放入堆棧但邊界點(diǎn)不能作為填充胚.

第2步，將新得到的填充胚依次出棧，按第1步的方法進(jìn)行環(huán)狀掃描擴(kuò)散與填充，得到新的填充胚在入棧前，先搜索堆棧中已經(jīng)存在的填充胚行列值進(jìn)行匹配，如果匹配成功，說明該填充胚已存在，不要再重復(fù)進(jìn)入，否則放入堆棧，同時(shí)還要和邊界點(diǎn)行列值匹配，防止邊界溢出.所謂區(qū)域的邊界點(diǎn)，就是無論將它的鄰域取得多小，它都包含有集合的內(nèi)點(diǎn)和外點(diǎn)［6］.

第3步，將每次環(huán)狀掃描循環(huán)產(chǎn)生新的填充胚行列值放入棧中，只保留最近連續(xù)兩次循環(huán)產(chǎn)生的填充胚，刪除之前所有的填充胚，不包含邊界點(diǎn)，以節(jié)省存儲(chǔ)空間.

第4步，當(dāng)棧非空時(shí)，轉(zhuǎn)到第一步，否則算法結(jié)束.

1.3 改進(jìn)算法的流程圖

改進(jìn)算法流程圖如圖2所示.

圖2 改進(jìn)算法流程圖

2 柵格的行列值與十進(jìn)制Morton編碼的轉(zhuǎn)換

先將行與列的值轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)，再將二進(jìn)制的行與列的每一位依次交叉排列，從而產(chǎn)生新的二進(jìn)制數(shù)據(jù)，最后將二進(jìn)制數(shù)據(jù)轉(zhuǎn)換成十進(jìn)制數(shù)值，即得到Morton編碼，例如，第5行第3列的柵格單元，行與列轉(zhuǎn)換為二進(jìn)制后分別為：101和011，交叉排列生成新的二進(jìn)制為100111，轉(zhuǎn)換成十進(jìn)制為39，即Morton編碼，如圖3所示.

圖3 行列值與Morton編碼的轉(zhuǎn)換

圖4 邊界點(diǎn)與填充胚

3 數(shù)據(jù)驗(yàn)證

3.1 多邊形區(qū)域填充

圖4表示一個(gè)多邊形區(qū)域，屬性等于1的點(diǎn)為區(qū)域范圍線上的像元，屬性為2的是填充胚.

填充前，首先把邊界點(diǎn)對(duì)應(yīng)的行列值轉(zhuǎn)換成相應(yīng)的Morton碼保存在堆棧中，用來檢測(cè)填充胚是否溢出.圖1中的種子填充胚的行列值為7行6列，對(duì)應(yīng)的二進(jìn)制分別為0111，0110，按位交叉排列后得到新的二進(jìn)制數(shù)為00111110，轉(zhuǎn)換成十進(jìn)制Morton碼為62，以種子填充胚為中心，采用四鄰法從種子填充胚頂部開始按順時(shí)針方向進(jìn)行搜索與填充，得到4個(gè)新的填充胚，它們對(duì)應(yīng)的行列值分別是8行6列、7行7列、6行6列和7行5列，轉(zhuǎn)換成相應(yīng)的十進(jìn)制Morton碼分別是148、63、60、59，在進(jìn)入堆棧前先搜索堆棧中的邊界點(diǎn)和填充胚的編碼值，檢查是否存在邊界溢出和重復(fù)的點(diǎn)，將4個(gè)新的填充胚放入堆棧，這樣第1次循環(huán)填充結(jié)束，開始第2次循環(huán)填充，編碼為148的點(diǎn)開始以同樣的方法填充，得到新的填充胚行列值分別是9行6列、8行7列、7行6列、8行5列，轉(zhuǎn)換成十進(jìn)制Morton碼分別是150、149、62、145，在進(jìn)入堆棧前先和邊界點(diǎn)堆棧中第1次循環(huán)產(chǎn)生的填充胚進(jìn)行匹配，其中7行6列的編碼為62的點(diǎn)已經(jīng)存在于堆棧中，所以不能再重復(fù)進(jìn)入，其他3個(gè)新的填充胚進(jìn)入堆棧.其次以編碼為63的點(diǎn)開始搜索填充，得到的填充胚對(duì)應(yīng)的十進(jìn)制Morton碼是149、106、61、62，和堆棧中的邊界點(diǎn)和其他填充胚進(jìn)行一一匹配后得出，編碼62、149已經(jīng)存在不能再重復(fù)進(jìn)入.再次以編碼為60的點(diǎn)為中心開始填充，得到的十進(jìn)制Morton碼分別為62、61、64、57，進(jìn)行匹配后可以看到編碼61和編碼62已經(jīng)存在不能重復(fù)進(jìn)入.最后以編碼59為中心進(jìn)行填充，得到十進(jìn)制Morton碼為145、62、57、58，進(jìn)行匹配后看到編碼62、57、145已經(jīng)存在不能再進(jìn)入，第2次循環(huán)填充結(jié)束，堆棧中的填充胚為編碼62、148、63、60、59、150、147、145、106、61、54、57、58在內(nèi)的12個(gè)點(diǎn)，其中種子填充胚在進(jìn)行2次循環(huán)填充后已經(jīng)不可能需要再次出棧填充，所以可以從堆棧中刪除，以節(jié)省存儲(chǔ)空間.同樣的方法，開始第3次循環(huán)填充，得到新的填充胚在經(jīng)過與堆棧中的邊界點(diǎn)和其他已經(jīng)存在的點(diǎn)匹配后可以進(jìn)入堆棧，當(dāng)?shù)?次循環(huán)填充結(jié)束后，應(yīng)當(dāng)及時(shí)刪除第1次循環(huán)產(chǎn)生的填充胚，始終只保留連續(xù)兩輪循環(huán)填充產(chǎn)生的填充胚，及時(shí)釋放出堆?？臻g.在循環(huán)填充時(shí)，要防止堆棧溢出.

3.2 算法評(píng)價(jià)

由表1可知：1）將多邊形圖形中的柵格點(diǎn)所對(duì)應(yīng)的行列值轉(zhuǎn)換成十進(jìn)制Morton編碼，可以保證唯一性，避免同一個(gè)點(diǎn)多次反復(fù)進(jìn)出堆棧.2）對(duì)于復(fù)雜大型的多邊形圖形，需要填充的點(diǎn)繁多且存在許多狹窄區(qū)域，改進(jìn)后的算法以環(huán)狀掃描方式進(jìn)行填充，能很輕松填充滿整個(gè)多邊形，這些是種子填充算法無法實(shí)現(xiàn)的.3）環(huán)狀掃描線遇到邊界點(diǎn)的時(shí)候，不會(huì)再將該點(diǎn)作為種子點(diǎn)存入堆棧.4）隨著環(huán)狀掃描循環(huán)次數(shù)的增大，每次掃描得到的點(diǎn)成倍增加，填充效率非常好.

4 總結(jié)

基于遞歸種子填充算法采用十進(jìn)制Morton編碼和環(huán)狀掃描線方法提出一種新的改進(jìn)算法，從數(shù)據(jù)驗(yàn)證的結(jié)果可以看出，改進(jìn)后的算法占用極少的堆?？臻g，避免一個(gè)點(diǎn)多次反復(fù)進(jìn)入堆棧，做到一個(gè)填充胚只檢索一次，即節(jié)約時(shí)間也節(jié)省存儲(chǔ)空間，該算法適合填充比較大的多邊形圖形.

［1］閆浩文，楊樹文，孫建國(guó)，等.計(jì)算機(jī)地圖制圖原理與算法基礎(chǔ)［M］.北京：科學(xué)出版社，2007：216-217.

［2］張正峰，馬少飛，李瑋.新的種子點(diǎn)區(qū)域填充算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（6）：201.

［3］馬治平.一種區(qū)域填充算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2004，21（4）：84-85.

［4］聶慶華.地理信息系統(tǒng)及其在環(huán)境科學(xué)中的應(yīng)用［M］.北京：高等教育出版社，2006：171-175.

［5］秦曉嶶.區(qū)域填充算法的研究［J］.赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2011，27（6）：47-49.

［6］鄧國(guó)強(qiáng)，孫景鰲，蔡安妮，等.一種基于曲線積分的區(qū)域填充算法［J］.北京郵電大學(xué)學(xué)報(bào)，2001，24（2）：87-91.

The Seed Filling Algorithm for Circular Scan Lines of Polygon

QIU Guoqing
（College of Computer,Minnan Normal University，363000，F(xiàn)ujian，Zhangzhou，China）

Recursive seed filling algorithm on ploygon filling when there is a multiple import and stack occupies a lot of storage space，only suitable for small area filling.Therefore，based on the Morton code principle and proposes an improved algorithm.First，the filling embryo value into the rank of hexadecimal Morton code.Second，fill each embryo one by one in orde to avoid duplication of point stack.Last，use the circular scan line in clockwise or counterclockwise direction of polygon scan fill.A lot of experiment date show，the new algorithm can save more storage space than old way and avoid one point repeated import stack.

Morton code；circular scan line;recursive seed algorithm;stack；filling embryo

TP 399

A

2095-0691（2017）01-0064-04

表1 根據(jù)圖1計(jì)算出的數(shù)據(jù)

循環(huán)次數(shù)1 2 3 4 5存儲(chǔ)空間4個(gè)字節(jié)8個(gè)字節(jié)11個(gè)字節(jié)15個(gè)字節(jié)20個(gè)字節(jié)新得到點(diǎn)的坐標(biāo)(x,y) (8,6)(7,7)(6,6)(7,5) (9,6)(8,7)(8,5)(7,8)(6,7)(5,6)(6,5)(7,4) (10,6)(9,7)(9,5)(8,8)(8,4)(7,9)(6,8)(5,7) (4,5)(6,4)(7,3) (11,6)(10,7)(10,5)(9,8)(9,4)(8,9)(8,3) (7,10)(6,9)(5,8)(4,7)(5,4)(6,3)(7,2) (12,6)(11,7)(11,5)(10,4)(10,8)(9,9)(9,3) (10,9)(9,10)(7,11)(6,10)(5,9)(4,8)(3,7) (4,6)(6,4)(5,5)(4,4)(5,3)(7,1)十進(jìn)制Morton值148、63、60、59 150、147、145、106、61、54、57、58 140、151、147、192 144、117、104、55 49、56、47 158、157、153、194 134、193、133、110 105、98、53、50、45、46 180、159、155、152 199、195、135、201 198、111、108、99 96、31、52、56、51、48、39、43

2016-11-25

福建省教育廳科研項(xiàng)目（JAT160290）

邱國(guó)清（1975- ），男，江西臨川人，講師，碩士，研究方向：圖形編碼處理.