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

楊　璽　吳　晟　李英娜　李　川

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院　云南 昆明 650500)

?

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

楊璽吳晟李英娜李川

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院云南 昆明 650500)

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

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

0　引　言

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

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

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

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

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

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

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

這里定義一條等值線即為單等值線，則未填充顏色的等值線圖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++實(shí)現(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為自定義的一個(gè)具有屬性的單條等值線的數(shù)據(jù)結(jié)構(gòu)：

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

typedef struct _SINGLELINE

{

list singleLine;

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

}SINGLELINE;

其中，Cline為一個(gè)線段類。

2　填充算法

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

2.1顏色表的建立

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

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

圖1　單等值線集與顏色對(duì)應(yīng)關(guān)系

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

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

(3)

(4)

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

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

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

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

2.2.1邊界點(diǎn)集合的生成

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

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

(5)

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

圖3　邊界點(diǎn)集分布

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

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

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

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

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

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

圖4　開(kāi)區(qū)域分類

文獻(xiàn)[10]通過(guò)圍成開(kāi)區(qū)域等值線屬性值個(gè)數(shù)與大小確定顏色，需要知道區(qū)域輪廓所有等值線的屬性值，計(jì)算量大，為此，本文通過(guò)兩點(diǎn)比較法來(lái)確定開(kāi)區(qū)域顏色。 方法如下：

(1) 如圖5(a)所示的區(qū)域Ri，A′∈ST，即點(diǎn)A′不是等值線端點(diǎn)，而是三角網(wǎng)點(diǎn)。此時(shí)，由于A′在填充區(qū)域Ri的內(nèi)部，如果設(shè)點(diǎn)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點(diǎn)所在單等值線集在Contourline[n]中的索引，F(xiàn)ill(Ri,Color(Ri))為填充區(qū)域函數(shù)。

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

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

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

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

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

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

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

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

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

設(shè)圖6中的開(kāi)區(qū)域Ri為當(dāng)前已填充區(qū)域R，并設(shè)Color(Ri)的顏色表索引為i，即Color(Ri)==Color[i]。由圖1所示單等值線與顏色的對(duì)應(yīng)關(guān)系可知，R的一級(jí)子封閉區(qū)域顏色為Color[i+1] 或者Color[i-1]。如果一級(jí)子封閉區(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的一個(gè)一級(jí)子封閉區(qū)域輪廓。

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

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

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

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

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

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

2.4復(fù)雜度分析

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

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

3　實(shí)　驗(yàn)

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

圖8　算法耗時(shí)曲線

圖9為采用邊界掃描算法填充的包含開(kāi)區(qū)域等值線圖，該算法不能對(duì)閉區(qū)域進(jìn)行填充。圖10為利用本文給出方法對(duì)包含開(kāi)區(qū)域等值線圖的填充結(jié)果?？梢钥闯?，本文方法準(zhǔn)確地填充了封閉區(qū)域。

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

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

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

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

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

4　結(jié)　語(yǔ)

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

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

[1] 鄭元滿,姚長(zhǎng)利,張晨,等.基于等值線拓?fù)渥呦虻目焖賲^(qū)域填充算法[J].石油地球物理勘探,2010,45(6):899-908.

[2] 張登榮,劉紹華,毛天露,等.等值線自動(dòng)建立拓?fù)潢P(guān)系算法與快速填充應(yīng)用[J].中國(guó)圖象圖形學(xué)報(bào),2001,6(3):264-269.

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

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

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

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

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

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

[9] 康建榮.不規(guī)則區(qū)域等值線拓?fù)潢P(guān)系的建立及充填算法[J].測(cè)繪通報(bào),2004(9):7-9.

[10] 張道軍,李瑞雪,席振銖,等.基于逆生長(zhǎng)三角網(wǎng)的等值線圖自動(dòng)填充算法[J].地球物理學(xué)進(jìn)展,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。云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目(2013FZ 021)。楊璽，碩士生，主研領(lǐng)域：地理信息系統(tǒng)。吳晟，教授。李英娜，副教授。李川，教授。

TP391

A

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