一種改進(jìn)的局部多邊形填充方法

2011-03-14 00:39許少華

黑龍江科學(xué) 2011年1期

許少華，李偉

（東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院黑龍江大慶163318）

等值線圖是一種離散數(shù)據(jù)的圖形表示方法，在水利、土木、地質(zhì)、石油勘探等工程和技術(shù)領(lǐng)域內(nèi)廣泛應(yīng)用，已成為各研究領(lǐng)域的研究人員進(jìn)行分析研究不可缺少的圖件之一。等值帶的填充就是用不同的顏色填充不同等值線圍成的區(qū)域，使等值線圖更直觀反映二維數(shù)據(jù)特征，且美觀清晰。在油田勘探開(kāi)發(fā)和生產(chǎn)過(guò)程中，等值線圖可以用來(lái)推斷地質(zhì)構(gòu)造和地質(zhì)分布參數(shù)，從而認(rèn)識(shí)油氣富集特征；也可直觀的顯示產(chǎn)油、含水等生產(chǎn)指標(biāo)的分布情況，為油田生產(chǎn)方案調(diào)整提供依據(jù)。在傳統(tǒng)的開(kāi)發(fā)過(guò)程中，石油工程師一般根據(jù)現(xiàn)場(chǎng)測(cè)量數(shù)據(jù)進(jìn)行手工繪制，不僅費(fèi)時(shí)費(fèi)力而且誤差較大。隨著計(jì)算機(jī)軟硬件的發(fā)展，用于顯示和繪制等值線圖等其他地質(zhì)圖件的軟件已被廣泛用于石油勘探開(kāi)發(fā)，為等值線繪制提供了很大的便利。但從模型和算法上改進(jìn)相應(yīng)的軟件系統(tǒng)，提高繪圖質(zhì)量，還是十分必要的。

國(guó)內(nèi)外對(duì)等值線的繪制已經(jīng)有很多成熟的算法和軟件，而對(duì)等值帶填充的研究則相對(duì)較少。目前填充算法主要有：種子法、柵格法、拓?fù)涮畛?、邊界掃描等[1-4]。歸納起來(lái)可以分為兩類(lèi)：一類(lèi)是先利用網(wǎng)格數(shù)據(jù)追蹤等值線（等值帶的邊界），然后搜索連通區(qū)域進(jìn)行填充；一類(lèi)是根據(jù)網(wǎng)格化以后的數(shù)據(jù)，進(jìn)行平面插值，使得繪圖區(qū)域中當(dāng)前設(shè)備分辨率下的每一個(gè)繪圖像素點(diǎn)都有一個(gè)數(shù)據(jù)值，然后根據(jù)這個(gè)值給其所在的像素填上相應(yīng)的顏色。第一類(lèi)方法需要經(jīng)過(guò)追蹤和搜索兩個(gè)步驟，算法復(fù)雜，實(shí)現(xiàn)困難；第二類(lèi)方法實(shí)現(xiàn)簡(jiǎn)單但計(jì)算量跟繪圖區(qū)域大小成正比。

龐世明等人提出一種局部多邊形填充算法[5]，其基本思想:是在每一個(gè)小矩形中按照填充顏色的級(jí)別將網(wǎng)格矩形分割為多個(gè)多邊形，然后用相應(yīng)的顏色進(jìn)行填充，再進(jìn)行網(wǎng)格范圍的循環(huán)完成整個(gè)區(qū)域的填充。該算法的優(yōu)點(diǎn)是不需要進(jìn)行等值線的追蹤，編程容易實(shí)現(xiàn)，計(jì)算量也較小。但是算法在搜索多邊形時(shí)有以下不足：根據(jù)網(wǎng)格矩形各邊等值點(diǎn)個(gè)數(shù)需要討論多達(dá)12種情況，太過(guò)繁瑣。

針對(duì)上述問(wèn)題,本文提出一種改進(jìn)的局部多邊形填充方法。算法和龐世明等人提出的局部多邊形填充算法類(lèi)似，不需要進(jìn)行等值線的追蹤，將討論情況精簡(jiǎn)為兩種；且在多邊形填充中時(shí)使用了凸包算法確定頂點(diǎn)的順序，所以在搜索多邊形時(shí)不用考慮點(diǎn)的空間位置，只需考慮各點(diǎn)對(duì)應(yīng)的高程值。

1 算法實(shí)現(xiàn)

1.1 算法原理

首先通過(guò)插值算法，將離散數(shù)據(jù)網(wǎng)格化，得到網(wǎng)格各頂點(diǎn)處的坐標(biāo)和高程值信息，然后逐一遍歷每一個(gè)小矩形，在這些小矩形中按照填充顏色的級(jí)別計(jì)算等值點(diǎn)，找出其包含的多邊形，最后用相應(yīng)的顏色進(jìn)行填充。

在搜索多邊形時(shí)，首先計(jì)算出網(wǎng)格各邊的等值點(diǎn)。因?yàn)椴煌叱讨档牡戎稻€必不相交[6]，并且一條等值線與矩形邊的交點(diǎn)個(gè)數(shù)只有0、2、4三種情況，所以算法根據(jù)矩形網(wǎng)格中是否有一組或多組等值點(diǎn)的個(gè)數(shù)為4，分為兩種情況討論。如圖1共有兩組等值點(diǎn)，分別為EH和FG。圖2也有兩組等值點(diǎn)，EJ和FGHI，其中有第二組等值點(diǎn)個(gè)數(shù)為4，這種情況需特殊處理。由于插值算法，則等值點(diǎn)的權(quán)重同時(shí)也蘊(yùn)含著與頂點(diǎn)間的距離，所以接著講頂點(diǎn)和等值點(diǎn)按權(quán)重排序，然后按照一定規(guī)律即可將網(wǎng)格分割成多個(gè)多邊形。

填充時(shí)，填充函數(shù)接收到的數(shù)組頂點(diǎn)是按照權(quán)重值排序的而不是二維平面內(nèi)的坐標(biāo)關(guān)系，因此若要填充多邊形，還需要將這些頂點(diǎn)按照坐標(biāo)關(guān)系按順時(shí)針或者逆時(shí)針排序。這里應(yīng)用二維凸包Graham算法來(lái)解決。Graham算法的描述：如果S為平面內(nèi)的點(diǎn)的集合，Graham掃描算法從S中找出有最小的y坐標(biāo)的點(diǎn)p（通過(guò)選出最左邊的點(diǎn)打破平局）。然后根據(jù)點(diǎn)和p連線和正X軸所成的角度將S中的點(diǎn)排序[7]。詳細(xì)實(shí)現(xiàn)過(guò)程這里不再贅述。填充顏色由多邊形各個(gè)頂點(diǎn)高程值的平均在所在的顏色確定。

圖-1等值點(diǎn)情況1Fig.1 Situation 1 of equivalent point

圖-2等值線情況2Fig.2 Situation 2 of equivalent point

1.2 算法步驟

為實(shí)現(xiàn)算法，首先定義三個(gè)數(shù)組：AllFaces記錄所有的網(wǎng)格矩形；AllPoints記錄所有網(wǎng)格頂點(diǎn)；Found-Points記錄每個(gè)網(wǎng)格中參與搜索多邊形的點(diǎn)。兩個(gè)類(lèi)：ContourPoint類(lèi)有3個(gè)屬性，記錄X,Y坐標(biāo)和W（高程值）用于描述各矩形頂點(diǎn)和等值點(diǎn)；CountFace類(lèi)有四個(gè)屬性，記錄一個(gè)矩形的四個(gè)頂點(diǎn)在AllPoints中的序號(hào)。

算法步驟如下：

Step 1：從AllFaces數(shù)組中取出一個(gè)元素。GOTO Step2。

Step 2：IF遍歷結(jié)束

THEN退出程序；ELSE GOTOStep 3；

Step 3：清空FoundPoints數(shù)組。取出網(wǎng)格矩形四個(gè)頂點(diǎn)，根據(jù)級(jí)別定義，按順時(shí)針從AB到DA（如圖1）的順序搜索各邊上的等值點(diǎn)，并將頂點(diǎn)和等值點(diǎn)依次放入FoundPoints中。GOTOStep 4；

Step 4：IF FoundPoints長(zhǎng)度大于4 THENGOTOSTEP 5；

ELSE將數(shù)組傳遞給填充函數(shù)；GOTO STEP 3；

Step 5：對(duì)FoundPoints按點(diǎn)高程值進(jìn)行插入排序。定義整形i=0,記錄當(dāng)前點(diǎn)在數(shù)組的位置GOTO Step 6；

Step 6：添加FoundPoints[i]到臨時(shí)數(shù)組中，定義TempW記錄其高程值。GOTOStep 7；

Step 7：定義j=i+1；IF FoundPoints[j].W！=TempW THENGOTOStep 17；ELSE GOTOStep 8；

Step 8：定義k=j+1;添加FoundPoints[k]到臨時(shí)數(shù)組中；

IF FoundPoints[k].W==TempW THENGOTOStep 9；ELSE GOTOStep 8；

Step 9：將FoundPoints[k+1]放入臨時(shí)數(shù)組傳給填充函數(shù)；并將FoundPoints中k-3之后的所有元素放入NewFoundPoints；將這四個(gè)相同高程值的等值點(diǎn)記錄在temp數(shù)組中錄；定義flag=0，記錄是否出現(xiàn)新的一對(duì)等值點(diǎn)。GOTOStep 10；

Step 10：將temp數(shù)組的元素加入臨時(shí)數(shù)組中，定義m=4，記錄當(dāng)前點(diǎn)在NewFoundPoints的位置；GOTO Step 11；

Step 11：添加NewFoundPoints[m]到臨時(shí)數(shù)組，定義TempW記其高程值。GOTOStep 12；

Step 12：定義n=m+1；IF NewFoundPoints[n].W== TempW

Step 13:flag=1;將臨時(shí)數(shù)組傳遞給填充函數(shù)后清空。添加NewFoundPoints[n-1]到臨時(shí)數(shù)組；m=n；GOTOStep 16；

Step 14：IF flag=0

THENGOTOStep15；

Step 15：將臨時(shí)數(shù)組傳遞給填充函數(shù)后清空后添加temp數(shù)組的元素；GOTOStep16；

Step 16：IF NewFoundPoints[m]是最后一個(gè)元素

THEN將其添加對(duì)臨時(shí)數(shù)組；傳遞給填充函數(shù)；退出程序；

ELSE GOTOStep 11；

Step 17：IF FoundPoints[i]是最后一個(gè)元素

THEN將其添加對(duì)臨時(shí)數(shù)組；傳遞給填充函數(shù)；退出程序；

ELSE GOTOStep 6；

如圖1的情況，排序后的點(diǎn)位AEHBDFGC,先后傳遞給繪圖函數(shù)的點(diǎn)數(shù)組AEH、EFBDFG，F(xiàn)GC；如圖2的情況，排序后點(diǎn)依次為AEJFGHIBDC（也可能是AEJFGHIDBC）。傳遞給填充函數(shù)的點(diǎn)依次為AEJ，EJFGHI然后進(jìn)行特殊處理時(shí)傳遞給填充函數(shù)的點(diǎn)為FGHIB，F(xiàn)GHID，F(xiàn)GHIC。

2 實(shí) 例

筆者將算法應(yīng)用油田含水飽和度等動(dòng)態(tài)指標(biāo)圖中，網(wǎng)格數(shù)據(jù)比較平滑，在網(wǎng)格粗糙的情況下也具有較好的效果。如圖3中等值帶個(gè)數(shù)為5，網(wǎng)格密度分別為10*10和20*20以及網(wǎng)格密度為20*20等值帶個(gè)數(shù)分別為10和20作為條件進(jìn)行了測(cè)試，計(jì)算速度都很快。而且隨著網(wǎng)格密度和等值帶個(gè)數(shù)的增加，算法效果越好。

圖3 算法效果Fig.3 Effects of algorithm

3 結(jié) 論

（1）提出了一種新的方法解決常規(guī)的繪制彩色填充等值帶問(wèn)題,該方法不需要在網(wǎng)格化數(shù)據(jù)的基礎(chǔ)上進(jìn)行等值線追蹤,具有編程簡(jiǎn)單、計(jì)算量小的特點(diǎn)。

（2）本算法不需要討論過(guò)多的種類(lèi)，只需要特別處理具有相同權(quán)重的等值點(diǎn)為4的情況。

（3）本算法采用的四邊形網(wǎng)格，但因?yàn)樗惴ㄔ趯ふ叶噙呅螘r(shí)是按各點(diǎn)權(quán)重排序，而跟坐標(biāo)無(wú)關(guān)。所以可以方便地推廣三角形構(gòu)網(wǎng)的等值帶填充中。

（4）本算法已在程序系統(tǒng)中得到很好的應(yīng)用,速度快，效果良好。

[1]徐勝利.一種堆棧式快速等值線圖填充算法[J].計(jì)算機(jī)工程與應(yīng)用，2010,46(8):193～195.

[2]吳自銀,高金耀.一種基于格網(wǎng)的快速等值線充填算法[J].測(cè)繪學(xué)報(bào)，1999,28(4):350～354.

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

[4]成建梅，陳崇希，孫紅林.三角網(wǎng)格等值線自動(dòng)生成方法及程序?qū)崿F(xiàn)[J].水利學(xué)報(bào)，1998，29(10):23～26.

[5]龐世明,蔡玉華,靳文芳.等值線圖的彩色填充方法[J].計(jì)算機(jī)應(yīng)用，2004(1)：60～62.

[6] Kantz H,Schreiber T.Nonlinear time series analysis[M].Beijing：Tsinghua UniversityPress，2000：42～47.