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

邱國清

?

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

邱國清

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

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

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

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

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

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

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

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

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

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

1.1 繪制等間距平行線

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

其中，[]為取整符號。

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

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

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

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

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

1.2 算法描述

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

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

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

(4) 按照式(4)計算每個交點的坐標(biāo)值并保存。

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

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

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

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

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

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

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

2 數(shù)據(jù)驗證及算法對比

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

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

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

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

表1 等間距平行線與輪廓各條邊的交點

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

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

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

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

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

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

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

2.3.1 算法對比

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

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

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

表3 算法對比

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

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

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

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

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

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

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

圖4 外層多邊形與等間距平行線的交點

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

for(int i=0;i

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

}

for(int i=z;i

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

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]);}//平行線離開被嵌套的多邊形沒有交點

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

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

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

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

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

3 總 結(jié)

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

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

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

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

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

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

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

[7] 于海燕, 蔡鴻明, 何援軍. 圖學(xué)計算基礎(chǔ)[J]. 圖學(xué)學(xué)報, 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

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

邱國清(1975–)，男，江西臨川人，講師，碩士。主要研究方向為計算機圖形編碼。E-mail：qiugq02@163.com