基于不規則三角網的等值線填充算法

楊　璽　吳　晟　李英娜　李　川

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

?

基于不規則三角網的等值線填充算法

楊璽吳晟李英娜李川

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

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

等值線圖顏色填充三角網對應關系深度優先

0　引　言

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

傳統的等值線生成與填充通常采用規則網格法，但很多時候需要在一個不規則空間內生成等值線，即離散數據點坐標分布沒有規律性。此時，如采用規則矩形網格方式繪制等值線，首先需要采用插值法將不規則離散點集變為規則網格離散點集，但等值線的走向往往與實測有一定偏差。而采用三角網方法生成的等值線能很好地解決這一問題。

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

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

1　算法原理與數據結構定義

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

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

這里定義一條等值線即為單等值線，則未填充顏色的等值線圖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++實現，具體數據結構定義如下：

數據結構1單等值線集數據結構

class Contourline_S

{

public:

float Z;

//等值線屬性值

list singleLines;

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

};

其中，SINGLELINE為自定義的一個具有屬性的單條等值線的數據結構：

數據結構2單等值線數據結構

typedef struct _SINGLELINE

{

list singleLine;

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

}SINGLELINE;

其中，Cline為一個線段類。

2　填充算法

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

2.1顏色表的建立

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

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

圖1　單等值線集與顏色對應關系

2.2含有開區域的等值線圖填充

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

(3)

(4)

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

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

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

圖2　含有開區域等值線圖的填充流程

2.2.1邊界點集合的生成

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

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

(5)

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

圖3　邊界點集分布

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

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

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

開區域包括兩種模式：

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

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

圖4　開區域分類

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

(1) 如圖5(a)所示的區域Ri，A′∈ST，即點A′不是等值線端點，而是三角網點。此時，由于A′在填充區域Ri的內部，如果設點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]中的索引，Fill(Ri,Color(Ri))為填充區域函數。

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

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

圖5　開區域顏色確定方法

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

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

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

2.2.3封閉區域的填充

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

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

設圖6中的開區域Ri為當前已填充區域R，并設Color(Ri)的顏色表索引為i，即Color(Ri)==Color[i]。由圖1所示單等值線與顏色的對應關系可知，R的一級子封閉區域顏色為Color[i+1] 或者Color[i-1]。如果一級子封閉區域的顏色為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的輪廓包含且圍成區域與R相鄰的封閉單等值線即為R的一個一級子封閉區域輪廓。

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

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

圖6　封閉區域分布情況

2.3不含開區域的等值線圖填充

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

圖7　不含開區域的等值線圖示例

2.4復雜度分析

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

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

3　實　驗

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

圖8　算法耗時曲線

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

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

圖9　含開區域等值線圖的邊界掃描算法填充結果

圖10　含開區域等值線圖的基于本文算法填充結果

圖11　不含開區域等值線圖的基于逆生長三角網算法填充結果

圖12　不含開區域等值線圖的基于本文算法填充結果

4　結　語

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

通過程序實現，證明了該方法簡單、可靠，為等值線圖的填充算法研究提供了一個有效參考，且能在地理信息系統開發中得以較好應用。此外，本方法應用在了瞬變電磁探測數據的成圖與識別系統中。

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

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

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

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

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

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

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

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

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

[10] 張道軍,李瑞雪,席振銖,等.基于逆生長三角網的等值線圖自動填充算法[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。云南省應用基礎研究計劃項目(2013FZ 021)。楊璽，碩士生，主研領域：地理信息系統。吳晟，教授。李英娜，副教授。李川，教授。

TP391

A

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