含断层的不规则散乱数据域的等值线绘制

胡必鑫 (长江大学计算机科学学院，湖北 荆州 434023)

含断层的不规则散乱数据域的等值线绘制

胡必鑫 (长江大学计算机科学学院，湖北 荆州 434023)

以石油地质勘探数据处理为应用背景，提出了一种含断层的不规则散乱数据域中等值线的绘制方法。对于数据域中的断层作为区域中的内边界处理，通过平面外推法对边界上的点进行插值。然后按照Delaunay三角剖分准则和边界约束条件通过生长法对区域进行三角剖分，最后进行等值线追踪和平滑，取得了较好的效果。

等值线；Delaunay三角剖分；断层

等值线绘制是科学与工程计算领域中的一种常用的可视化方法。在石油地质勘探数据处理系统中，数据域边界通常是任意形状的多边形，而且其中可能包含各种断层。对该区域上的大规模散乱数据的等值线图的绘制一直是人们的研究热点[1，2]。笔者以石油地质勘探数据处理为应用背景，提出了一种含断层的不规则散乱数据域等值线绘制方法，在实际应用中取得了较好的效果。

1 区域边界数据处理

区域中的断层和无有效数据的孔洞，与区域外边界一样实质上是区域中数据的边界约束条件。为了内外边界处理的一致性，对区域外边界和内边界(包括断层、孔洞等)采用不同方向的有向多边形表示，规定外边界采用逆时针方向，而内边界采用顺时针方向，这样当沿有向边界行进时，不论内边界还是外边界，区域内部点总在边界线的左侧。

在大规模散乱数据的等值线绘制中，由于给定的数据均位于区域内，区域边界上往往会缺失高程数据，为了使生成的等值线能够抵达边界，在获取数据后必须首先对边界进行高程数据外推插值，即通过外推点附近的点构造一个曲面，然后通过将外推点坐标代入曲面方程得到该点的高程数据。最简单的方法是采用平面外推法对边界上的数据进行插值，即假定外插点和其最近的3个点共面。

对于任意需要插值的边界点(x,y)，首先在区域内找到离其最近的不在一条直线上的3个点(x1,y1)、(x2,y2)、(x3,y3)。该3点的高程值分别为z1、z2和z3。则该3点所在的平面为：

(1)

将x和y代入该平面方程(1)即可得到该边界点的高程值。

2 含断层的不规则散乱数据域的三角剖分

不规则的多边形区域的等值线绘制，通常要将区域剖分为小的单元，然后在这些小单元的边界上找到所要求的等值点并逐步追踪。由于每一个三角形网格单元只可能有一条等值线存在，而且三角形网格适用于各种不规则的多边形区域，因此，对不规则区域的区域剖分常采用Delaunay三角剖分。

Delaunay三角剖分要求所获得的三角剖分网格最大可能地避免出现具有尖锐内角且形状狭长的三角形形状，这一特性即所谓的最大最小角准则(Max-Min Angle Criterion)：在三角形网格中，对任意相邻的、构成严格凸四边形的2个三角形来说，其6个内角中的最小值大于交换四边形的对角线形成的另2个三角形的6个内角中的最小值。

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

笔者给出了一种带内边界(断层)约束的基于三角形生长的Delaunay三角剖分方法。

2.1数据结构

图1 三角剖分数据结构示意图

基于三角形单元的等值线追踪的基本原理是区域边界或内部三角形网格的边上找到一个等值点，然后从一个三角形单元出发，找到该三角形单元的出边，该边同时又是相邻三角形单元的一条入边，因此，在进行区域的三角剖分时，不仅要记录三角形3个顶点的坐标，同时还要记录三角形网格与各条边的关系。笔者主要采用网格点表、三角形网格表和边表3类数据表来存储区域三角剖分网格各元素及其相互关系。网格点表存储所有网格点数据，其中每个网格点结构包括其坐标位置及该点的高程数据值；三角形网格表按逆时针方向顺序存储其3条有向边的序号，若边的方向相反则其值取负；边表采用有向线段记录剖分中得到的三角形的每条边，为了下一步等值线追踪的需要，还同时存储该有向边左右两边的三角形在三角形数组中的序号。

2.2三角剖分算法

笔者提出的三角剖分算法从边界边开始通过三角形逐步生长得到区域剖分结果。首先取边界上两相邻点形成一条边作为生长种子入栈，当栈非空时，重复执行如下操作：

1)取栈顶边元素出栈；

2)若该边某方向(左或右)未扩展三角形，则按照Delaunay三角剖分准则及边界约束条件(三角形的边不允许穿越边界)在指定方向找到第3点，与出栈边形成一个三角形，并记录该三角形及新产生的边，同时记录其相互关系；

3)若新形成三角形的2条边不在边界上且为新产生的边则入栈。

在上述算法中，运算量主要集中于在某边的相应方向扩展三角形时找第3点。按照Delaunay三角剖分的基本准则，应该尽量使三角形接近于正三角形，也就是说，第3点一般应位于边的中点附近的某个区域内。基于上述分析，在进行三角剖分之前，首先将网格点数据按照一定间距划分为网格，这样找第3点时只需要在边的中点附近的网格点中进行比较即可快速找到与该边构成Delaunay三角剖分的第3点。

3 等值线追踪与平滑

对于给定高程值的等值线，首先按边的存储顺序查找具有相应等值点的边。对同一高程值，任意三角形单元内只可能有一条等值线通过，即一条等值线从某三角形单元的一条边进入后，一定通过另2条边之一走出该三角形单元，故找到具有等值点的边后，在该三角形的另2条边上查找下一个等值点。在进行三角剖分时已经记录边与三角形的关系，因此只需要按照有等值点的边记录的左右2个三角形就可从一个三角形单元追踪进入下一个三角形单元，在追踪过程中同时记录已查找过的边。若等值线为开曲线(即起始等值点在边界边上)，则追踪到下一条边界边即可；若等值线为闭曲线(即起始等值点从内部边开始)，则追踪到起始等值点为止。

由于具有同一高程值的等值线可能有多条，因此采用链表记录每一条等值线，同时用动态数组记录每条等值线链表的表头。

图2 含断层的不规则区域等值线图

完成等值点追踪后，为了使生成的等值线具有一定的光滑性，对每一条等值线可通过二次或三次Bazier曲线或样条曲线进行拟合。

4 实际绘制效果

图2给出了一个等值线绘制实例。在不规则的散乱数据区域中，多边形ABCD内无有效数据，多边形EFGH是一个断层，其上下盘数值存在差异，从等值线追踪结果来看，开等值线的起始点和终止点非常准确地抵达边界，断层约束得到了很好的体现，等值线平滑效果也非常好。实例证明，笔者给出的算法能够满足石油地质勘探数据的等值线图的绘制要求。

5 结 语

笔者提出了带内边界约束条件的不规则区域等值线生成及追踪方法用于解决具有断层的散乱数据等值线图的绘制。实例结果表明，该方法对于有断层等复杂内外边界的地质数据的区域剖分和等值线绘制具有较好的效果。

[1]王跃.在计算机上绘制含断层的等值线图[J].石油物探，1991，30(1)：109～114.

[2] 闻道秋.格网法绘制不规则区域等值线图的计算机实现[J].南方冶金学院学报，1997，18(4)：265～270.

[3] 杨钦，徐永安，陈其明，等.任意平面域上离散点集的三角化方法[J].软件学报，1998，9(4)：241～245.

[4] 卢朝阳，吴成柯，周幸妮.满足全局Delaunay特性的带特征约束的散乱数据最优三角剖分[J].计算机学报，1997，20(2)：118～124.

[5] 卢朝阳，吴成柯.任意多边形内带特征约束的散列数据的最优三角剖分[J].计算机辅助设计与图形学学报，1997，9(4)：302～308.

[6] 赵文芳.离散点集Delaunay三角网生成算法改进与软件开发[J].测绘工程，2003，12(4)：22～25.

[7] 潘荣江.基于均匀网格的Delaunay三角网算法在随机聚合网屏中的应用[J].中国图像图形学报，2002，(5)：495～500.

[8] 唐泽圣，徐志强.二维点集三角剖分的动态生成与修改[J].计算机辅助设计与图形学学报，1990，(3)：1～8.

[9] 简宪华，崔汉国，曹茂春，等.带内边界约束散乱数据的Delauday三角剖分算法研究[J].计算机工程，2001，27(5)：105～106.

[10] 凌海滨，吴兵.改进的自连接Delaunay三角网生成算法[J].计算机应用，1999，19(12)：10～12.

[11] 周晓云，朱心雄.散乱数据点三角剖分方法综述[J].工程图学学报，1993，(1)：48～54.

[编辑] 易国华

TP15；TP391.41

A

1673-1409(2009)02-N066-03

2009-03-28

胡必鑫(1963-)，男， 1983年大学毕业，硕士，副教授，现主要从事科学计算可视化和图像处理方面的教学与研究工作。