一種改進的局部多邊形填充方法

許少華， 李 偉

（東北石油大學計算機與信息技術學院黑龍江大慶163318）

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

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

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

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

1 算法實現

1.1 算法原理

首先通過插值算法，將離散數據網格化，得到網格各頂點處的坐標和高程值信息，然后逐一遍歷每一個小矩形，在這些小矩形中按照填充顏色的級別計算等值點，找出其包含的多邊形，最后用相應的顏色進行填充。

在搜索多邊形時，首先計算出網格各邊的等值點。因為不同高程值的等值線必不相交[6]，并且一條等值線與矩形邊的交點個數只有0、2、4三種情況，所以算法根據矩形網格中是否有一組或多組等值點的個數為4，分為兩種情況討論。如圖1共有兩組等值點，分別為EH和FG。圖2也有兩組等值點，EJ和FGHI，其中有第二組等值點個數為4，這種情況需特殊處理。由于插值算法，則等值點的權重同時也蘊含著與頂點間的距離，所以接著講頂點和等值點按權重排序，然后按照一定規律即可將網格分割成多個多邊形。

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

圖-1等值點情況1Fig.1 Situation 1 of equivalent point

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

1.2 算法步驟

為實現算法，首先定義三個數組：AllFaces記錄所有的網格矩形；AllPoints記錄所有網格頂點；Found-Points記錄每個網格中參與搜索多邊形的點。兩個類：ContourPoint類有3個屬性，記錄X,Y坐標和W（高程值）用于描述各矩形頂點和等值點；CountFace類有四個屬性，記錄一個矩形的四個頂點在AllPoints中的序號。

算法步驟如下：

Step 1：從AllFaces數組中取出一個元素。GOTO Step2。

Step 2：IF遍歷結束

THEN退出程序；ELSE GOTOStep 3；

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

Step 4：IF FoundPoints長度大于4 THENGOTOSTEP 5；

ELSE將數組傳遞給填充函數；GOTO STEP 3；

Step 5：對FoundPoints按點高程值進行插入排序。定義整形i=0,記錄當前點在數組的位置GOTO Step 6；

Step 6：添加FoundPoints[i]到臨時數組中，定義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]到臨時數組中；

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

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

Step 10：將temp數組的元素加入臨時數組中，定義m=4，記錄當前點在NewFoundPoints的位置；GOTO Step 11；

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

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

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

Step 14：IF flag=0

THENGOTOStep15；

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

Step 16：IF NewFoundPoints[m]是最后一個元素

THEN將其添加對臨時數組；傳遞給填充函數；退出程序；

ELSE GOTOStep 11；

Step 17：IF FoundPoints[i]是最后一個元素

THEN將其添加對臨時數組；傳遞給填充函數；退出程序；

ELSE GOTOStep 6；

如圖1的情況，排序后的點位AEHBDFGC,先后傳遞給繪圖函數的點數組AEH、EFBDFG，FGC；如圖2的情況，排序后點依次為AEJFGHIBDC（也可能是AEJFGHIDBC）。傳遞給填充函數的點依次為AEJ，EJFGHI然后進行特殊處理時傳遞給填充函數的點為FGHIB，FGHID，FGHIC。

2 實 例

筆者將算法應用油田含水飽和度等動態指標圖中，網格數據比較平滑，在網格粗糙的情況下也具有較好的效果。如圖3中等值帶個數為5，網格密度分別為10*10和20*20以及網格密度為20*20等值帶個數分別為10和20作為條件進行了測試，計算速度都很快。而且隨著網格密度和等值帶個數的增加，算法效果越好。

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

3 結 論

（1）提出了一種新的方法解決常規的繪制彩色填充等值帶問題,該方法不需要在網格化數據的基礎上進行等值線追蹤,具有編程簡單、計算量小的特點。

（2）本算法不需要討論過多的種類，只需要特別處理具有相同權重的等值點為4的情況。

（3）本算法采用的四邊形網格，但因為算法在尋找多邊形時是按各點權重排序，而跟坐標無關。所以可以方便地推廣三角形構網的等值帶填充中。

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

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

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

[3]張登榮，劉紹華，毛天露等.等值線自動建立拓撲關系算法與快速填充應用[J].中國圖象圖形學報，2001.6A(3)：264～269.

[4]成建梅，陳崇希，孫紅林.三角網格等值線自動生成方法及程序實現[J].水利學報，1998，29(10):23～26.

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

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

[7]鄭宗漢,鄭曉明.算法設計與分析[M].清華大學出版社.北京2010：278～285.