基于規則三角網的等值線追蹤與填充算法的實現和應用

廖國忠，張 偉，梁生賢，吳文賢，李 富

（中國地質調查局 成都地質調查中心，成都 610081）

0 引言

隨著地質科學的發展，等值線圖在礦產普查與勘探中的作用越來越大。等值線研究是科學計算可視化的一個基礎而重要的內容，等值線圖在物化探的信息提取、礦產勘查的定量化計算中發揮著重大作用［1－5］。

當前最常見的等值線追蹤算法是基于規則矩形網格，以規則矩形網格為最小單元，連接網格邊上的交點來實現［6－10］，但是當一個四邊形中的交點達到四個時，這種算法將為等值線追蹤帶來不確定性（圖1（b））。因此作者在此算法上進行了修改，將網格四邊形劃分為上、下兩個三角形，一個三角形中要么有兩個交點，要么沒有交點，連接兩個交點便確定一條直線，確保了等值線的唯一性（圖1（c））。

1 算法設計

1.1 數據結構定義

為了克服基于規則矩形網格追蹤算法帶來的不確定性，作者在本文中，提出用矩形網格的對角線將矩形網格劃分為上、下兩個小三角形，在同一個三角形中，等值線與三角形的邊要么沒有交點，要么有兩個交點。雖然矩形網格有兩條對角線，但如果當所有的網格都選擇同一方向的對角線，則就消除了劃分三角形的不確定性。新定義的數據結構如圖2所示。

1.2 求取等值線與三角形邊的交點

三角網格各個頂點的坐標及值是已知的，等值線不總是在頂點上，為了更精確地查找到等值線與三角形邊的交點，首先篩選出與等值線有交點的三角網格，然后分別在三條邊上利用一次線性插值確定等值線與邊的交點［7］（圖3）。

交點坐標計算公式為式（1）。

1.3 追蹤交點并將連接組成等值線

圖1 矩形網格不確定性和三角網格的唯一性Fig.1 Uncertainty of the rectangular grid and uniqueness of the triangle grid

圖2 規則三角網的數據結構Fig.2 Data structure of triangular network

圖3 確定邊與等值線的交點Fig.3 Determine the intersection of the edges and contours

等值線追蹤遵循原則：①先追蹤與整個網格的邊相交的不閉合等值線，再追蹤與整個網格的邊不相交的閉合等值線；②不閉合等值線追蹤，從左下右上的順序查找邊界上的交點作為起始追蹤點；③閉合等值線追蹤，從下而上的尋找交點作為起始追蹤點［8，11－13］。

當得到起始追蹤點A后，直接連接同一三角形的另一交點B既可，然后再查找共用交點B所在的邊的另一個三角形，并以B作為下一個三角形的起始追蹤點，如此類推，依次得到的交點便是等值線的節點，追蹤過程如圖4所示。

1.4 填充等值線

（1）首先將整個網格的四個角點組成的矩形，以最小值對應的顏色進行填充。

（2）填充不閉合等值線，按左下右上的順序，找到不閉合等值線的線頭，已知線頭后便可知線尾，然后從線尾出發，按逆時針方向查找整個網格的四個角點，將線尾和線頭間的網格的角點與等值線的節點組成一個多邊形，然后以此等值線值所對應的顏色進行填充。

（3）最后將閉合等值線的節點組成一個多邊形，以此等值線值所對應的顏色進行填充。

2 軟件實現及測試

圖4 等值線追蹤過程Fig.4 Process of contour tracing

根據上面的算法設計，在 Microsoft Visual C＋＋6.0開發環境下，運用C＋＋這種面向對象的程序設計語言［14－15］，開發完成了基于規則三角網等值線追蹤、填充的軟件，并且利用橫坐標范圍為“0”到“100”，縱坐標范圍為“0”到“100”，值的范圍為“1.5”到“2.5”為基數，隨機產生的1 000個離散數據，先利用surfer9網格化，然后將本軟件實現的等值線追蹤填充結果與sufer 9成圖進行對比（圖5）發現，除了兩個軟件繪制的色彩不現外，其圖效果幾乎一致，從而證明了本軟件不僅實現了等值線追蹤填充的目的，同時也證明了算法的正確性和高效性。

3 軟件應用

將編制成功的軟件，應用于區域地球物理調查成果集成與方法技術研究項目中的EH4電阻率反演剖面，利用本軟件成圖后的結果見圖6。此EH4測線方向在地表垂直于斷裂，通過EH4大地電磁測深反演后，利用本軟件成圖，圖6中對斷裂顯示清晰，不同電性的地下地質體界面清晰。

4 總結

圖5 對比本軟件與surfer 9成圖效果Fig.5 The software and surfer9comparison of drawing effect

圖6 EH4電阻率反演剖面圖Fig.6 Inversion profile chart of EH4 electrical resistivity

作者圍繞著基于規則三角網格等值線追蹤算法，利用C＋＋面向對象語言，在 Microsoft Visual C＋＋6.0環境下，成功地編制了基于規則三角網格等值線成圖軟件，通過與成功商業軟件surfer9的效果對比，顯示了本軟件有很好的成圖效果，等值線追蹤速度快，不存在等值線相交的錯誤。最后將此軟件應用于實際物探資料顯示中，得到很好的效果。雖然算法已經實現，但目前只能對規則的網格進行追蹤，對于有空洞或者不是長方形的數據還不能進行追蹤；色標只能在程序中設定，缺少接口進行交互式設置；等值線的等級不能交互式設置；標注也還沒有實現，總之軟件還需要更多的完善。

［1］李歡，奚小雙，吳城明.關于地質等值線圖繪制的幾個問題［J］.科技信息，2009（34）：71－72.

［2］陳永輝，盧德唐，黃豐.地質構造等值線原理及實現技術［J］.計算機應用與軟件，2006（04）：83－84，119.

［3］胡祥云，胡祖志，鐘宏偉，等.科學可視化及其在地學中的應用［J］.工程地球物理學報，2004（04）：358－362.

［4］郭長春.“等值線”教學探究［J］.黑龍江科技信息，2010（17）：177－178.

［5］夏健明.繪制規則離散點等值線的一種算法［J］.計算機工程與設計，2003（09）：94－96.

［6］孫桂茹，馬亮，路登平，等.等值線生成與圖形填充算法［J］.天津大學學報，2000（06）：816－818.

［7］吳天毅.矩形網格節點上的插值函數［J］.天津科技大學學報，2008，23（3）：83－86.

［8］于嘉，吳旭.一種改進的矩形網格等值線追蹤算法［J］.河南師范大學學報：自然科學版，2008（06）：34－36.

［9］李水鄉，陳斌，趙亮，等.快速Delaunay逐點插入網格生成算法［J］.北京大學學報：自然科學版，網絡版，2006，1（3）：302－306.

［10］孫科峰，孫根正，李潔.一種新的矩形網格生成等值線算法［J］.東華大學學報：自然科學版，2005（04）：66－69.

［11］于黎.等值線的跟蹤繪制［J］.石油工業計算機應用，1997（04）：18－19.

［12］何生存，郭三剛，劉珍花，等.離散點數據插值方法及等值線繪制技術的應用［J］.青海科技，2006（4）：24－26.

［13］湯子東，鄭明璽，王思群，等.一種基于三角網的等值線自動填充算法［J］.中國圖象圖形學報，2009（12）：2577－2581.

［14］呂鳳.C＋＋語言基礎教程［M］.北京：清華大學出版社，2000.

［15］李現勇.Visual C＋＋串口通信技術與工程實踐［M］.北京：人民郵電出版社，2003.