邱國(guó)清

?

區(qū)域填充算法在多重嵌套多邊形圖形中的應(yīng)用

邱國(guó)清

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

區(qū)域填充算法在制圖中有著廣泛的應(yīng)用，但目前對(duì)任意多個(gè)多邊形相互嵌套的區(qū)域填充算法很難實(shí)現(xiàn)，為此提出一種基于等間距平行線的區(qū)域填充算法。首先，按一定的間隔繪制一組平行線；其次，計(jì)算所有平行線與任意嵌套的多邊形的交點(diǎn)；最后，以間隔值作為子塊大小的參數(shù)，計(jì)算每條平行線所包含的子塊個(gè)數(shù)及坐標(biāo)值并填充，最終完成整個(gè)區(qū)域填充。在實(shí)驗(yàn)的過(guò)程中解決了如何準(zhǔn)確計(jì)算相互嵌套的多邊形同時(shí)與平行線都有交點(diǎn)的問(wèn)題。通過(guò)自主設(shè)計(jì)的應(yīng)用程序驗(yàn)證多組數(shù)據(jù)，表明該算法能快速準(zhǔn)確地完成任意數(shù)量的多邊形相互嵌套的區(qū)域填充并對(duì)實(shí)驗(yàn)過(guò)程中的技術(shù)難點(diǎn)和算法復(fù)雜度做了分析。

等間距平行線；內(nèi)點(diǎn)；多重嵌套；區(qū)域填充；子塊

計(jì)算機(jī)輔助設(shè)計(jì)技術(shù)是當(dāng)今計(jì)算機(jī)輔助領(lǐng)域中的研究熱點(diǎn)之一[1]。區(qū)域填充算法在計(jì)算機(jī)輔助設(shè)計(jì)及其他領(lǐng)域有廣泛的應(yīng)用，是將區(qū)域內(nèi)的一點(diǎn)(常稱為種子點(diǎn))賦予給定顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程[2]。常用的算法有遞歸種子填充算法和掃描線填充算法，由于這些算法在實(shí)際應(yīng)用中存在一個(gè)點(diǎn)多次反復(fù)進(jìn)入堆棧占用大量存儲(chǔ)空間，當(dāng)有多個(gè)對(duì)象需要填充時(shí)，種子點(diǎn)的選擇非常困難[3]，故在這些算法的基礎(chǔ)上產(chǎn)生了一些改進(jìn)算法，這些經(jīng)典的填充算法在填充前需要設(shè)定種子點(diǎn)，往返進(jìn)出堆棧，還需要判斷多邊形邊界是否溢出，算法的通用性和填充的自動(dòng)化效果比較低，而隨著計(jì)算機(jī)圖形學(xué)技術(shù)的發(fā)展，區(qū)域填充的自動(dòng)化和適應(yīng)性算法成為衡量填充算法優(yōu)劣的關(guān)鍵參數(shù)。相對(duì)于效率而言，算法的通用性和自動(dòng)化程度是更關(guān)注的問(wèn)題[4]。基于等間距平行線區(qū)域填充算法是一種研究全自動(dòng)填充任意復(fù)雜多邊形區(qū)域的技術(shù)，是在借鑒其他算法的基礎(chǔ)上做出改進(jìn)，該算法以繪制一組等間距平行線為原理，計(jì)算每條線所經(jīng)過(guò)的內(nèi)點(diǎn)，計(jì)算簡(jiǎn)單，對(duì)圖形的適應(yīng)性強(qiáng)，不需要設(shè)置填充胚和求解邊界像素點(diǎn)序列，不存在一個(gè)點(diǎn)多次反復(fù)進(jìn)入堆棧的問(wèn)題?；贏utoCAD的二次開(kāi)發(fā)[5]，可以將區(qū)域填充技術(shù)作為子模塊嵌入到CAD系統(tǒng)中。

1 基于等間距平行線區(qū)域填充算法

基于等間距平行線區(qū)域填充算法與傳統(tǒng)的遞歸種子填充算法和掃描線填充算法的區(qū)別在于，等間距平行線區(qū)域填充算法不需要設(shè)置填充胚，每個(gè)填充點(diǎn)也不需要反復(fù)多次進(jìn)入堆棧，沒(méi)有堆棧溢出的問(wèn)題，新算法對(duì)于任意大小的多邊形區(qū)域都可以快速實(shí)現(xiàn)填充，特別是對(duì)多邊形區(qū)域狹小的凸起或凹進(jìn)部分都可以準(zhǔn)確的計(jì)算并填充。傳統(tǒng)的填充算法在存儲(chǔ)數(shù)據(jù)時(shí)需要用到堆棧結(jié)構(gòu)，存在一個(gè)點(diǎn)反復(fù)多次進(jìn)入堆棧，造成堆棧的溢出，不適合大型的多邊形區(qū)域填充。

等間距平行線區(qū)域填充算法在計(jì)算每條平行線內(nèi)點(diǎn)的同時(shí)繪制子塊并完成子塊的填充，需要準(zhǔn)確的計(jì)算出內(nèi)點(diǎn)的坐標(biāo)值，所以該算法的區(qū)域填充處理分兩個(gè)主要內(nèi)容：

(1) 對(duì)一個(gè)多邊形區(qū)域繪制一組相互垂直的等間距平行線，計(jì)算每條平行線與多邊形邊界的交點(diǎn)坐標(biāo)值。

(2) 根據(jù)相鄰兩個(gè)內(nèi)點(diǎn)的坐標(biāo)，按精度值大小繪制子塊。

因此，基于等間距平行線區(qū)域填充算法核心的問(wèn)題在于怎樣利用每條平行線內(nèi)點(diǎn)來(lái)繪制子塊。在每條平行線上取相鄰兩個(gè)點(diǎn)，以這兩點(diǎn)為基點(diǎn)，繪制長(zhǎng)度等于精度值且垂直于平行線的線段，然后連接兩條線段的端點(diǎn)使其成為一個(gè)封閉的方形，即子塊，在繪制子塊的同時(shí)完成填充，從而實(shí)現(xiàn)整個(gè)多邊形區(qū)域的填充。

1.1 繪制等間距平行線

(2) 為了能讓每條平行線穿過(guò)區(qū)域內(nèi)點(diǎn)，約定等間距平行線之間的間距等于柵格數(shù)據(jù)二維網(wǎng)格大小，這樣就可以計(jì)算出每條平行線經(jīng)過(guò)內(nèi)點(diǎn)的行列值，為區(qū)域填充提供前提條件，求新坐標(biāo)系中輪廓點(diǎn)橫坐標(biāo)的最小值和最大值，取輪廓點(diǎn)中橫坐標(biāo)最小值，為等間距平行線的間距(等于網(wǎng)格大小)，首先選定一條平行線開(kāi)始推算，該平行線與新坐標(biāo)系軸之間的距離稱為值，也就是第一條平行線的橫坐標(biāo)，即

其中，[]為取整符號(hào)。

計(jì)算平行線與輪廓各條邊的交點(diǎn)，如果(–X)(–X+1)<0，則表明有交點(diǎn)[6]，計(jì)算交點(diǎn)坐標(biāo)值，即

計(jì)算得到的坐標(biāo)依次保存在數(shù)組中。

(3) 成對(duì)讀取數(shù)組里的坐標(biāo)值，繪制等間距平行線，計(jì)算每條平行線經(jīng)過(guò)內(nèi)點(diǎn)的個(gè)數(shù)及相應(yīng)的行列值，計(jì)算如下：

內(nèi)點(diǎn)個(gè)數(shù)為

內(nèi)點(diǎn)坐標(biāo)分別為

1.2 算法描述

(1) 設(shè)置間距值，掃描多邊形圖形每個(gè)頂點(diǎn)的橫坐標(biāo)值，找出最大值和最小值，按式(3)計(jì)算第一條平行線的橫坐標(biāo)值。

(2) 根據(jù)式(4)計(jì)算新的平行線與多邊形圖形是否有交點(diǎn)，如果沒(méi)有交點(diǎn)則執(zhí)行第3步，否則執(zhí)行第4步。

(3) 計(jì)算下一條平行線的橫坐標(biāo)值，返回到第2步。

(4) 按照式(4)計(jì)算每個(gè)交點(diǎn)的坐標(biāo)值并保存。

(5) 判斷的值是否大于的最大值，如果小于則返回第3步，否則直接退出。

(6) 根據(jù)式(5)和(6)計(jì)算每條平行線所經(jīng)過(guò)的內(nèi)點(diǎn)個(gè)數(shù)及其相應(yīng)的坐標(biāo)值，對(duì)所有內(nèi)點(diǎn)填充。

1.3 區(qū)域填充算法流程圖

根據(jù)1.2 算法描述繪制出等間距平行線區(qū)域填充算法的流程圖，如圖1所示。

圖1 等間距平行線填充算法流程圖

1.4 區(qū)域填充算法與圖形學(xué)算法的區(qū)別

在計(jì)算機(jī)圖形學(xué)中，有許多經(jīng)典的填充算法，如掃描線填充、邊緣填充、邊標(biāo)志填充、邊界填充等算法，這些經(jīng)典的算法各有優(yōu)勢(shì)，但也有不足之處，如邊緣填充算法對(duì)于復(fù)雜圖形每個(gè)像素可能要訪問(wèn)多次，占用過(guò)多的存儲(chǔ)空間。邊界填充算法需要用到堆棧結(jié)構(gòu)，太多的像素壓入堆棧，空間需求量大。掃描線算法需要防止多邊形區(qū)域邊界溢出，在進(jìn)行掃描時(shí)，需要檢查是否到達(dá)邊界。區(qū)域填充算法與其他經(jīng)典算法的不同在于，該算法在每生成一條平行線時(shí)，判斷該條線與多邊形是否有交點(diǎn)，如果有則保存交點(diǎn)坐標(biāo)，如果沒(méi)有則生成新的平行線，計(jì)算簡(jiǎn)單，運(yùn)算速度塊，不需要堆棧結(jié)構(gòu)，也不需要判斷邊界。

2 數(shù)據(jù)驗(yàn)證及算法對(duì)比

2.1 數(shù)據(jù)采集及驗(yàn)證

首先讀取多邊形區(qū)域每個(gè)頂點(diǎn)的坐標(biāo)值，然后從坐標(biāo)原點(diǎn)開(kāi)始繪制一組平行于軸的等間距平行線，間距大小根據(jù)精度值來(lái)設(shè)定，最后根據(jù)1.1的計(jì)算方法求解每條平行線與多邊形邊界的交點(diǎn)并保存交點(diǎn)的坐標(biāo)值，計(jì)算每條平行線的長(zhǎng)度，除以間距，即等于該條平行線所經(jīng)過(guò)的內(nèi)點(diǎn)個(gè)數(shù)。根據(jù)每個(gè)內(nèi)點(diǎn)的坐標(biāo)，繪制垂直與平行線垂線，垂直線的距離等于平行線的間距，這樣就可以形成子塊，如圖2所示。

圖2 多邊形區(qū)域的等間距平行線

假設(shè)圖2所表示的等間距平行線與軸夾角為0，=7，多邊形頂點(diǎn)的坐標(biāo)分別為(125,95)、(155,80)、(175,115)，此時(shí)輪廓各點(diǎn)在新坐標(biāo)和原坐標(biāo)中的行列值一樣，按照計(jì)算公式得出等間距平行線與多邊形輪廓各條邊的交點(diǎn)，實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表1。

表1 等間距平行線與輪廓各條邊的交點(diǎn)

根據(jù)表1的結(jié)果可以得出每一條平行線與輪廓各邊的交點(diǎn)，按照1.1算法第3步的計(jì)算公式可以計(jì)算出每條平行線經(jīng)過(guò)內(nèi)點(diǎn)個(gè)數(shù)及相應(yīng)行列值，實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表2。

2.2 多邊形多重嵌套的區(qū)域填充

區(qū)域填充的過(guò)程中經(jīng)常會(huì)遇到多邊形嵌套的圖形，也就是孤島，在對(duì)孤島進(jìn)行區(qū)域填充時(shí)，往往會(huì)分多種情況，如圖3所示，有5個(gè)相互嵌套的多邊形，依次分為1、2、3、4、5。在1區(qū)域中嵌套2、3、4、5，而孤島4、5嵌套在孤島3中，孤島3嵌套在孤島4中。例如，只對(duì)1和2的區(qū)域進(jìn)行填充，此時(shí)可以根據(jù)等間距平行線區(qū)域填充算法，分別計(jì)算每條平行線與1、2兩個(gè)多邊形區(qū)域的交點(diǎn)，圖3中從第4條平行線開(kāi)始與1和2同時(shí)有交點(diǎn)，從第35條平行線開(kāi)始與孤島2沒(méi)有交點(diǎn)，孤島5是整個(gè)區(qū)域填充，填充時(shí)，孤島5的填充線與1、2區(qū)域的平行線是同一組。

表2 計(jì)算輪廓內(nèi)點(diǎn)個(gè)數(shù)及行列值

在圖3中，實(shí)現(xiàn)的是最外層和次外層兩個(gè)相互嵌套的多邊形和最內(nèi)層三角形的內(nèi)部區(qū)域填充，其間的相互聯(lián)系在于從第17條平行線開(kāi)始到第23條平行線結(jié)束，孤島5與1、2區(qū)域同時(shí)經(jīng)過(guò)這7條平行線，在填充時(shí)，對(duì)1和2區(qū)域的嵌套部分進(jìn)行填充，單獨(dú)對(duì)孤島5的內(nèi)部區(qū)域進(jìn)行填充。

圖3 任意嵌套的區(qū)域填充

2.3 算法對(duì)比與復(fù)雜度分析

2.3.1 算法對(duì)比

常用的多邊形區(qū)域填充算法有遞歸種子算法、掃描線填充算法以及一些改進(jìn)的算法。遞歸種子填充算法能對(duì)具有任意復(fù)雜多邊形區(qū)域進(jìn)行填充，但該算法存在一個(gè)點(diǎn)多次進(jìn)出堆棧，占用很大的存儲(chǔ)空間，僅僅只適用比較小的多邊形區(qū)域。掃描線填充算法在掃描上具有連貫性，但該算法需要重復(fù)判斷大量像素點(diǎn)的顏色以及存在不必要的回溯?；诘乳g距平行線區(qū)域填充算法以繪制等間距平行線為基礎(chǔ)，計(jì)算每條平行線經(jīng)過(guò)的內(nèi)點(diǎn)，不需要判斷內(nèi)點(diǎn)即不存在一個(gè)點(diǎn)多次進(jìn)出堆棧，占用存儲(chǔ)空間小而且具有連貫性，計(jì)算簡(jiǎn)單，實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表3。

2.3.2 算法復(fù)雜度分析

計(jì)算復(fù)雜度包括空間復(fù)雜性和時(shí)間復(fù)雜性[7]。等間距平行線區(qū)域填充算法的復(fù)雜程度取決于等間距值的大小，值越小，劃分的越細(xì)小，意味循環(huán)次數(shù)越大，交點(diǎn)越多，數(shù)據(jù)量也隨著增大，需要填充的子塊更多，但精度更好。算法在時(shí)間并不明顯，但隨著交點(diǎn)數(shù)量的增大，需要保存的交點(diǎn)的坐標(biāo)數(shù)量就大，以圖3為例，間距為7，算法的復(fù)雜度見(jiàn)表4。

表3 算法對(duì)比

表4 算法復(fù)雜度分析

2.3.3 區(qū)域填充的自動(dòng)化和算法適應(yīng)性

等間距平行線區(qū)域填充算法取多邊形頂點(diǎn)中橫坐標(biāo)中的最小值作為平行線的初始值開(kāi)始循環(huán)繪制，每循環(huán)一次繪制一條平行線，間隔等于設(shè)定的精度值，直到最后一條平行線的橫坐標(biāo)大于多邊形中橫坐標(biāo)最大值時(shí)停止循環(huán)，在每次循環(huán)繪制平行線的同時(shí)再次設(shè)定循環(huán)條件，依次計(jì)算該條平行線與多邊形的所有邊是否存在交點(diǎn)，如果有則計(jì)算并保存交點(diǎn)坐標(biāo)，否則接著循環(huán)，直到該條平行線與每條邊都計(jì)算過(guò)，這就是等間距平行線算法的兩重循環(huán)原理，完全可以實(shí)現(xiàn)填充的自動(dòng)化。該算法在編寫(xiě)程序時(shí)，只需要設(shè)定兩重循環(huán)條件即可，算法簡(jiǎn)單，有較好的適用性。

2.4 算法技術(shù)難點(diǎn)的分析

在使用自主設(shè)計(jì)的應(yīng)用程序?qū)Φ乳g距平行線區(qū)域填充算法進(jìn)行數(shù)據(jù)驗(yàn)證的過(guò)程中，遇到以下兩個(gè)關(guān)鍵技術(shù)難點(diǎn)，分析如下：

(1) 在相互嵌套的多邊形圖形中，如何準(zhǔn)確從數(shù)組中找到平行線同時(shí)經(jīng)過(guò)兩個(gè)嵌套多邊形的交點(diǎn)，如圖4~5所示。

從圖4~5中可看到，圖4的數(shù)據(jù)是外層多邊形與平行線的交點(diǎn)坐標(biāo)，圖5的數(shù)據(jù)是被嵌套的多邊形與平行線的交點(diǎn)，在圖4~5中帶下劃線的坐標(biāo)對(duì)有46對(duì)，填充時(shí)必須上下兩部分坐標(biāo)成對(duì)出現(xiàn)，否則填充就會(huì)出現(xiàn)混亂。圖4的數(shù)據(jù)中從第9個(gè)位置開(kāi)始與圖5的第一個(gè)數(shù)據(jù)成對(duì)，相差8。例如，圖4中的(65, 31)與圖5中的(65, 60)成對(duì)，圖5中的(65, 5)與圖4中的(65, 121)成對(duì)，依次類(lèi)推，兩部分有46對(duì)坐標(biāo)是成對(duì)的，圖4中的數(shù)據(jù)從第55個(gè)開(kāi)始就不再與圖5中的數(shù)據(jù)存在成對(duì)坐標(biāo)，意味此時(shí)平行線和外層多邊形有交點(diǎn)，后面的填充只需要圖4中的數(shù)據(jù)坐標(biāo)成對(duì)就可以，例如圖4中的(226, 39)與(226, 214)成對(duì)、(233, 39)與(233, 162)成對(duì)。程序的核心代碼如下：

圖4 外層多邊形與等間距平行線的交點(diǎn)

圖5 內(nèi)層多邊形與等間距平行線的交點(diǎn)

for(int i=0;i

g5.drawLine(tx[i],ty[i],tx[i+1],ty[i+1]); //平行線還未與被嵌套的多邊形有交點(diǎn)

}

for(int i=z;i

g5.drawLine(tx[i],ty[i],kkx[i-z],kky[i-z]); //平行線與被嵌套的多邊形有交點(diǎn)

i++;

g5.drawLine(kkx[i-z],kky[i-z],tx[i],ty[i]);

}

for(int i=zz+z;i<100;i=i+2){

g5.drawLine(tx[i],ty[i],tx[i+1],ty[i+1]);}//平行線離開(kāi)被嵌套的多邊形沒(méi)有交點(diǎn)

(2) 如何準(zhǔn)確計(jì)算等間距平行線同時(shí)經(jīng)過(guò)相互嵌套的多邊形的條數(shù)。只有先計(jì)算出同時(shí)經(jīng)過(guò)相互嵌套的多邊形的條數(shù)，才能準(zhǔn)確知道兩個(gè)多邊形從第幾個(gè)循環(huán)填充開(kāi)始外層與被嵌套的多邊形交點(diǎn)成對(duì)，否則就是外層多邊形坐標(biāo)自行成對(duì)。解決方法為找出被嵌套的多邊形橫坐標(biāo)的最小和最大值，最小值除以間距就是第一條同時(shí)經(jīng)過(guò)相互嵌套的多邊形的平行線，最大值除以間距就是最后一條同時(shí)經(jīng)過(guò)相互嵌套的多邊形的平行線，每條線有4組坐標(biāo)，兩兩成對(duì)，實(shí)現(xiàn)填充。

第一次同時(shí)經(jīng)過(guò)相互嵌套的多邊形的線=

[最小值/間距]–1 (7)

最后同時(shí)經(jīng)過(guò)相互嵌套的多邊形的線=

[最大值/間距)] (8)

3 總 結(jié)

計(jì)算區(qū)域內(nèi)等間距平行線經(jīng)過(guò)內(nèi)點(diǎn)的個(gè)數(shù)及對(duì)應(yīng)的行列值，根據(jù)每條平行線相鄰兩個(gè)點(diǎn)分別繪制垂直于平行線的線段，構(gòu)成一個(gè)封閉的子區(qū)域，可以快速而準(zhǔn)確的確定需要填充的網(wǎng)格子塊，為每個(gè)子塊賦予指定的像素值，不需要重復(fù)判斷內(nèi)點(diǎn)和使用堆棧結(jié)構(gòu)，避免了一個(gè)點(diǎn)多次堆棧造成溢出的缺陷。等間距平行線填充算法采用計(jì)算每條平行線與多邊形各條邊的交點(diǎn)的方法實(shí)現(xiàn)了任意多層嵌套多邊形的區(qū)域全自動(dòng)填充和任意復(fù)雜區(qū)域算法的通用性，能夠把任意復(fù)雜的多邊形區(qū)域一次完成全部填充。

[1] 熊勝華, 謝正堅(jiān), 何濤. 計(jì)算機(jī)輔助結(jié)構(gòu)設(shè)計(jì)與分析的集成框架研究[J]. 圖學(xué)學(xué)報(bào), 2012, 33(4): 129-135.

[2] 任繼成, 劉慎權(quán). 區(qū)域填充掃描線算法的改進(jìn)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1998, 10(6): 481-486.

[3] 陳優(yōu)廣, 顧國(guó)慶, 王玲. 一種基于縫隙碼的區(qū)域填充算法[J]. 中國(guó)圖象圖形學(xué)報(bào), 2007, 12(11): 2086-2092.

[4] 柳稼航, 方濤, 楊建峰. 適用于復(fù)雜區(qū)域的全自動(dòng)填充方法[J]. 計(jì)算機(jī)工程, 2008, 34(4): 238-240.

[5] 唐永勇, 馮劍, 陳國(guó)民, 等. 機(jī)械制圖中CAD教學(xué)的軟件選擇與教學(xué)設(shè)計(jì)[J]. 圖學(xué)學(xué)報(bào), 2014, 35(5): 798-803.

[6] 閆浩文, 楊樹(shù)文, 孫建國(guó), 等. 計(jì)算機(jī)地圖制圖原理與算法基礎(chǔ)[M]. 北京: 科學(xué)出版社, 2007: 132-134.

[7] 于海燕, 蔡鴻明, 何援軍. 圖學(xué)計(jì)算基礎(chǔ)[J]. 圖學(xué)學(xué)報(bào), 2013, 34(6): 1-5.

Application of Region Filling Algorithm in Multi Nested Polygon Graph

QIU Guoqing

(Computer College, Minnan Normal University, Zhangzhou Fujian 363000, China)

Region filling algorithm is widely used in drawing, but the arbitrary polygon nested region filling algorithm is very difficult to achieve, in order to solve this problem, puts forward new area filling algorithm that based on equidistant parallel lines. Firstly, draw a set of parallel lines use the same intervals. Secondly, calculation the intersection that all parallel lines with arbitrary nesting the polygon. Finally, use the interval value as a parameter sub block of size, each line contains the parallel calculation of the number of blocks and coordinates and filling, completion of the entire region filling at last. In the process of the experiment, solve the problem of computing in intersection of the nested polygons with the parallel lines is solved. Use multi group data through the application of independent design show that the algorithm can quickly and accurately complete any number of nested polygon area filling and explain the technical difficulties and algorithm complexity which arise in the process of experiment.

equal spaced parallel lines; interior point; multiple nesting; area filling; sub block

TP 399

10.11996/JG.j.2095-302X.2018020357

A

2095-302X(2018)02-0357-05

2017-06-22；

2017-08-03

福建省教育廳中青年教師科研項(xiàng)目(JAT160290)

邱國(guó)清(1975–)，男，江西臨川人，講師，碩士。主要研究方向?yàn)橛?jì)算機(jī)圖形編碼。E-mail：qiugq02@163.com