王俊驕 陳 晴 張姍姍

(1.杭州市氣象局，浙江 杭州 310008;2.浙江省氣象信息網(wǎng)絡(luò)中心，浙江 杭州 310017)

0 引 言

在氣象要素圖形顯示中經(jīng)常用到等值線圖，它能較直觀地給出氣象要素的分布情況。不管是網(wǎng)格化的數(shù)值預(yù)報產(chǎn)品分析，還是在離散站點數(shù)據(jù)網(wǎng)格化應(yīng)用中，等值線圖的應(yīng)用都非常廣泛。等值線圖是以相等數(shù)值點的連線表示連續(xù)分布且逐漸變化數(shù)量特征的一種圖型，等值線生成常用算法有標準網(wǎng)格法和三角網(wǎng)格法兩種[1]。而標準網(wǎng)格法利用區(qū)域內(nèi)的高程離散點,建立逼近的曲面模型,然后通過內(nèi)插得到一組規(guī)則的矩形網(wǎng)格數(shù)據(jù),再在矩形網(wǎng)格的基礎(chǔ)上線性插值追蹤得到各條等值線。

目前，國內(nèi)對標準網(wǎng)格等值線追蹤的算法很多，如按一定方向直接對每個網(wǎng)格各邊的等值點進行等值線追蹤[2]、通過對角線轉(zhuǎn)軸法進行追蹤[3]、利用數(shù)據(jù)關(guān)聯(lián)表生成矩形網(wǎng)格等值線[4]等等，對追蹤出來的等值線再用一些插值擬合方法進行平滑處理,如Bezier、B樣條擬合等[5]，或為了使等值線圖更直觀,還需要對等值線進行顏色填充[7]。

以上等值線追蹤算法的設(shè)計均旨在提高整體的搜索效率，提升速度，在搜索過程中只考慮小網(wǎng)格的進邊和出邊，未分析等值線在小網(wǎng)格內(nèi)的走向，在小網(wǎng)格尺寸很大時尤其明顯。因此，本文提出一種基于網(wǎng)格重心的等值線追蹤算法，在等值線追蹤過程中，引入重心點分析每個網(wǎng)格，通過增加等值點序列中點的數(shù)量，不僅可更真實地反應(yīng)等值線整體逐漸變化的特征，而且為后續(xù)的等值線光滑提供更多的控制點，同時由于本文算法在判斷出邊時僅需通過重心判斷，避免了網(wǎng)格出口邊判斷復雜的問題。

1 等值線的原理及算法

對于標準網(wǎng)格的等值線生成，首先需獲得網(wǎng)格數(shù)據(jù)，在氣象應(yīng)用中，網(wǎng)格數(shù)據(jù)一般通過內(nèi)插方法將離散數(shù)據(jù)轉(zhuǎn)換成網(wǎng)格數(shù)據(jù)，也可從氣象應(yīng)用中常用的Micaps四類格式、Grib格式和Netcdf文件獲取。

在整個大網(wǎng)格中，分析每個小網(wǎng)格獲取等值點，再判斷走向，將它們依次用線連接起來，最后光滑等值線，從而構(gòu)成等值線。本文重點討論分析網(wǎng)格數(shù)據(jù)等值線追蹤[8]。

1.1 等值點的判斷

在幾何中，對于由點A和點B構(gòu)成的一條邊AB，其中XA，YA分別表示點A的橫坐標和縱坐標，XB，YB分別表示點B的橫坐標和縱坐標，VA，VB分別代表點A和點B的高程值。判斷在該邊上是否存在滿足高程值為W的等值點R的條件如下：

(VA-W)(VB-W)<0

(1)

若邊AB滿足(1)式，則通過內(nèi)插可知等值點R的橫坐標XR和縱坐標YR：

(2)

假設(shè)規(guī)則網(wǎng)格是由m×n個網(wǎng)格數(shù)據(jù)點構(gòu)成,用Di,j表示縱向第i行，橫向第j列的網(wǎng)格點，則用Vi,j表示該點的高程值，Di,jDi,j+1表示由點Di,j和Di,j+1所構(gòu)成的橫向邊，Di,jDi+1,j表示由點Di,j和Di+1,j所構(gòu)成的縱向邊，其中1≤i≤m，1≤j≤n。

定義1對于任意一條邊Di,jDi+1,j，若滿足(1)式，則邊Di,jDi+1,j定義為等值邊，而等值點R的橫向位置x和縱向位置y：

(3)

同理對于任意一條橫邊Di,jDi,j+1為等值邊，可得到等值點相應(yīng)的位置。

定理1由等值點的滿足條件(1)式可知，在任意一個小網(wǎng)格中，若某邊為等值邊，即存在等值點，則該網(wǎng)格的另外3條邊中至少有1條邊同時為等值邊。

另外，在網(wǎng)格數(shù)據(jù)等值線追蹤過程中，須對每次搜索到的等值點進行判別，分析該點是否為終點，以停止搜索。而根據(jù)等值線特性可知，在搜索某高程值等值線時，終點需滿足以下條件：該點為邊界上的點或者該點為搜索起始點。

1.2 傳統(tǒng)網(wǎng)格追蹤

一條等值線的傳統(tǒng)追蹤算法描述如下：首先，依照自上而下，自左向右的順序搜索每個小網(wǎng)格，將第一個找到等值邊上的等值點作為搜索起始點，以該等值邊為進邊分析該網(wǎng)格，計算該網(wǎng)格上另外一個等值點和相應(yīng)的等值邊，連接兩個等值點，即完成第一個網(wǎng)格的追蹤。然后，以新的等值邊作為進邊，得到下一個網(wǎng)格，依此類推，直至等值點為終點。

然而，在傳統(tǒng)追蹤過程中，當網(wǎng)格內(nèi)不止存在一條出邊時(見圖1)，就需判斷等值線的走向。不僅降低了追蹤的效率，而且可能由于不同的判斷方法導致產(chǎn)生不同的等值線。當網(wǎng)格尺寸較大時，雖然能加快等值線搜索速度，但無法更真實地反映網(wǎng)格內(nèi)部和整體的變化特征。

圖1 傳統(tǒng)追蹤示意圖(括號中代表該點高程值)

2 本文算法

2.1 基于小網(wǎng)格重心的追蹤

本文在傳統(tǒng)的追蹤算法基礎(chǔ)上，提出利用網(wǎng)格的重心來控制等值線的走向，通過重心引導，避免了等值線走向問題，同時使等值線在網(wǎng)格內(nèi)的走向更符合等值線的實際特征(見圖2中b，c，d)。

圖2 等值點追蹤時小網(wǎng)格內(nèi)部的走向

在一個小網(wǎng)格中，已知四個點A,B,C,D，括號內(nèi)為該點的高程值。則重心點E的橫坐標Ex、縱坐標Ey和高程值VE為：

基于小網(wǎng)格重心的追蹤算法可描述為：當某一邊進入小網(wǎng)格時，分析以該網(wǎng)格重心與進入邊構(gòu)成的三角形。由于在該三角形中另外兩條邊中有且僅有一條為等值邊，則找到該等值邊及相應(yīng)的等值點。繼續(xù)分析下一個三角形，直到找到的等值點在該網(wǎng)格的四條邊上，即結(jié)束該小網(wǎng)格的搜索。一般該追蹤算法可出現(xiàn)圖2中b，c，d 3種情況。

以圖2中的c為例，追蹤高程值為5的等值線。首先得到網(wǎng)格ABCD的重心E，以邊AB作為進入邊，則分析三角形ABE得到新的等值邊AE，由于AE不是網(wǎng)格的邊，則繼續(xù)分析三角形AED，CDE，直到找到網(wǎng)格的出邊CD，才完成整個小網(wǎng)格的追蹤。在該網(wǎng)格的追蹤中，共增加了2個新點，將這2個點存入到整條等值線點的序列中，可為后續(xù)的光滑，增加新控制點。

2.2 算法

等值線追蹤到的所有等值點坐標按順序連接就形成了等值線。然而該線條為一條折線，故需對這些等值點進行曲線平滑處理，將處理后的坐標連接起來即可繪出連續(xù)平滑曲線。曲線平滑常用的方法有Bezier方法、B樣條方法、三次樣條方法及最小二乘法，同時對等值線進行填充顏色，邊界裁剪等后續(xù)加工處理。

為避免在追蹤過程中，對某些等值點重復追蹤，造成算法冗余，在追蹤順序時，本文先依序搜索網(wǎng)格最外面4條邊，根據(jù)等值線要么自封閉,要么邊界封閉的特性，先將邊界封閉的等值線追蹤完畢，再追蹤自封閉的等值線。因此，本文的算法流程圖如下。

圖3 本文算法的流程框圖

3 本文算法的應(yīng)用

為驗證本文算法的可用性，選取2016年4月5日08時歐洲中心細網(wǎng)格的小時降水預(yù)報，在數(shù)值預(yù)報中繪制高程值為8的等值線，為能清楚地展示網(wǎng)格內(nèi)部等值線追蹤的效果，截取了中心10×10網(wǎng)格數(shù)據(jù),用于展示等值線追逐效果，并通過傳統(tǒng)和本文的算法進行比較(結(jié)果見圖4和圖5)。

圖4 傳統(tǒng)追蹤的示范圖

圖5 本文基于重心追蹤的示范圖

由圖4和圖5可知：采用傳統(tǒng)的追蹤算法比基于重心追蹤的等值點少，所以等值線會相對比較粗糙，基于重心的追蹤法更能反映等值線在小網(wǎng)格內(nèi)的走向。傳統(tǒng)的追蹤方法因為需對網(wǎng)格出口邊判斷，從而導致整體生成的等值線會不同，而等于重心追蹤在小網(wǎng)格中不涉及出口邊判斷問題，確保了等值線的唯一性，可以應(yīng)用到實際業(yè)務(wù)中。

4 結(jié) 語

本文在分析傳統(tǒng)矩形網(wǎng)格等值線追蹤算法的基礎(chǔ)上,引入小網(wǎng)格重心的算法加以改進,實現(xiàn)尋點與追蹤同步。與傳統(tǒng)方法比較,本文的方法有以下改進：1)可更真實地反應(yīng)等值線整體逐漸變化的特征；2)在等值線點序列中增加了節(jié)點，為后續(xù)的等值線光滑提供更多的控制點；3)在追蹤過程中，不涉及出口邊判斷問題，確保了等值線的唯一性；4)可利用同樣原理擴展到三角網(wǎng)格的等值線追蹤中。

本文算法通過編碼，已成功應(yīng)用到氣象數(shù)值預(yù)報產(chǎn)品、Micaps四類格式的資料處理中，并應(yīng)用到實際業(yè)務(wù)中。

[1] 林毅,金燁，馬登哲等.正規(guī)網(wǎng)格等值線的虛路徑掃描算法[J].計算機工程及應(yīng)用，2001,37(13):92-94.

[2] 余衛(wèi)東,李湘閣,王靖.氣象場等值線自動繪制[J].氣象科技，2002,30(4):222-225.

[3] Dayhoff M O. A contour map program for X-ray crystallogra-phy[J]. Co mmunications of the Association for Computing Machinery,1963,6(10):620-62.

[4] 孫科峰,孫根正,李潔.一種新的矩形網(wǎng)格生成等值線算法[J].東華大學學報(自然科學版)，2005,31(4):66-69.

[5] 韓麗娜,張紅祥,張群會.Bezier曲線修改的一種分割算法[J].計算機工程與科學，2006(7):77-79.

[6] 韓家新,王家華.一種等值線填充的連通區(qū)域搜索算法[J].計算機應(yīng)用與軟件，2003(10)：5-6.

[7] 陳正旭,封秀燕,王亞云.多島嶼地圖上繪制氣象要素等值線色塊的自適應(yīng)方法[J].氣象科技，2009,37(3):356-359.

[8] 王亞強.等值線相關(guān)算法類庫的開發(fā)與應(yīng)用[J].氣象科技，2010(4):478-482.

[9] 張紅祥,車鵬飛.一種多段Bezier曲線光順擬合方法[J].科技信息,2008(13):48-49.

[10] 孫桂茹,馬亮,路登平等.等值線生成與圖形填充算法[J].天津大學學報,2000,33(6):816-818.