區域填充算法在多重嵌套多邊形圖形中的應用

邱國清

?

區域填充算法在多重嵌套多邊形圖形中的應用

邱國清

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

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

等間距平行線；內點；多重嵌套；區域填充；子塊

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

1 基于等間距平行線區域填充算法

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

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

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

(2) 根據相鄰兩個內點的坐標，按精度值大小繪制子塊。

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

1.1 繪制等間距平行線

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

其中，[]為取整符號。

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

計算得到的坐標依次保存在數組中。

(3) 成對讀取數組里的坐標值，繪制等間距平行線，計算每條平行線經過內點的個數及相應的行列值，計算如下：

內點個數為

內點坐標分別為

1.2 算法描述

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

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

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

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

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

(6) 根據式(5)和(6)計算每條平行線所經過的內點個數及其相應的坐標值，對所有內點填充。

1.3 區域填充算法流程圖

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

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

1.4 區域填充算法與圖形學算法的區別

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

2 數據驗證及算法對比

2.1 數據采集及驗證

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

圖2 多邊形區域的等間距平行線

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

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

根據表1的結果可以得出每一條平行線與輪廓各邊的交點，按照1.1算法第3步的計算公式可以計算出每條平行線經過內點個數及相應行列值，實驗數據見表2。

2.2 多邊形多重嵌套的區域填充

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

表2 計算輪廓內點個數及行列值

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

圖3 任意嵌套的區域填充

2.3 算法對比與復雜度分析

2.3.1 算法對比

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

2.3.2 算法復雜度分析

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

表3 算法對比

表4 算法復雜度分析

2.3.3 區域填充的自動化和算法適應性

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

2.4 算法技術難點的分析

在使用自主設計的應用程序對等間距平行線區域填充算法進行數據驗證的過程中，遇到以下兩個關鍵技術難點，分析如下：

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

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

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

圖5 內層多邊形與等間距平行線的交點

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) 如何準確計算等間距平行線同時經過相互嵌套的多邊形的條數。只有先計算出同時經過相互嵌套的多邊形的條數，才能準確知道兩個多邊形從第幾個循環填充開始外層與被嵌套的多邊形交點成對，否則就是外層多邊形坐標自行成對。解決方法為找出被嵌套的多邊形橫坐標的最小和最大值，最小值除以間距就是第一條同時經過相互嵌套的多邊形的平行線，最大值除以間距就是最后一條同時經過相互嵌套的多邊形的平行線，每條線有4組坐標，兩兩成對，實現填充。

第一次同時經過相互嵌套的多邊形的線=

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

最后同時經過相互嵌套的多邊形的線=

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

3 總 結

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

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

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

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

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

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

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

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