一種基于網(wǎng)格重心的等值線追蹤算法

王俊驕 陳 晴 張姍姍

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

0 引 言

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

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

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

1 等值線的原理及算法

對(duì)于標(biāo)準(zhǔn)網(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文件獲取。

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

1.1 等值點(diǎn)的判斷

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

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

(1)

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

(2)

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

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

(3)

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

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

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

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

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

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

圖1 傳統(tǒng)追蹤示意圖(括號(hào)中代表該點(diǎn)高程值)

2 本文算法

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

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

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

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

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

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

2.2 算法

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

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

圖3 本文算法的流程框圖

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

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

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

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

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

4 結(jié) 語

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

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

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

[2] 余衛(wèi)東,李湘閣,王靖.氣象場(chǎng)等值線自動(dòng)繪制[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].東華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005,31(4):66-69.

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

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

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

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

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

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