邱國清

?

基于柵格的任意復(fù)雜區(qū)域自動填充算法

邱國清

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

基于柵格與等間距平行線原理，設(shè)計出一種適用于任意復(fù)雜區(qū)域完全自動化填充算法。首先，將整個填充區(qū)域柵格化。其次，繪制一組等間距平行線，計算每條平行線經(jīng)過多邊形區(qū)域內(nèi)柵格的行列序號值。最后，根據(jù)計算出柵格的行列序號值，采用自主循環(huán)方法對每個柵格單元填充，最終實現(xiàn)整個區(qū)域的自動化填充。通過自主設(shè)計的應(yīng)用程序驗證多組數(shù)據(jù)表示該算法能快速自動填充，對實驗中出現(xiàn)的技術(shù)難點做了詳細分析。

柵格；等間距平行線；區(qū)域填充；算法復(fù)雜度；自動化填充

區(qū)域填充是指給出一個區(qū)域的邊界，在邊界范圍內(nèi)對所有像素單元賦予指定的像素值。經(jīng)典的區(qū)域填充算法遞歸種子填充和掃描線種子填充及其的改進算法能快速實現(xiàn)填充，但區(qū)域填充的全自動化已經(jīng)成為區(qū)域填充領(lǐng)域的主要研究方向。遞歸種子算法需要預(yù)先設(shè)置填充胚，以此為基礎(chǔ)不斷搜索新的填充胚，這種方法雖然使用簡單，但無法通過狹窄區(qū)域，不能填滿整個區(qū)域，當(dāng)有多個對象需要填充時，種子點的選擇非常困難[1]，種子填充算法效率比較低的原因是大量的出入棧操作[2]。掃描線填充則需要判斷大量像素點的值，填充效率不佳，主要用來填充比較簡單的標準多邊形區(qū)域，比如圓、橢圓以及其他一些簡單的多邊形，其對輪廓線的形狀有一定要求[3]。隨著圖形學(xué)技術(shù)的發(fā)展，區(qū)域填充的全自動化和算法的通用性已經(jīng)成為衡量區(qū)域填充算法的主要參數(shù)。基于柵格和等間距平行線原理的全自動區(qū)域填充算法在實現(xiàn)自動填充和通用性方面做了具體分析和研究。

1 區(qū)域填充算法原理

1.1 等間距平行線基本原理

(2) 求新坐標系里曲面輪廓點橫坐標的最小值和最大值，取輪廓點中橫坐標最小值，為等間距平行線的間距，首先選定一條平行線開始推算，該平行線與新坐標系軸之間的距離稱為值，也就是第一條平行線的橫坐標，計算公式為[4]

其中，[ ]表示取整符號。

(3) 根據(jù)斜率公式計算交點坐標值，即

(4) 根據(jù)交點坐標計算該條平行線穿過的柵格單元的行列序號，即

其中，[ ]表示取整符號

=+(6)

1.2 奇異點的處理

當(dāng)平行線通過多邊形頂點的時會出現(xiàn)交點個數(shù)異常，這種交點計數(shù)也會出現(xiàn)二義性的情況，就是奇異點問題。正確處理好奇異點問題，是算法獲得成功的關(guān)鍵?？梢詺w納出兩點：①當(dāng)角點處的兩條輪廓邊位于剖面線的兩側(cè)時，應(yīng)計一個交點為正確。②當(dāng)角點處的兩條輪廓邊位于剖面線的同側(cè)時，應(yīng)不計交點或者索性計兩個交點為正確。要實現(xiàn)上述兩個要求，可以采用左閉右開的原則，即在一條輪廓邊線段的兩個端點中，一端采用閉區(qū)間而另一端采用開區(qū)間的處理原則。結(jié)果為：兩輪廓邊位于剖面線兩側(cè)，則角點處的兩個端點必一取一舍；兩輪廓邊位于剖面線同側(cè)，則角點處的兩個端點必同取或同舍。

1.3 區(qū)域柵格化

柵格數(shù)據(jù)是最直觀的空間數(shù)據(jù)結(jié)構(gòu)，是指將二維平面劃分為大小一致、緊密相連的網(wǎng)格陣列，每個網(wǎng)格作為一個像元，每個像元由行列號確定其位置，且具有表示實體屬性類型或值的編碼值。網(wǎng)格質(zhì)量的好壞直接影響到數(shù)值計算的精度[5]。代表像素的網(wǎng)格通常為正方形、矩形或者等邊三角形等。網(wǎng)格邊長決定了柵格數(shù)據(jù)的精度。通過平面上行距、列距固定的點內(nèi)插值是獲取柵格數(shù)據(jù)的常用方法。

1.4 算法流程圖

基于柵格與等間距平行線原理算法中，首先依次采集區(qū)域邊界頂點的坐標，找出其中橫坐標的最小值作為等間距平行線的初始值，同時按設(shè)定的精度值將整個區(qū)域柵格化，把對區(qū)域的填充轉(zhuǎn)化為對區(qū)域內(nèi)所有柵格單元的填充，柵格單元劃分的越細，填充效果越明顯，引入一組等間距平行線，計算每條平行線與所有邊界的交點，根據(jù)交點的橫坐標或縱坐標的差值來確定該條平行線穿過的單元個數(shù)及行列序號，因為柵格大小均是一致的，所以可以很快計算出所有單元的坐標，整個過程完全由計算機程序自動完成，具體的算法流程如圖1所示。

圖1 填充算法流程圖

2 數(shù)據(jù)驗證

2.1 不規(guī)則復(fù)雜區(qū)域填充

采集多邊形區(qū)域所有頂點坐標值繪制填充區(qū)域，如圖2(a)所示，該區(qū)域是一個完全不規(guī)則的圖形，有多個凹進和凸起部分，對于這樣的圖形填充，很多專業(yè)的繪圖軟件都比較難實現(xiàn)全自動填充。依照圖1，將整個區(qū)域柵格化，從圖2(b)中可以看到，所有的邊界均落在柵格單元中。根據(jù)等間距平行線繪制算法，計算每一條平行線與邊界是否存在交點以及交點的坐標，根據(jù)交點的坐標可以確定該條平行線在區(qū)域中的起點和終點的行列序號；同時根據(jù)平行線起點和終點縱坐標的差值計算出該條平行線所經(jīng)過的柵格單元個數(shù)及對應(yīng)的行列序號；最后根據(jù)每個柵格單元行列序號填充，循環(huán)依次就完成一條平行線所經(jīng)過的區(qū)域內(nèi)柵格單元的填充，再執(zhí)行下一條平行線的繪制，最終的效果如圖3所示。

圖2 不規(guī)則復(fù)雜區(qū)域的柵格化

圖3 不規(guī)則復(fù)雜區(qū)域的柵格與等間距平行線填充

圖3表示的是不規(guī)則復(fù)雜區(qū)域的等間距平行線填充，圖3(a)柵格邊長為15，平行線間距為5，圖3(b)柵格邊長為30，平行線間距為27，可以看到每一條平行線均穿過至少一列柵格單元，通過對比可以看出，網(wǎng)格密度越小，平行線間距越細，填充效果越好。以圖3(b)為例，每條平行線穿過區(qū)域內(nèi)柵格單元的行列序號見表1。

采用柵格化與等間距平行線填充算法得到的填充效果取決于柵格的大小，柵格劃分越細密，得到的填充效果越好，但計算量也變大。為了做到柵格的每一列或每一行都至少能有一條平行線穿過，約定等間距平行線的間距值不能大于柵格單元的邊長，否則會出現(xiàn)若干列或若干行沒有被平行線穿過，這樣該列或該行的柵格單元就無法被填充，圖4是柵格邊長為15，等間距平行線間距為8時的填充效果。

表1 平行線與邊界的交點及經(jīng)過內(nèi)點的行列序號表

圖4 柵格與等間距平行線算法填充效果

2.2 區(qū)域填充與其他填充算法的對比

從區(qū)域填充的全自動化和算法的普遍有效性對比，掃描線算法和種子填充算法常常不能同時滿足這兩方面的要求。掃描線種子算法是指區(qū)域內(nèi)同值相鄰像素在水平方向的組合，一段掃描線的中間只能有一種像素，需要存放每條掃描線格填充區(qū)域段右端點作為種子點。遞歸種子算法需要在區(qū)域內(nèi)設(shè)定一個種子點而且種子點反復(fù)進出堆棧，消耗大量的時間和內(nèi)存，改進的掃描線種子算法需要找出種子點所在的區(qū)域，這些經(jīng)典的填充算法在算法的適用性和填充自動化方面的無法做到最大效率?；跂鸥窕偷乳g距平行線填充算法通過將區(qū)域柵格化并引入一組等間距的平行線，計算每條平行線所經(jīng)過區(qū)域內(nèi)柵格單元的行列序號并對每個單元一一填充，不需要設(shè)置種子點，實現(xiàn)了區(qū)域填充的自動化和算法的普遍性，該算法的循環(huán)次數(shù)等于等間距平行線和多邊形邊界數(shù)目中的最大值，3種算法比較的對比結(jié)果見表2。

計算復(fù)雜度包括空間復(fù)雜度和時間復(fù)雜度?？臻g復(fù)雜度一般指存儲量的問題，時間復(fù)雜度則是指計算的工作量問題[6]。以圖2(b)為例，通過比較可以看出，采用掃描種子算法的存儲空間為58個點，柵格與等間距平行線算法存儲空間為58個點，但兩種算法的區(qū)別在于前者需要把每條掃描線的右端點作為種子胚放入堆棧，采用四鄰法的遞歸種子算法的存儲空間為22+24+26+…+22n，表示填充次數(shù)，經(jīng)過計算存儲空間大約為72個點，其中多個點反復(fù)進出堆棧。

表2 算法對比表

2.3 技術(shù)難點的分析

(1) 如果計算平行線所經(jīng)過區(qū)域內(nèi)柵格單元的行列序號?；跂鸥窕c等間距平行線填充算法的關(guān)鍵在于程序如何自主搜尋并保存每一條平行線穿過的柵格單元并記錄行列序號，為下一步的填充提供數(shù)據(jù)。根據(jù)平行線與邊界的交點，計算縱坐標方向的距離，除以柵格單元的邊長就等于該條平行線穿過柵格單元的個數(shù)，交點的起點和終點代表該條平行線首尾兩個柵格單元的平面坐標。

for (int j=0; j< tx.length(); j=j+2)

g.fillRect ((int)(tx[j]/15)*15, (int) (ty[j]/15)* 15,15, (ty[j+1]/15–ty[j]/15+1)*15)

// tx[j]/15表示列序號，ty[j]/15表示行序號，15表示柵格單元邊長，ty[j+1]–ty[j]+1表示該條平行線穿過柵格單元個數(shù)

(2) 奇異點的處理?；跂鸥衽c等間距平行線填充算法在繪制等間距平行線時難免會出現(xiàn)奇異點，解決的方式主要是通過稍微增大或者減小平行線的間距值，這樣就可以解決。

(3) 如何解決凹進與凸起部分填充問題。對于任意復(fù)雜的區(qū)域包含多個凸起和凹進部分，當(dāng)某一條平行線同時穿過多個不規(guī)則部位時，偶爾會出現(xiàn)平行線在穿過與自身垂直方向連續(xù)多個凹進或凸起區(qū)域時，既穿過區(qū)域內(nèi)的柵格單元也穿過了一些區(qū)域外不應(yīng)該被填充的單元，如圖5(a)所示，由于計算機系統(tǒng)有時難以分辨過于狹小的凹進或凸起部分，在圖中等間距平行線是垂直方向，、、、連續(xù)4個水平方向的凹進和凸起，其與等間距平行線方向基本垂直。為了避免出現(xiàn)類似問題，可以稍微調(diào)整區(qū)域頂點坐標的采集順序，原來頂點采集順序為abcdefghigklmnopqrsa，此時可調(diào)整為sabcdefghijklmnopqrs，調(diào)整后此類問題就可以解決，如圖5(b)所示。

3 結(jié)束語

基于柵格化與等間距平行線區(qū)域填充算法適用于復(fù)雜的區(qū)域填充，特別是對于凹進和凸起的區(qū)域填充更適合，有很好地填充自動化和算法的適用性，采用的是網(wǎng)格和等間距平行線計算區(qū)域內(nèi)柵格單元的行列序號，對非常復(fù)雜的區(qū)域經(jīng)一次處理即可完成全部的填充。

圖5 消除多余的區(qū)域填充

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

[2] 張正峰, 馬少飛, 李瑋. 新的種子點區(qū)域填充算法[J]. 計算機工程與應(yīng)用, 2009, 45(6): 201-202.

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

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

[5] 劉喜康, 張建海, 殷榮剛, 等. 一種基于邏輯柵格的網(wǎng)格自動生成算法[J]. 計算機工程, 2012, 38(21): 268-271.

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

Automatic Filling Algorithm of Arbitrary Complex Region Based on Grid

QIU Guoqing

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

A fully automated filling algorithm for any complex area is designed based on the principle of grid and equal-spaced parallel lines. Firstly, we turn the whole area filling into grid. Secondly, we draw a series of equidistant parallel lines and calculate row column ordinal value of each parallel line going through the polygon grid. Thirdly, each grid cell is filled with the autonomous cycle method, according to the calculation of the row and column number value of the grid. Finally, the entire area is automatically filled. The verification of multiple sets of data through an independently designed application program indicates that the algorithm can realize filling quickly and automatically, and a detailed analysis is made on the technical difficulties that occur in the experiment.

grid; parallel lines; area filling; algorithm complexity; automatic filling

TP 399

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

A

2095-302X(2018)03-0419-05

2017-08-10；

2017-09-12

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

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