基于規(guī)則三角網(wǎng)的等值線追蹤與填充算法的實(shí)現(xiàn)和應(yīng)用

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

（中國地質(zhì)調(diào)查局 成都地質(zhì)調(diào)查中心，成都 610081）

0 引言

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

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

1 算法設(shè)計

1.1 數(shù)據(jù)結(jié)構(gòu)定義

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

1.2 求取等值線與三角形邊的交點(diǎn)

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

交點(diǎn)坐標(biāo)計算公式為式（1）。

1.3 追蹤交點(diǎn)并將連接組成等值線

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

圖2 規(guī)則三角網(wǎng)的數(shù)據(jù)結(jié)構(gòu)Fig.2 Data structure of triangular network

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

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

當(dāng)?shù)玫狡鹗甲粉欬c(diǎn)A后，直接連接同一三角形的另一交點(diǎn)B既可，然后再查找共用交點(diǎn)B所在的邊的另一個三角形，并以B作為下一個三角形的起始追蹤點(diǎn)，如此類推，依次得到的交點(diǎn)便是等值線的節(jié)點(diǎn)，追蹤過程如圖4所示。

1.4 填充等值線

（1）首先將整個網(wǎng)格的四個角點(diǎn)組成的矩形，以最小值對應(yīng)的顏色進(jìn)行填充。

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

（3）最后將閉合等值線的節(jié)點(diǎn)組成一個多邊形，以此等值線值所對應(yīng)的顏色進(jìn)行填充。

2 軟件實(shí)現(xiàn)及測試

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

根據(jù)上面的算法設(shè)計，在 Microsoft Visual C＋＋6.0開發(fā)環(huán)境下，運(yùn)用C＋＋這種面向?qū)ο蟮某绦蛟O(shè)計語言［14－15］，開發(fā)完成了基于規(guī)則三角網(wǎng)等值線追蹤、填充的軟件，并且利用橫坐標(biāo)范圍為“0”到“100”，縱坐標(biāo)范圍為“0”到“100”，值的范圍為“1.5”到“2.5”為基數(shù)，隨機(jī)產(chǎn)生的1 000個離散數(shù)據(jù)，先利用surfer9網(wǎng)格化，然后將本軟件實(shí)現(xiàn)的等值線追蹤填充結(jié)果與sufer 9成圖進(jìn)行對比（圖5）發(fā)現(xiàn)，除了兩個軟件繪制的色彩不現(xiàn)外，其圖效果幾乎一致，從而證明了本軟件不僅實(shí)現(xiàn)了等值線追蹤填充的目的，同時也證明了算法的正確性和高效性。

3 軟件應(yīng)用

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

4 總結(jié)

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

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

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

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

［2］陳永輝，盧德唐，黃豐.地質(zhì)構(gòu)造等值線原理及實(shí)現(xiàn)技術(shù)［J］.計算機(jī)應(yīng)用與軟件，2006（04）：83－84，119.

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

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

［5］夏健明.繪制規(guī)則離散點(diǎn)等值線的一種算法［J］.計算機(jī)工程與設(shè)計，2003（09）：94－96.

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

［7］吳天毅.矩形網(wǎng)格節(jié)點(diǎn)上的插值函數(shù)［J］.天津科技大學(xué)學(xué)報，2008，23（3）：83－86.

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

［9］李水鄉(xiāng)，陳斌，趙亮，等.快速Delaunay逐點(diǎn)插入網(wǎng)格生成算法［J］.北京大學(xué)學(xué)報：自然科學(xué)版，網(wǎng)絡(luò)版，2006，1（3）：302－306.

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

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

［12］何生存，郭三剛，劉珍花，等.離散點(diǎn)數(shù)據(jù)插值方法及等值線繪制技術(shù)的應(yīng)用［J］.青?？萍?，2006（4）：24－26.

［13］湯子?xùn)|，鄭明璽，王思群，等.一種基于三角網(wǎng)的等值線自動填充算法［J］.中國圖象圖形學(xué)報，2009（12）：2577－2581.

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

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