楊　璽　吳　晟　李英娜　李　川

(昆明理工大學信息工程與自動化學院　云南 昆明 650500)

?

基于不規(guī)則三角網(wǎng)的等值線填充算法

楊璽吳晟李英娜李川

(昆明理工大學信息工程與自動化學院云南 昆明 650500)

現(xiàn)有基于不規(guī)則三角網(wǎng)的等值線填充算法較少，且不能精確判斷區(qū)域顏色。對此給出一種通過不規(guī)則三角網(wǎng)快速填充等值線圖的算法，搜索出所有開區(qū)域輪廓，通過圍成區(qū)域等值線屬性值與不同顏色的對應關(guān)系確定區(qū)域顏色，采用深度優(yōu)先的方法對開區(qū)域及其內(nèi)部的多級封閉區(qū)域進行矢量填充。對不同數(shù)據(jù)源運行該算法，并與其他算法進行比較，根據(jù)對比結(jié)果可知該算法比現(xiàn)有算法更適合于基于三角網(wǎng)生成的等值線圖精確填充。

等值線圖顏色填充三角網(wǎng)對應關(guān)系深度優(yōu)先

0　引　言

利用規(guī)則矩形網(wǎng)格和不規(guī)則三角網(wǎng)TIN(Triangulation Irregular Network)方法可以生成等值線，對等值線圍成的區(qū)域進行顏色填充能夠使等值線圖更直觀地反映區(qū)域的屬性值范圍。為了使等值線圖準確反映數(shù)據(jù)分布情況，需要找到一種合理的算法生成并填充等值線。

傳統(tǒng)的等值線生成與填充通常采用規(guī)則網(wǎng)格法，但很多時候需要在一個不規(guī)則空間內(nèi)生成等值線，即離散數(shù)據(jù)點坐標分布沒有規(guī)律性。此時，如采用規(guī)則矩形網(wǎng)格方式繪制等值線，首先需要采用插值法將不規(guī)則離散點集變?yōu)橐?guī)則網(wǎng)格離散點集，但等值線的走向往往與實測有一定偏差。而采用三角網(wǎng)方法生成的等值線能很好地解決這一問題。

鄭元滿等[1]通過樣本點與等值線屬性值比較來填色，簡化了填色過程，但是采用矩形網(wǎng)格追蹤算法生成等值線，偏離原始數(shù)據(jù)分布情況。張登榮等基于等值線的拓撲關(guān)系實現(xiàn)等值線填充[2],通過拓撲樹可以矢量填充等值線區(qū)域，但是沒有給出顏色確定方法。韓麗娜[3]等采用雙屬性法來進行區(qū)域的顏色確定，通過圍成區(qū)域的等值線平均值確定區(qū)域顏色，方法簡單，但是顏色與區(qū)域?qū)傩灾涤幸欢ㄆ?。李強等[4]針對溫度分布等值線利用圍成區(qū)域的屬性值變化趨勢來判斷區(qū)域顏色，對于由顯著趨勢的等值線圖可以準確填色，但是不能適應復雜趨勢情況。劉冬韡等[5]通過等值線分類確定填色順序，引入格點數(shù)據(jù)進行顏色確定，填色準確，但是對于含大量閉合區(qū)域的等值線圖填充過程較慢。

為此，本文給出了一種基于不規(guī)則三角網(wǎng)的等值線圖填充方法，采用逐點插入法生成TIN的方式繪制等值線，無需對離散數(shù)據(jù)網(wǎng)格化，更能精確反映離散數(shù)據(jù)分布情況。并通過兩點屬性值比較與深度優(yōu)先搜索的方法確定填充區(qū)域顏色，填色準確，效率較高。

1　算法原理與數(shù)據(jù)結(jié)構(gòu)定義

生成等值線圖并填充顏色，主要是在原始離散數(shù)據(jù)的組成的空間點集上用逐點插入法建立TIN[6]，采用線性插值法生成所有等值線[7，8]，確定填充區(qū)域的輪廓與顏色，再進行矢量填充。

等值線圖中的填充區(qū)域可以分為開區(qū)域和封閉區(qū)域兩類，其中，開區(qū)域由一條或幾條等值線與等值線圖邊界的子線段確立，閉合區(qū)域由一條封閉的等值線確立。等值線圖可以既含有開區(qū)域也含有閉區(qū)域，也可以只含有開區(qū)域或者只含有閉區(qū)域，需要分情況進行填充。

這里定義一條等值線即為單等值線，則未填充顏色的等值線圖G擁有n種具有不同Z值(屬性值)的等值線，且每種等值線有mi(mi≥ 1)條單等值線。則：

(1)

Contourline_Si={SingleLinej|Z(SingleLinej)=Zi}j≤mi

(2)其中，Contourline_Si為Z值為Zi的等值線集合，BoundaryLines為邊界線集合，SingleLinej為Contourlines_Si中的第j條單等值線。

算法采用C++實現(xiàn)，具體數(shù)據(jù)結(jié)構(gòu)定義如下：

數(shù)據(jù)結(jié)構(gòu)1單等值線集數(shù)據(jù)結(jié)構(gòu)

class Contourline_S

{

public:

float Z;

//等值線屬性值

list singleLines;

//Z值相同的等值線集合

};

其中，SINGLELINE為自定義的一個具有屬性的單條等值線的數(shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)2單等值線數(shù)據(jù)結(jié)構(gòu)

typedef struct _SINGLELINE

{

list singleLine;

//具有具體屬性值的單條等值線

}SINGLELINE;

其中，Cline為一個線段類。

2　填充算法

對于等值線圖的填充，關(guān)鍵是要確定開區(qū)域或封閉區(qū)域的顏色，這需要建立一張顏色表，通過等值線屬性值與顏色的對應關(guān)系來確定填充區(qū)域顏色。

2.1顏色表的建立

具有n+1種顏色的等值線圖應包含n種具有不同Z值的單等值線集。據(jù)此，可以為等值線圖建立一個具有n+1個顏色值的并且按所表示Z值大小升序排列的顏色表ColorTable(即一個顏色數(shù)組Color[n+1])。ColorTable與按屬性值升序排列分類的單等值線集數(shù)組Contourline[n]的構(gòu)成及對應關(guān)系如圖1所示。

具體顏色值Color[i]、Color[i+1]與屬性值為Zi的單等值線集合Contourline[i]具有對應關(guān)系，可以表述為：在屬性值為Zi的單條等值線兩側(cè)的區(qū)域顏色為Color[i]和Color[i+1]。通過這種關(guān)系，便可以確定由等值線圍成區(qū)域的顏色。

圖1　單等值線集與顏色對應關(guān)系

2.2含有開區(qū)域的等值線圖填充

首先，利用線性插值法可以繪制出所有等值線。基于TIN中三角形邊采用線性插值法生成等值線的公式為：

(3)

(4)

其中，(x1,y1)、(x2,y2)分別為三角網(wǎng)一邊兩個端點的坐標，z1、z2為該邊兩個端點的屬性值，x、y為在該邊上插入等值點的坐標,z為該等值點的屬性值。生成的單等值線集數(shù)組為Contourlines[n]。

然后，找到TIN的邊界點集，把所有單等值線端點插入到該點集中，對新點集逆時針排序，利用邊界點追蹤算法生成一個新的開區(qū)域輪廓[9]，采用深度優(yōu)先策略對開區(qū)域及其內(nèi)部的封閉區(qū)域進行顏色的確定與填充。

對所有開區(qū)域及其內(nèi)部的封閉區(qū)域都按上述方法進行操作，便完成了整個等值線圖的填充。流程如圖2所示。

圖2　含有開區(qū)域等值線圖的填充流程

2.2.1邊界點集合的生成

對TIN內(nèi)的每個三角形存儲三個邊的鄰接三角形信息。如果一個三角形的某條邊沒有鄰接三角形，則該條邊即為TIN的邊界子線段。此時，TIN的邊界由在原始數(shù)據(jù)點集中并且在邊界子線段上的點連接而成，設(shè)該點集為ST。

S={Pi|Pi∈ST}∪{LPi|LPi∈SL}

(5)

如圖3所示，將該點集按空間關(guān)系逆時針排序，并存儲在有序邊界點列表S′中。

圖3　邊界點集分布

2.2.2開區(qū)域的填充1) 確定開區(qū)域輪廓

利用邊界點追蹤填充區(qū)域的方法，確立一個由非閉合等值線和邊界線段組成的開區(qū)域Ri。并設(shè)該區(qū)域輪廓點集中的第一個在S′中并且是單等值線端點的點為A。然后，找到S′中排在點A前面的一個點，設(shè)為A′(若A為S′中第一個點，則A′為S′中的最后一個點)。

2) 確定開區(qū)域顏色并填充

開區(qū)域包括兩種模式：

模式1由Z值為zi的等值線組中的一條單等值線和邊界中的線段圍成(如圖4中單等值線L1和邊界線段Lc1、Lc2圍成的區(qū)域R1)；

模式2由Z值為zi和zi±1的兩個等值線組中的一條或多條單等值線和邊界線段圍成(如圖4中單等值線L1、L2、L3和邊界線段Lc3、Lc4、Lc5圍成的區(qū)域R2)。

圖4　開區(qū)域分類

文獻[10]通過圍成開區(qū)域等值線屬性值個數(shù)與大小確定顏色，需要知道區(qū)域輪廓所有等值線的屬性值，計算量大，為此，本文通過兩點比較法來確定開區(qū)域顏色。 方法如下：

(1) 如圖5(a)所示的區(qū)域Ri，A′∈ST，即點A′不是等值線端點，而是三角網(wǎng)點。此時，由于A′在填充區(qū)域Ri的內(nèi)部，如果設(shè)點A所在單等值線的索引比較Z(A′)與Z(A)的大小，如果Z(A′)>Z(A)，則Color(Ri) =Color[i+1]，如果Z(A′)

算法1

if(ContourlineIndex(Z(A)) == i)

if Z(A′)>Z(A)

set Color(Ri) = Color[i+1];

else if Z(A′)

set Color(Ri) = Color[i];

Fill(Ri,Color(Ri));

其中，ContourlineIndex(Z(A))為A點所在單等值線集在Contourline[n]中的索引，F(xiàn)ill(Ri,Color(Ri))為填充區(qū)域函數(shù)。

(2) 如圖5(a)中的Ri′所示單等值線與邊界線段圍成開區(qū)域情況。由式(3)、式(4)可知，單等值線兩頭必然落在兩條不同的三角網(wǎng)邊上，所以Ri′輪廓中，必然有一個以上的集合ST中的點。所以單等值線圍成區(qū)域的顏色值可以由算法1確定。

(3) 如圖5(b)所示，A′∈SL，即點A′為單等值線端點。此時，A′為單等值線上的點，但是，如果在線段AA′上取一個虛擬的點A″，則A″的Z值有兩種情況：一是Z(A″)>Z(A)，二是Z(A″)

圖5　開區(qū)域顏色確定方法

上述方法(1)-方法(3)中，Z(A)>Z(A′)或Z(A)

如果如圖5(a)所示，A′∈ST(即A′為原始數(shù)據(jù)點)或者如圖5(b)所示，A′∈SL(即A′為等值線上的點)，則A、A′必然在TIN中同一個三角形的同一條邊上(如果A、A′在TIN中三角形的兩條不同的邊上，則A、A′之間必定有一個三角形邊的頂點屬于集合ST)。此時，由于采用的等值線生成算法為線性插值法，則該邊上的任意兩點屬性值必然不等，即點A、A′的屬性值必然不相等。

這樣即使不知道圍成開區(qū)域所有等值線的屬性值也能確定開區(qū)域顏色。

2.2.3封閉區(qū)域的填充

對于封閉區(qū)域的填充，無論是文獻[3]提出的雙屬性算法還是文獻[4]提出的趨勢判斷法，都無法對內(nèi)部不包含子封閉區(qū)域的封閉區(qū)域的顏色進行準確判斷。為此，本文給出一種利用已填充區(qū)域顏色值，逐級進行深度遍歷填充子封閉區(qū)域的方法。

如圖6所示，L1或L3圍成的封閉區(qū)域R1、R3被區(qū)域Ri所包圍，如果兩個區(qū)域之間只隔著一條單等值線即為相鄰區(qū)域，則區(qū)域R1、R3與Ri是相鄰的，并R1、R3為Ri的一級子封閉區(qū)域。同樣的，R2與Ri不相鄰，與R1相鄰，為R1的一級子封閉區(qū)域，且說R2為Ri的二級子封閉區(qū)域，R4與R2類似。一個開或閉區(qū)域的多級子封閉區(qū)域的定義以此類推。由于含有開區(qū)域的等值線圖中的封閉區(qū)域一定是由某一個開區(qū)域包含的，所以只要對所有開區(qū)域的一到多級子封閉區(qū)域逐級填充便可以完成整個等值線圖的填充。下面結(jié)合圖6給出的具有代表性的示例，對一個開區(qū)域及其內(nèi)部所有子封閉區(qū)域逐級填充的具體方法。

設(shè)圖6中的開區(qū)域Ri為當前已填充區(qū)域R，并設(shè)Color(Ri)的顏色表索引為i，即Color(Ri)==Color[i]。由圖1所示單等值線與顏色的對應關(guān)系可知，R的一級子封閉區(qū)域顏色為Color[i+1] 或者Color[i-1]。如果一級子封閉區(qū)域的顏色為Color[i+1]，則其輪廓為單等值線集Contourline[i].SingleLines[mi]中的一條單等值線，如果顏色為Color[i-1]，則其輪廓為Contourline[i-1].SingleLines[mi-1]中的一條單等值線。找到單等值線集Contourline[i].SingleLines[mi]和Contourline[i-1].SingleLines[mi-1]中被Ri的輪廓包含且圍成區(qū)域與R相鄰的封閉單等值線即為R的一個一級子封閉區(qū)域輪廓。

判斷Contourline[i].SingleLines[mi]或者Contourline[i-1].SingleLines[mi-1]中的一條單等值線Lt圍成區(qū)域Rt與R相鄰與否的具體方法為：如果Lt(圖6中的L1、L3)不被其他同屬性值的封閉單等值線包含，則Rt為R的一級子封閉區(qū)域(圖6中的R1、R3)輪廓，對Lt圍成的區(qū)域Rt進行填充；如果Lt(如圖6中的L2)被其他同屬性值的一條封閉單等值線(圖6中的L1)包含，而且包含Lt的這條同屬性值單等值線圍成的區(qū)域(設(shè)為圖6中的R1)沒有被填充，則代表Lt圍成區(qū)域Rt與R不相鄰，暫不對其進行填充。

在對圖6中Ri的二級子封閉區(qū)域R2、R4填充時，可以遞歸地將當前區(qū)域R由Ri換為R1及R3，再對R的一級子封閉區(qū)域進行填充操作即可，同樣地，Ri的多級子封閉區(qū)域也采用類似方法進行填充，直到當前區(qū)域R沒有相鄰子封閉區(qū)為止。

圖6　封閉區(qū)域分布情況

2.3不含開區(qū)域的等值線圖填充

有時等值線圖中只包含封閉區(qū)域，如圖7所示。這種情況下，由于等值線圖邊界上沒有等值點，需要把邊界當做一個特殊的開區(qū)域RS進行填充。由于邊界中必然包含一個三角網(wǎng)點PS，由圖1可知，只需比較PS的屬性值Z(PS)與單等值線集數(shù)組Contourline[n]中的Contourline[i]屬性值Z(Contourline[i])大小即可確定RS的顏色。例如，如果Z(PS) >Z(Contourline[i])且Z(PS)

圖7　不含開區(qū)域的等值線圖示例

2.4復雜度分析

本文算法對開區(qū)域的填充采用兩點屬性值比較方法，在等值線圖由t個開區(qū)域，且每個開區(qū)域由k條非封閉等值線圍成的情況下，僅需進行屬性值的t次比較就能確定開區(qū)域顏色，時間復雜度為O(t)。對于封閉區(qū)域的填充，算法采用深度優(yōu)先搜索方式確定區(qū)域顏色與填充，填充一個封閉區(qū)域需對其在屬性值上相鄰的單等值線集進行遍歷。如果等值線圖含有n種屬性等級，每種等級有m條封閉等值線，算法對封閉區(qū)域填充的時間復雜度應為O(nm2)。算法的總時間復雜度為O(t) +O(nm2)。但經(jīng)過大量數(shù)據(jù)分析發(fā)現(xiàn)，當n線性增長時，t也呈線性增長且速率與n一致，但k、m往往保持在常量水平，故算法的實際時間復雜度為O(n)+O(n)即O(n)。

文獻[10]對開區(qū)域的填充須記錄所有等值線屬性值，時間復雜度為O(kt)，對封閉區(qū)域的填充通過三角網(wǎng)中線段與等值線的空間關(guān)系及屬性值比較來確定區(qū)域顏色，時間復雜度為O(nm)，總時間復雜度為O(kt)+O(nm)，由上述分析可知，實際時間復雜度應為O(n)+O(n)亦即O(n)。但三角網(wǎng)生長方法效率較低[6]，已經(jīng)很少有人使用，本文算法采用逐點插入法生成三角網(wǎng)，故本文算法在實用性上更高。

3　實　驗

采用C++與OpenCV編程實現(xiàn)上述算法。圖8為通過對一組數(shù)據(jù)20種不同屬性等級的等值線圖進行本文算法實現(xiàn)的耗時曲線，從中可以看出算法時間復雜度為O(n)這與2.4節(jié)分析的一致。

圖8　算法耗時曲線

圖9為采用邊界掃描算法填充的包含開區(qū)域等值線圖，該算法不能對閉區(qū)域進行填充。圖10為利用本文給出方法對包含開區(qū)域等值線圖的填充結(jié)果?？梢钥闯觯疚姆椒蚀_地填充了封閉區(qū)域。

圖11為采用文獻[10]提出的基于逆生長三角網(wǎng)算法填充的不含開區(qū)域等值線圖，可見不能對等值線圖的邊界圍成的區(qū)域進行填充。圖12為采用本文方法填充的不含開區(qū)域的等值線圖。通過對比可以看出，本文方法對于包含或者不包含開區(qū)域的等值線圖均能進行較好的填充。

圖9　含開區(qū)域等值線圖的邊界掃描算法填充結(jié)果

圖10　含開區(qū)域等值線圖的基于本文算法填充結(jié)果

圖11　不含開區(qū)域等值線圖的基于逆生長三角網(wǎng)算法填充結(jié)果

圖12　不含開區(qū)域等值線圖的基于本文算法填充結(jié)果

4　結(jié)　語

本文先采用逐點插入法生成TIN，再生成等值線，充分發(fā)揮了TIN方式生成等值線更忠實于原始離散數(shù)據(jù)分布情況的特點，確保了等值線圖的精確性。同時，采用兩點屬性值比較法判斷開區(qū)域顏色，采用深度優(yōu)先遍歷方式，根據(jù)當前等值線的屬性值逐層對包含的封閉區(qū)域進行顏色判斷。對于一些顏色走勢不顯著與走勢復雜的情況也能夠進行很好的填充，且能夠?qū)Σ缓_區(qū)域的等值線圖進行填充。本文實現(xiàn)了對基于TIN生成的等值線圖的精確繪制。

通過程序?qū)崿F(xiàn)，證明了該方法簡單、可靠，為等值線圖的填充算法研究提供了一個有效參考，且能在地理信息系統(tǒng)開發(fā)中得以較好應用。此外，本方法應用在了瞬變電磁探測數(shù)據(jù)的成圖與識別系統(tǒng)中。

[1] 鄭元滿,姚長利,張晨,等.基于等值線拓撲走向的快速區(qū)域填充算法[J].石油地球物理勘探,2010,45(6):899-908.

[2] 張登榮,劉紹華,毛天露,等.等值線自動建立拓撲關(guān)系算法與快速填充應用[J].中國圖象圖形學報,2001,6(3):264-269.

[3] 韓麗娜,石昊蘇,張群會.基于邊界點追蹤的等值線圖區(qū)域填充算法[J].計算機工程與科學, 2006,28(11):66-67.

[4] 李強,李超,甘建紅.基于三角網(wǎng)的等值線填充算法研究[J].計算機工程與應用,2013,49(5):185-189.

[5] 劉冬韡,戴建華,林紅,等.基于等值線分類的區(qū)域填充算法[J].氣象科技, 2009,37(5):597-600.

[6] 余杰,呂品,鄭昌文.Delaunay三角網(wǎng)構(gòu)建方法比較研究[J].中國圖象圖形學報,2010,15(8):1158-1167.

[7] 付曉東,趙俊三,馬紹雄.不規(guī)則區(qū)域內(nèi)基于D_TIN的等值線生成算法[J].昆明理工大學學報:理工版,2006,31(6):46-50.

[8] 陳宏文,曾繁彩,王剛龍,等.改進Delaunay 三角網(wǎng)格等值線提取方法[J].熱帶海洋學報,2013,32(4):92-96.

[9] 康建榮.不規(guī)則區(qū)域等值線拓撲關(guān)系的建立及充填算法[J].測繪通報,2004(9):7-9.

[10] 張道軍,李瑞雪,席振銖,等.基于逆生長三角網(wǎng)的等值線圖自動填充算法[J].地球物理學進展,2014,29(3):1458-1462.

THE CONTOUR FILLING ALGORITHM BASED ON TRIANGULATED IRREGULAR NETWORK

Yang XiWu ShengLi YingnaLi Chuan

(FacultyofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,Kunming650500,Yunnan,China)

Currently, there are little contour filling algorithm based on triangulated irregular network, and have trouble in judging color regions accurately. In this case, an algorithm of filling contour map rapidly by triangulated irregular network is proposed to search for outlines of all open regions. Then the region color is confirmed by the corresponding relationship between the attribute value of isograms and different colors, and the multistage closed region of open regions and its inside is filled with vectors by using the method of deep optimization. After running the algorithm on different data sources and comparing with other algorithms, it is learned that the proposed algorithm is more suitable to fill contour map generated by triangulated network accurately than other existing algorithms.

Contour mapColor fillingTriangulation networkCorresponding relationsDepth-first

2015-07-04。云南省應用基礎(chǔ)研究計劃項目(2013FZ 021)。楊璽，碩士生，主研領(lǐng)域：地理信息系統(tǒng)。吳晟，教授。李英娜，副教授。李川，教授。

TP391

A

10.3969/j.issn.1000-386x.2016.10.059