李 強(qiáng)，李 超，甘建紅

1.成都信息工程學(xué)院 計(jì)算機(jī)學(xué)院，成都 6102252.成都信息工程學(xué)院 發(fā)展規(guī)劃處，成都 6102253.成都信息工程學(xué)院 軟件學(xué)院，成都 610225

基于三角網(wǎng)的等值線(xiàn)填充算法研究

李 強(qiáng)1，李 超2，甘建紅3

1.成都信息工程學(xué)院 計(jì)算機(jī)學(xué)院，成都 610225
2.成都信息工程學(xué)院 發(fā)展規(guī)劃處，成都 610225
3.成都信息工程學(xué)院 軟件學(xué)院，成都 610225

1 引言

等值線(xiàn)能夠以圖形的方式表示離散數(shù)據(jù)，而色斑圖則是由等值線(xiàn)輔以分層著色，以進(jìn)一步提高等值線(xiàn)圖的直觀效果。由于色斑圖（如溫度，降水色斑圖等）看起來(lái)形象直觀，它在GIS、氣象學(xué)、地質(zhì)，石油勘探等許多學(xué)科中有著廣泛的應(yīng)用。色斑圖繪制過(guò)程一般分為離散數(shù)據(jù)三角化及插值[1]，等值線(xiàn)追蹤[2-3]，等值線(xiàn)平滑[4-5]，等值線(xiàn)填充[6-11]及裁剪幾個(gè)步驟。

等值線(xiàn)填充就是根據(jù)等值線(xiàn)的拓?fù)潢P(guān)系，對(duì)等值線(xiàn)區(qū)域進(jìn)行快速、準(zhǔn)確的填充。等值線(xiàn)填充需要解決的兩個(gè)關(guān)鍵問(wèn)題是：（1）如何確定兩條相鄰等值線(xiàn)之間的區(qū)域；（2）確定這個(gè)區(qū)域應(yīng)該用何種顏色填充。在圖形學(xué)中有許多不同的算法能對(duì)等值線(xiàn)進(jìn)行填充，如格網(wǎng)法[7]、掃描線(xiàn)填充[8]、Voronoi圖環(huán)評(píng)[9]等。格網(wǎng)法需要制定基于單個(gè)三角形的填充，來(lái)拼湊任意形狀的填充，如果多邊形太復(fù)雜勢(shì)必影響效率。掃描線(xiàn)填充，對(duì)填充顏色的確定比較復(fù)雜。而Voronoi圖環(huán)評(píng)用Voronoi圖來(lái)構(gòu)建拓?fù)涠鏄?shù)，雖然算法新穎，但算法不易編程實(shí)現(xiàn)。而且這些算法對(duì)等值線(xiàn)的特點(diǎn)都沒(méi)有進(jìn)行充分利用，增加了確定填充區(qū)域的難度。本文的目的就是從等值線(xiàn)的特點(diǎn)著手，無(wú)需判斷等值線(xiàn)首尾點(diǎn)在邊界上的走向[11]，使對(duì)等值線(xiàn)拓?fù)潢P(guān)系及填充顏色的判定達(dá)到最簡(jiǎn)化，減小傳統(tǒng)算法的時(shí)間空間復(fù)雜度并結(jié)合AS3.0語(yǔ)言的特點(diǎn)提出一種可靠性高，時(shí)間復(fù)雜度小，等值線(xiàn)拓?fù)潢P(guān)系及填充顏色判定簡(jiǎn)單且適合在web環(huán)境中運(yùn)行的算法。

2 等值線(xiàn)填充算法的基本思路

本文以氣象實(shí)時(shí)業(yè)務(wù)系統(tǒng)中基于WEBGIS繪制色斑圖為研究背景，以中國(guó)氣象科學(xué)數(shù)據(jù)共享服務(wù)網(wǎng)提供的194個(gè)氣象基準(zhǔn)站的經(jīng)緯度、溫度以及全國(guó)行政邊界的shp文件為數(shù)據(jù)源。氣象實(shí)時(shí)業(yè)務(wù)的汛期（4～9月）數(shù)據(jù)訪問(wèn)集中，分析業(yè)務(wù)集中而頻繁，希望色斑圖繪制分析等業(yè)務(wù)不負(fù)載于服務(wù)器，而是使用良好的終端資源，正是基于這樣的需求，結(jié)合Flash實(shí)現(xiàn)氣象實(shí)時(shí)業(yè)務(wù)分析系統(tǒng)，其核心是要實(shí)現(xiàn)色斑圖的繪制。本文結(jié)合Flash AS3.0語(yǔ)言?xún)?yōu)勢(shì)直接在客戶(hù)端讀取shp文件，對(duì)氣象站點(diǎn)基于Delaunay快速構(gòu)建三角網(wǎng)，插值，追蹤，生成等值線(xiàn)，然后對(duì)等值線(xiàn)進(jìn)行平滑及填充，最終生成等值線(xiàn)色斑圖。

3 等值線(xiàn)精度分析

影響等值線(xiàn)的精度的因素有：離散數(shù)據(jù)網(wǎng)格化，網(wǎng)格點(diǎn)插值以及等值線(xiàn)平滑，而等值線(xiàn)填充不會(huì)影響等值線(xiàn)的精度。離散數(shù)據(jù)網(wǎng)格化可分為矩形網(wǎng)法和三角網(wǎng)法。相對(duì)于矩形網(wǎng)格，三角網(wǎng)法的特點(diǎn)[12]有：（1）三角網(wǎng)法不需要將離散點(diǎn)經(jīng)插值轉(zhuǎn)換為矩形網(wǎng)格點(diǎn)，減少了計(jì)算時(shí)間且三角形網(wǎng)格點(diǎn)數(shù)據(jù)就是離散點(diǎn)數(shù)據(jù)本身，最大程度上保留了原始數(shù)據(jù)，其精度顯然高于經(jīng)插值得到的矩形網(wǎng)格點(diǎn)精度。（2）能通過(guò)任意形狀的凸包區(qū)域生成等值線(xiàn)，而矩形網(wǎng)法的邊界則只能是矩形。（3）三角網(wǎng)法則對(duì)特征點(diǎn)部位任意小的等值線(xiàn)都能繪出，而矩形網(wǎng)格法可能會(huì)丟掉很小的閉合等值線(xiàn)。很明顯三角網(wǎng)法在精度上優(yōu)于矩形網(wǎng)法，所以本文采用已經(jīng)非常成熟的Delaunay三角形來(lái)對(duì)氣象站點(diǎn)進(jìn)行構(gòu)網(wǎng)，但是由于站點(diǎn)分布不均勻，可能會(huì)導(dǎo)致Delaunay三角網(wǎng)大小差別較大，比如產(chǎn)生狹長(zhǎng)三角形或面積較小的三角形，最終繪制出來(lái)的等值線(xiàn)精度低，可視化效果差。這時(shí)可以對(duì)初始delaunay網(wǎng)格進(jìn)行加密[13]，使其成為相對(duì)均勻分布的網(wǎng)格，并對(duì)新插入的點(diǎn)采用克里金（kriging）或者距離加權(quán)反比法（Inverse Distance Weighting，IDW）插值獲得數(shù)據(jù)值，最后繪制等值線(xiàn)，這樣繪制出來(lái)的等值線(xiàn)可靠性更高。注意由于側(cè)重點(diǎn)不一樣本文沒(méi)有對(duì)初始delaunay進(jìn)行加密，具體算法可以參考文獻(xiàn)[13]，本文主要討論等值線(xiàn)平滑對(duì)精度的損失以及等值線(xiàn)追蹤填充算法。

繪制出來(lái)的等值線(xiàn)是一條一條的折線(xiàn)，為了使等值線(xiàn)連續(xù)平滑，還需要對(duì)其進(jìn)行平滑處理。由于氣象數(shù)據(jù)是高度離散的，如果偏差一點(diǎn)，可能就會(huì)造成很大的精度損失，為了確?？臻g分析的精度，平滑過(guò)后的曲線(xiàn)應(yīng)該盡量通過(guò)原始離散點(diǎn)。常用的等值線(xiàn)平滑算法有二次、三次貝塞爾曲線(xiàn)和二次、三次B樣條曲線(xiàn)等，其中以二次B樣條曲線(xiàn)最為常用。但這些算法平滑過(guò)后的曲線(xiàn)都沒(méi)有通過(guò)原始離散點(diǎn)，對(duì)等值線(xiàn)精度造成了一定的損失。三次貝塞爾曲線(xiàn)有兩個(gè)固定點(diǎn)（起點(diǎn)和終點(diǎn)），另加兩個(gè)決定曲線(xiàn)走向的控制點(diǎn)（CP），本文采用Maxim Shemanarev提出的一種改進(jìn)的三次貝塞爾曲線(xiàn)（cubic Bezier）算法[14]（以下簡(jiǎn)稱(chēng)MS Bezier算法），使平滑過(guò)后的等值線(xiàn)仍然穿過(guò)離散點(diǎn)，如圖1所示。其大致思路就是先計(jì)算出相鄰原始點(diǎn)的中點(diǎn)，再把相鄰中點(diǎn)連接起來(lái)的線(xiàn)段平移到對(duì)應(yīng)的原始點(diǎn)，以平移后的線(xiàn)段所在直線(xiàn)上的點(diǎn)作為控制點(diǎn)，并可以使用一個(gè)與控制點(diǎn)和頂點(diǎn)距離相關(guān)的系數(shù)K，用來(lái)沿直線(xiàn)移動(dòng)控制點(diǎn)，控制點(diǎn)離頂點(diǎn)越近，拐點(diǎn)看起來(lái)就越趨于銳利。然后以相鄰原始點(diǎn)為起始點(diǎn)畫(huà)三次貝塞爾曲線(xiàn)，這樣就得到了一條穿過(guò)所有原始點(diǎn)的光滑曲線(xiàn)，減小了等值線(xiàn)平滑造成的精度損失。其最終實(shí)例效果如4.3節(jié)圖5所示。

圖1 MS Bezier與二次B樣條平滑效果示意圖

4 三角網(wǎng)構(gòu)建與等值線(xiàn)追蹤

為了便于闡述，整個(gè)算法實(shí)現(xiàn)過(guò)程的數(shù)據(jù)結(jié)構(gòu)見(jiàn)圖2。

圖2 算法數(shù)據(jù)結(jié)構(gòu)說(shuō)明

4.1 構(gòu)建三角網(wǎng)及插值

本文采用Delaunay三角形對(duì)氣象站點(diǎn)構(gòu)建三角網(wǎng)。其算法基本思路是由地圖邊界盒先初始化兩個(gè)三角形，ΔC1C4C2和ΔC2C4C3如圖3所示。然后不斷向三角網(wǎng)中添加新的點(diǎn)，在添加點(diǎn)的同時(shí)，采用Lawson提出的LOP方法對(duì)其進(jìn)行優(yōu)化，使優(yōu)化后的三角形滿(mǎn)足空外接圓，最小角最大化的屬性[1-2]。在站點(diǎn)三角化之后，在三角形的邊上進(jìn)行插值，求得等值點(diǎn)的坐標(biāo)。在所有三角形邊中找出凸包邊（此處即為C1C2，C2C3，C3C4，C4C1），其判斷標(biāo)識(shí)為該邊只被一個(gè)三角形使用。如三角形一條邊為E，則該邊為凸包邊的標(biāo)識(shí)為：E.tris.length==1。并按逆時(shí)針（或順時(shí)針）依次記錄凸包點(diǎn)（凸包邊端點(diǎn)）及凸包邊上的等值點(diǎn)（插值點(diǎn)），存入數(shù)組convexHull中，使其連接形成一個(gè)首尾閉合的凸包多邊形，如圖3所示。

圖3 站點(diǎn)三角網(wǎng)及凸包示意圖

4.2 等值線(xiàn)追蹤

等值線(xiàn)追蹤就是在已經(jīng)插值過(guò)的三角形邊上找出值相同的插值點(diǎn)，即等值點(diǎn)，然后連接成等值線(xiàn)。如圖4虛線(xiàn)部分為由氣象站點(diǎn)構(gòu)建的三角網(wǎng)，從邊AB開(kāi)始到EF結(jié)束的曲線(xiàn)為一條凸包邊封閉等值線(xiàn)（Convex Hull Closed Isoline，CHCL），而圖中較粗的環(huán)狀曲線(xiàn)則為一條自封閉等值線(xiàn)（Self Closed Isoline，SCL），為了方便后面等值線(xiàn)的填充，把CHCL和SCL區(qū)分開(kāi)，首先追蹤C(jī)HCL，然后再追蹤SCL。只要從凸包邊上某點(diǎn)開(kāi)始追蹤，那么等值線(xiàn)的尾點(diǎn)必然落在一條凸包邊上，得到的必然是一條CHCL。則遍歷convexHull數(shù)組順著凸包邊依次追蹤每一條CHCL，等值線(xiàn)追蹤算法如下：

（1）如圖4從等值點(diǎn)a開(kāi)始追蹤，首先判斷a點(diǎn)是否已經(jīng)被等值線(xiàn)穿過(guò)（a.lineThrough?=true），已穿過(guò)則跳過(guò)，否則記錄a點(diǎn)為等值線(xiàn)（a到i，記為a-i）的第一個(gè)點(diǎn)，即a-i. coords[0]=a。將a的lineThrough屬性標(biāo)識(shí)為true，并標(biāo)識(shí)currTri（當(dāng)前三角形）=T1(ΔABC)。

（2）判斷三角形T1(ΔABC)的其他兩條邊AB，AC，即lineThrough=false的兩條邊上是否有與點(diǎn)a值相同的等值點(diǎn)。

（3）通過(guò)判斷發(fā)現(xiàn)邊BC上有點(diǎn)b與點(diǎn)a值相同，記錄點(diǎn)b為等值線(xiàn)a-i的第二個(gè)點(diǎn)，即a-i.coords[1]=b。并將b 的lineThrough屬性標(biāo)識(shí)為true。

（4）判斷點(diǎn)BC是否為凸包邊即BC.tris.length是否等于1，是則終止，否則繼續(xù)。此時(shí)使用邊BC的有兩個(gè)三角形T1，T2，則currTri=[（currTri==BC.tris[0]）?1∶0]，很明顯此時(shí)currTri=T2則繼續(xù)判斷三角形T2(ΔBCD)的其他兩條邊BD，CD是否有與點(diǎn)b相同的等值點(diǎn)。

（5）重復(fù)上面三步，追蹤到凸包邊EF結(jié)束（EF.tris. length==1凸包邊一定只被一個(gè)三角形使用），這樣按順序記錄了所有等值點(diǎn)的一條CHCL就追蹤完成了。同時(shí)記錄下等值線(xiàn)a-i的isolineID為存放等值線(xiàn)的數(shù)組的當(dāng)前索引值，此處為第一條即為0。

（6）然后繼續(xù)以逆時(shí)針?lè)较蜷_(kāi)始追蹤凸包邊BE上的下一個(gè)等值點(diǎn)j，直到所有CHCL追蹤完畢，這樣就得到一個(gè)按凸包邊上等值點(diǎn)依次存放的CHCL數(shù)組：chclArr。

（7）最后遍歷非凸包邊，用同樣的算法追蹤SCL，只是SCL追蹤的結(jié)束標(biāo)識(shí)為：首尾點(diǎn)為同一個(gè)點(diǎn)，即當(dāng)lineThrough=true時(shí)，即可結(jié)束追蹤。此時(shí)又得到一個(gè)存放SCL的數(shù)組：sclArr。

圖4 CHCL和SCL等值線(xiàn)示意圖

4.3 等值線(xiàn)繪制及平滑

將追蹤得到的每條等值線(xiàn)繪制出來(lái)其實(shí)是由逐個(gè)點(diǎn)連接起來(lái)的一條折線(xiàn)，為了使后面填充的等值區(qū)域看起來(lái)連續(xù)平滑，本文采用前面提到的MS Bezier算法來(lái)對(duì)等值線(xiàn)進(jìn)行平滑，其效果如圖5所示。其中底圖為經(jīng)過(guò)MS Bezier平滑的等值線(xiàn)，兩個(gè)小方塊中折線(xiàn)為未平滑的等值線(xiàn)，平滑曲線(xiàn)分別為MS Bezier和二次B樣條平滑過(guò)后的等值線(xiàn)。

圖5 MS Bezier與二次B樣條平滑效果實(shí)例對(duì)比

5 等值線(xiàn)填充

等值線(xiàn)填充算法主要解決如何確定兩條等值線(xiàn)之間的區(qū)域，以及確定用何種顏色填充的問(wèn)題。但是由于任意兩條等值線(xiàn)之間區(qū)域的形狀是極不規(guī)則的，因此單純從確定兩條等值線(xiàn)間區(qū)域的思路出發(fā)將會(huì)使問(wèn)題變得極為復(fù)雜。先來(lái)看看等值線(xiàn)的特征與性質(zhì)：

（1）同一條等值線(xiàn)上的數(shù)值一定相等。

（2）相鄰的兩條等值線(xiàn)數(shù)值相差一個(gè)等值距，只有在凸包邊封閉等值線(xiàn)包含自封閉等值線(xiàn)時(shí)有可能相等。

（3）等值線(xiàn)可能自封閉的，也可能是凸包邊封閉的，而不封閉等值線(xiàn)的端點(diǎn)必然落在凸包邊上。

（4）等值線(xiàn)一定不會(huì)相互交錯(cuò)。

（5）對(duì)于任意連通區(qū)域來(lái)說(shuō)，圍成它的所有等值線(xiàn)值最多為2個(gè)。

（6）“大于大的，小于小的”原則：就是在兩條等值線(xiàn)a，b之間有一條子封閉等值線(xiàn)c。若c的數(shù)值與a，b中較小者相等，則c內(nèi)的數(shù)值小于c的數(shù)值。若c的數(shù)值與a，b中較大者相等，則c內(nèi)的數(shù)值大于c的數(shù)值。通過(guò)對(duì)等值線(xiàn)的特征分析，本文提出了一種快速且容易編程實(shí)現(xiàn)的算法。

5.1 凸包邊封閉等值線(xiàn)（CHCL）填充

（1）如圖6所示，若以a點(diǎn)為開(kāi)始點(diǎn)的等值線(xiàn)L為chclArr中的第一條等值線(xiàn)，則L=chclArr[a.isolineID]= chclArr[0]，從L的線(xiàn)頭（L.coords[0]）開(kāi)始，順著邊界逆時(shí)針比較凸包邊上點(diǎn)（凸包點(diǎn)及等值點(diǎn)）的X，Y值是否等于L. coords[n－1]（n=L.coords.length）的X，Y值，直到相等時(shí)結(jié)束，在convexHull中標(biāo)識(shí)L的線(xiàn)頭和線(xiàn)尾為已追蹤（convexHull[0]. isTraced=convexHull[n].isTraced=true），并標(biāo)記L的線(xiàn)尾為第一條填充等值線(xiàn)的線(xiàn)尾（convexHull[n].isFirstEndpoint= true），得到了第一個(gè)封閉區(qū)域。

（2）而該封閉區(qū)域的顏色則由逆時(shí)針順序的下一個(gè)點(diǎn)的值來(lái)確定，此處即為＜20，16＞，如果圖例從0開(kāi)始以4為間距，則該封閉區(qū)域應(yīng)該填充圖例中16～20區(qū)間的顏色。

（3）繼續(xù)從下一個(gè)點(diǎn)開(kāi)始追蹤，首先判斷點(diǎn)的isTraced屬性，若為true直接跳過(guò)，反之則繼續(xù)。此時(shí)繼續(xù)追蹤左邊值為16的等值線(xiàn)，得到第二個(gè)封閉區(qū)域，此處需要與凸包邊端點(diǎn)b進(jìn)行比較即＜16，14＞，所以給該封閉區(qū)域填充圖例中16～12區(qū)間的顏色。

（4）直到第一條填充的等值線(xiàn)L的結(jié)束點(diǎn)變成了開(kāi)始點(diǎn)，即點(diǎn)的isFirstEndpoint屬性為true，此時(shí)等值線(xiàn)（L）的下半部分的所有CHCL等值區(qū)域都已填充好，則應(yīng)順著邊界逆時(shí)針比較凸包邊上點(diǎn)的X，Y值是否等于L.coords[0]的X，Y值。只對(duì)此等值線(xiàn)進(jìn)行特殊處理，其他等值線(xiàn)都按原來(lái)的方法填充。

圖6 CHCL填充區(qū)域追蹤示意圖

具體的填充過(guò)程，如圖7。

5.2 自封閉等值線(xiàn)（SCL）填充

對(duì)于SCL需要根據(jù)等值線(xiàn)之間的包含關(guān)系以最外層的SCL為根節(jié)點(diǎn)構(gòu)造為一棵棵的拓?fù)錁?shù)，即把所有SCL轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)中的森林。首先填充外層SCL，然后依次遞歸填充其子SCL，其填充顏色由其子SCL的值來(lái)確定。具體算法實(shí)現(xiàn)如下：

圖7 CHCL的填充過(guò)程圖

（1）如圖6右下角兩條SCL，12到16之間就應(yīng)該填充圖例中12～16區(qū)間的顏色值。而值為16的SCL內(nèi)部則應(yīng)該填充圖例中16～20區(qū)間的顏色值。

（2）而對(duì)于圖4中左下角的那條SCL，它既沒(méi)有父節(jié)點(diǎn)又沒(méi)有子節(jié)點(diǎn)。雖然直觀從等值線(xiàn)圖上以“大于大的，小于小的”原則很容易判定該SCL內(nèi)部應(yīng)該填充什么顏色，但是讓程序去判斷包圍該SCL的等值線(xiàn)的拓?fù)浣Y(jié)構(gòu)是難以辦到的。通過(guò)觀察發(fā)現(xiàn)SCL內(nèi)部必然有1個(gè)或者多個(gè)三角形頂點(diǎn)，可根據(jù)其值判斷，如圖4所示。因此判斷標(biāo)準(zhǔn)如下：若E1（EC）和E2（AC）為該SCL穿過(guò)的兩條邊，P1，P2分別為其端點(diǎn)，有：

三角形頂點(diǎn)值=E1.P1.Z

三角形頂點(diǎn)值=E1.P2.Z

（3）現(xiàn)在需要解決的問(wèn)題是如何構(gòu)建這棵拓?fù)錁?shù)。根據(jù)等值線(xiàn)性質(zhì)4，等值線(xiàn)不能相互交錯(cuò)，則判斷兩條自封閉等值線(xiàn)的包含關(guān)系即可簡(jiǎn)化為，判斷某條等值線(xiàn)是否包含另一條等值線(xiàn)的任意一個(gè)點(diǎn)，即判斷點(diǎn)是否在多邊形內(nèi)。判斷點(diǎn)在多邊形內(nèi)的算法很多，如：水平交叉點(diǎn)數(shù)判別法[15]。其算法為O(N)，N為多邊形邊的數(shù)目。

（4）建立拓?fù)錁?shù)的偽代碼如下：

假如自封閉等值線(xiàn)SCL的條數(shù)為M，由于排除了不符合等值線(xiàn)間距規(guī)則的等值線(xiàn)，所以?xún)纱伪闅vclosedIsos的時(shí)間T應(yīng)該小于等于 M×M，再加上insidePolygon的時(shí)間復(fù)雜度為 O(n)，則整個(gè)算法的時(shí)間復(fù)雜度小于等于O(M×M×N)，N為多邊形邊的數(shù)目，即該等值線(xiàn)插值點(diǎn)個(gè)數(shù)。以全國(guó)194站的溫度為例，填充好的色斑圖如圖8所示。

圖8 全國(guó)194站溫度色斑圖

5.3 色斑圖裁剪

等值線(xiàn)圖繪制好后，還需要對(duì)超出地區(qū)邊界區(qū)域的部分進(jìn)行裁剪。本文使用Actionscript3.0內(nèi)置了蒙板遮罩的函數(shù)，其原理就是，遮罩層決定看到的形狀，被遮罩層決定顯示的內(nèi)容。那么可以將底圖顯示對(duì)象復(fù)制為兩份，一份用于畫(huà)等值線(xiàn)作為被遮罩層，一份用于決定顯示形狀作為遮罩層。用全國(guó)行政邊界的數(shù)據(jù)和內(nèi)置函數(shù)得到裁剪后的色斑圖如圖9所示。

圖9 溫度色斑圖裁剪前后的對(duì)比圖

6 算法效率測(cè)試

取全國(guó)194站的溫度，用AS3.0語(yǔ)言在CPU為Core 2.1 GHz，內(nèi)存1 GB的PC上實(shí)現(xiàn)了全部算法。表1中列出了本算法及近年來(lái)發(fā)表的等值線(xiàn)填充算法執(zhí)行效率比較，衡量標(biāo)準(zhǔn)為站點(diǎn)數(shù)比上運(yùn)行時(shí)間（單位：s）。

7 結(jié)論

當(dāng)前，隨著氣象探測(cè)系統(tǒng)的進(jìn)一步發(fā)展與完善，往往一個(gè)省的觀測(cè)站網(wǎng)將達(dá)到2 000～3 000個(gè)。另一方面，氣象實(shí)時(shí)分析業(yè)務(wù)所采用的硬件平臺(tái)（PC）比本文實(shí)驗(yàn)中采用的硬件平臺(tái)（見(jiàn)表1）性能要好得多，因此，利用該算法在終端處理氣象實(shí)時(shí)業(yè)務(wù)的色斑圖分析完全是可行的，從而保證實(shí)時(shí)業(yè)務(wù)的穩(wěn)定性（特別是在每年4～9月汛期）。實(shí)踐表明，該算法充分結(jié)合AS3.0語(yǔ)言的特點(diǎn)及優(yōu)勢(shì)，易于編程實(shí)現(xiàn)，等值線(xiàn)可信度高，適合在web中運(yùn)行，且運(yùn)算速度能滿(mǎn)足氣象業(yè)務(wù)需求。

表1 幾種等值線(xiàn)填充算法效率對(duì)比

[1]Bourke P.Efficient triangulation algorithm suitable for terrain modelling[C]//Pan Pacific Computer Conference.Beijing：[s.n.]，1989.

[2]郭新奇，嚴(yán)建鋼，楊士鋒，等.基于VC++的等值線(xiàn)追蹤與填充算法[J].兵工自動(dòng)化，2011，30（4）：81-84.

[3]張順謙.基于Delaunay三角網(wǎng)的區(qū)域等值線(xiàn)繪制關(guān)鍵算法[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2005，91（25）：39-41.

[4]蔣瑜，杜斌，盧軍，等.基于Delaunay三角網(wǎng)的等值線(xiàn)繪制算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（1）：102-103.

[5]Wen Yihong，Liu Yongjiang.An isoline generating algorithm based on Delaunay[C]//International Conference on Computer Engineering and Technology.Chengdu：[s.n.]，2010：173-175.

[6]黃本宇，王家華，王湘波.復(fù)雜地質(zhì)構(gòu)造的等值線(xiàn)填充及實(shí)現(xiàn)[J].阜陽(yáng)師范學(xué)院，2006，23（4）：51-52.

[7]楊清.C#實(shí)現(xiàn)基于三角網(wǎng)的等值線(xiàn)追蹤及填充算法[EB/OL]. （2010-11-29）.http：//blog.sciencenet.cn/u/moustudio.

[8]鄧飛，王美平.基于掃描線(xiàn)轉(zhuǎn)換的快速等值線(xiàn)填充算法[J].電子技術(shù)應(yīng)用，2006（3）：39-40.

[9]吳培寧，譚建榮.基于Voronoi圖的環(huán)評(píng)等值線(xiàn)快速拓?fù)涮畛鋄J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2009，43（2）：322-327.

[10]吳自銀，高金耀.一種基于格網(wǎng)的快速等值線(xiàn)充填算法[J].測(cè)繪學(xué)報(bào)，1999，28（4）：351-354.

[11]湯子?xùn)|，鄭明璽，王思群.一種基于三角網(wǎng)的等值線(xiàn)自動(dòng)填充算法[J].中國(guó)圖象圖形學(xué)報(bào)，2009，14（12）：2578-2581.

[12]巫昌海.提高三角網(wǎng)法繪制等值線(xiàn)精度的算法[J].武測(cè)科技，1993（2）：10-12.

[13]胡金虎.基于不規(guī)則三角網(wǎng)的高精度等值線(xiàn)生成方法[J].工程勘測(cè)，2011（2）：64-68.

[14]Interpolation with Bezier a very simple method of smoothing polygons[EB/OL].（2006-08-16）.http：//www.antigrain.com/research/bezier_interpolation/index.html.

[15]Bourke P.Determining if a point lies on the interior of a polygon[EB/OL].（2010-12-05）.http：//paulbourke.net/geometry/ insidepoly/.

LI Qiang1,LI Chao2,GAN Jianhong3

1.College of Computer Science and Technology,Chengdu University of Information and Technology,Chengdu 610225,China
2.Development and Planning Department,Chengdu University of Information and Technology,Chengdu 610225,China
3.College of Software,Chengdu University of Information and Technology,Chengdu 610225,China

With deep research on isoline filling algorithm,a new cover algorithm of isoline filling is proposed in this paper.This algorithm classifies isolines as Convex Hull Closed Isoline（CHCL）and Self Closed Isoline（SCL）.Taking full advantage of isoline's characteristic,the judgement of topological relation and filling color is simplified mostly.For CHCL isoline,tracing convex hull isoline-points and convex points are employed to determine filling area,and a multi-branches tree which is established by topological relation is adopted to determine the order of filling for SCL isoline.By repeating cover filling isoline-area orderly,all the isoline-area filling is accomplished.For smoothing isoline,a new method which can decrease the precision loss of isoline smoothing is adopted.Algorithm model is realized using client side programming language-ActionScript3.0,and it shows that this algorithm is easy to implement and the time cost can satisfy the business demands.

Delaunay triangle mesh;isoline tracing;isoline filling;contour plot

通過(guò)對(duì)現(xiàn)有等值線(xiàn)填充算法的深入研究，提出了一種覆蓋填充等值線(xiàn)的算法。該算法把等值線(xiàn)分類(lèi)為凸包邊封閉等值線(xiàn)（CHCL）和自封閉等值線(xiàn)（SCL），充分利用等值線(xiàn)的特點(diǎn)，使對(duì)等值線(xiàn)拓?fù)潢P(guān)系及填充顏色的判定達(dá)到最簡(jiǎn)化。對(duì)于CHCL采用對(duì)凸包邊等值點(diǎn)及凸包點(diǎn)追蹤來(lái)確定填充區(qū)域，對(duì)于SCL則根據(jù)拓?fù)潢P(guān)系以最外層的SCL為根節(jié)點(diǎn)構(gòu)建一棵多叉樹(shù)以確定填充順序.通過(guò)對(duì)等值區(qū)域依次反復(fù)覆蓋填充，最終完成所有等值線(xiàn)的填充。采用了一種穿過(guò)原始離散點(diǎn)平滑等值線(xiàn)的算法，減小了等值線(xiàn)平滑造成的精度損失。并運(yùn)用客戶(hù)端語(yǔ)言AS3.0（ActionScript3.0）實(shí)現(xiàn)了算法模型。實(shí)驗(yàn)結(jié)果表明，該算法簡(jiǎn)單易于實(shí)現(xiàn)，而且運(yùn)算速度能滿(mǎn)足業(yè)務(wù)需要。

Delaunay三角網(wǎng)；等值線(xiàn)追蹤；等值線(xiàn)填充；色斑圖

A

TP391.7

10.3778/j.issn.1002-8331.1203-0485

LI Qiang,LI Chao,GAN Jianhong.Study on algorithm of isoline filling based on triangle mesh.Computer Engineering and Applications,2013,49（5）：185-189.

成都信息工程學(xué)院人才引進(jìn)項(xiàng)目（No.KYTZ201040）。

李強(qiáng)（1986—），男，碩士，主要研究方向?yàn)閃EBGIS空間數(shù)據(jù)分析及WEB3D；李超（1964—），男，教授，主要研究方向?yàn)榛诰W(wǎng)絡(luò)的計(jì)算機(jī)應(yīng)用技術(shù)；甘建紅（1978—），男，博士，主要研究方向?yàn)閿?shù)字圖像處理。E-mail：lqlunwen@126.com

2012-03-21

2012-07-03

1002-8331（2013）05-0185-05