胡必鑫 (長江大學計算機科學學院，湖北 荊州 434023)

含斷層的不規(guī)則散亂數(shù)據(jù)域的等值線繪制

胡必鑫 (長江大學計算機科學學院，湖北 荊州 434023)

以石油地質勘探數(shù)據(jù)處理為應用背景，提出了一種含斷層的不規(guī)則散亂數(shù)據(jù)域中等值線的繪制方法。對于數(shù)據(jù)域中的斷層作為區(qū)域中的內邊界處理，通過平面外推法對邊界上的點進行插值。然后按照Delaunay三角剖分準則和邊界約束條件通過生長法對區(qū)域進行三角剖分，最后進行等值線追蹤和平滑，取得了較好的效果。

等值線；Delaunay三角剖分；斷層

等值線繪制是科學與工程計算領域中的一種常用的可視化方法。在石油地質勘探數(shù)據(jù)處理系統(tǒng)中，數(shù)據(jù)域邊界通常是任意形狀的多邊形，而且其中可能包含各種斷層。對該區(qū)域上的大規(guī)模散亂數(shù)據(jù)的等值線圖的繪制一直是人們的研究熱點[1，2]。筆者以石油地質勘探數(shù)據(jù)處理為應用背景，提出了一種含斷層的不規(guī)則散亂數(shù)據(jù)域等值線繪制方法，在實際應用中取得了較好的效果。

1 區(qū)域邊界數(shù)據(jù)處理

區(qū)域中的斷層和無有效數(shù)據(jù)的孔洞，與區(qū)域外邊界一樣實質上是區(qū)域中數(shù)據(jù)的邊界約束條件。為了內外邊界處理的一致性，對區(qū)域外邊界和內邊界(包括斷層、孔洞等)采用不同方向的有向多邊形表示，規(guī)定外邊界采用逆時針方向，而內邊界采用順時針方向，這樣當沿有向邊界行進時，不論內邊界還是外邊界，區(qū)域內部點總在邊界線的左側。

在大規(guī)模散亂數(shù)據(jù)的等值線繪制中，由于給定的數(shù)據(jù)均位于區(qū)域內，區(qū)域邊界上往往會缺失高程數(shù)據(jù)，為了使生成的等值線能夠抵達邊界，在獲取數(shù)據(jù)后必須首先對邊界進行高程數(shù)據(jù)外推插值，即通過外推點附近的點構造一個曲面，然后通過將外推點坐標代入曲面方程得到該點的高程數(shù)據(jù)。最簡單的方法是采用平面外推法對邊界上的數(shù)據(jù)進行插值，即假定外插點和其最近的3個點共面。

對于任意需要插值的邊界點(x,y)，首先在區(qū)域內找到離其最近的不在一條直線上的3個點(x1,y1)、(x2,y2)、(x3,y3)。該3點的高程值分別為z1、z2和z3。則該3點所在的平面為：

(1)

將x和y代入該平面方程(1)即可得到該邊界點的高程值。

2 含斷層的不規(guī)則散亂數(shù)據(jù)域的三角剖分

不規(guī)則的多邊形區(qū)域的等值線繪制，通常要將區(qū)域剖分為小的單元，然后在這些小單元的邊界上找到所要求的等值點并逐步追蹤。由于每一個三角形網(wǎng)格單元只可能有一條等值線存在，而且三角形網(wǎng)格適用于各種不規(guī)則的多邊形區(qū)域，因此，對不規(guī)則區(qū)域的區(qū)域剖分常采用Delaunay三角剖分。

Delaunay三角剖分要求所獲得的三角剖分網(wǎng)格最大可能地避免出現(xiàn)具有尖銳內角且形狀狹長的三角形形狀，這一特性即所謂的最大最小角準則(Max-Min Angle Criterion)：在三角形網(wǎng)格中，對任意相鄰的、構成嚴格凸四邊形的2個三角形來說，其6個內角中的最小值大于交換四邊形的對角線形成的另2個三角形的6個內角中的最小值。

目前Delaunay三角剖分方法主要包括分而治之法、逐點插入法、三角形生長法等多種方法[3～11]。

筆者給出了一種帶內邊界(斷層)約束的基于三角形生長的Delaunay三角剖分方法。

2.1數(shù)據(jù)結構

圖1 三角剖分數(shù)據(jù)結構示意圖

基于三角形單元的等值線追蹤的基本原理是區(qū)域邊界或內部三角形網(wǎng)格的邊上找到一個等值點，然后從一個三角形單元出發(fā)，找到該三角形單元的出邊，該邊同時又是相鄰三角形單元的一條入邊，因此，在進行區(qū)域的三角剖分時，不僅要記錄三角形3個頂點的坐標，同時還要記錄三角形網(wǎng)格與各條邊的關系。筆者主要采用網(wǎng)格點表、三角形網(wǎng)格表和邊表3類數(shù)據(jù)表來存儲區(qū)域三角剖分網(wǎng)格各元素及其相互關系。網(wǎng)格點表存儲所有網(wǎng)格點數(shù)據(jù)，其中每個網(wǎng)格點結構包括其坐標位置及該點的高程數(shù)據(jù)值；三角形網(wǎng)格表按逆時針方向順序存儲其3條有向邊的序號，若邊的方向相反則其值取負；邊表采用有向線段記錄剖分中得到的三角形的每條邊，為了下一步等值線追蹤的需要，還同時存儲該有向邊左右兩邊的三角形在三角形數(shù)組中的序號。

2.2三角剖分算法

筆者提出的三角剖分算法從邊界邊開始通過三角形逐步生長得到區(qū)域剖分結果。首先取邊界上兩相鄰點形成一條邊作為生長種子入棧，當棧非空時，重復執(zhí)行如下操作：

1)取棧頂邊元素出棧；

2)若該邊某方向(左或右)未擴展三角形，則按照Delaunay三角剖分準則及邊界約束條件(三角形的邊不允許穿越邊界)在指定方向找到第3點，與出棧邊形成一個三角形，并記錄該三角形及新產(chǎn)生的邊，同時記錄其相互關系；

3)若新形成三角形的2條邊不在邊界上且為新產(chǎn)生的邊則入棧。

在上述算法中，運算量主要集中于在某邊的相應方向擴展三角形時找第3點。按照Delaunay三角剖分的基本準則，應該盡量使三角形接近于正三角形，也就是說，第3點一般應位于邊的中點附近的某個區(qū)域內?；谏鲜龇治?，在進行三角剖分之前，首先將網(wǎng)格點數(shù)據(jù)按照一定間距劃分為網(wǎng)格，這樣找第3點時只需要在邊的中點附近的網(wǎng)格點中進行比較即可快速找到與該邊構成Delaunay三角剖分的第3點。

3 等值線追蹤與平滑

對于給定高程值的等值線，首先按邊的存儲順序查找具有相應等值點的邊。對同一高程值，任意三角形單元內只可能有一條等值線通過，即一條等值線從某三角形單元的一條邊進入后，一定通過另2條邊之一走出該三角形單元，故找到具有等值點的邊后，在該三角形的另2條邊上查找下一個等值點。在進行三角剖分時已經(jīng)記錄邊與三角形的關系，因此只需要按照有等值點的邊記錄的左右2個三角形就可從一個三角形單元追蹤進入下一個三角形單元，在追蹤過程中同時記錄已查找過的邊。若等值線為開曲線(即起始等值點在邊界邊上)，則追蹤到下一條邊界邊即可；若等值線為閉曲線(即起始等值點從內部邊開始)，則追蹤到起始等值點為止。

由于具有同一高程值的等值線可能有多條，因此采用鏈表記錄每一條等值線，同時用動態(tài)數(shù)組記錄每條等值線鏈表的表頭。

圖2 含斷層的不規(guī)則區(qū)域等值線圖

完成等值點追蹤后，為了使生成的等值線具有一定的光滑性，對每一條等值線可通過二次或三次Bazier曲線或樣條曲線進行擬合。

4 實際繪制效果

圖2給出了一個等值線繪制實例。在不規(guī)則的散亂數(shù)據(jù)區(qū)域中，多邊形ABCD內無有效數(shù)據(jù)，多邊形EFGH是一個斷層，其上下盤數(shù)值存在差異，從等值線追蹤結果來看，開等值線的起始點和終止點非常準確地抵達邊界，斷層約束得到了很好的體現(xiàn)，等值線平滑效果也非常好。實例證明，筆者給出的算法能夠滿足石油地質勘探數(shù)據(jù)的等值線圖的繪制要求。

5 結 語

筆者提出了帶內邊界約束條件的不規(guī)則區(qū)域等值線生成及追蹤方法用于解決具有斷層的散亂數(shù)據(jù)等值線圖的繪制。實例結果表明，該方法對于有斷層等復雜內外邊界的地質數(shù)據(jù)的區(qū)域剖分和等值線繪制具有較好的效果。

[1]王躍.在計算機上繪制含斷層的等值線圖[J].石油物探，1991，30(1)：109～114.

[2] 聞道秋.格網(wǎng)法繪制不規(guī)則區(qū)域等值線圖的計算機實現(xiàn)[J].南方冶金學院學報，1997，18(4)：265～270.

[3] 楊欽，徐永安，陳其明，等.任意平面域上離散點集的三角化方法[J].軟件學報，1998，9(4)：241～245.

[4] 盧朝陽，吳成柯，周幸妮.滿足全局Delaunay特性的帶特征約束的散亂數(shù)據(jù)最優(yōu)三角剖分[J].計算機學報，1997，20(2)：118～124.

[5] 盧朝陽，吳成柯.任意多邊形內帶特征約束的散列數(shù)據(jù)的最優(yōu)三角剖分[J].計算機輔助設計與圖形學學報，1997，9(4)：302～308.

[6] 趙文芳.離散點集Delaunay三角網(wǎng)生成算法改進與軟件開發(fā)[J].測繪工程，2003，12(4)：22～25.

[7] 潘榮江.基于均勻網(wǎng)格的Delaunay三角網(wǎng)算法在隨機聚合網(wǎng)屏中的應用[J].中國圖像圖形學報，2002，(5)：495～500.

[8] 唐澤圣，徐志強.二維點集三角剖分的動態(tài)生成與修改[J].計算機輔助設計與圖形學學報，1990，(3)：1～8.

[9] 簡憲華，崔漢國，曹茂春，等.帶內邊界約束散亂數(shù)據(jù)的Delauday三角剖分算法研究[J].計算機工程，2001，27(5)：105～106.

[10] 凌海濱，吳兵.改進的自連接Delaunay三角網(wǎng)生成算法[J].計算機應用，1999，19(12)：10～12.

[11] 周曉云，朱心雄.散亂數(shù)據(jù)點三角剖分方法綜述[J].工程圖學學報，1993，(1)：48～54.

[編輯] 易國華

TP15；TP391.41

A

1673-1409(2009)02-N066-03

2009-03-28

胡必鑫(1963-)，男， 1983年大學畢業(yè)，碩士，副教授，現(xiàn)主要從事科學計算可視化和圖像處理方面的教學與研究工作。