规则格网模型转换为三角网模型的新方法

李功权

(长江大学地球科学学院，湖北 荆州 434023)

规则格网模型转换为三角网模型的新方法

李功权

(长江大学地球科学学院，湖北 荆州 434023)

在保留重要点法的基础上，根据GRID与TIN模型的特性，设计了一个新的模板——“方孔钱”模板，此模板考虑了纵、横、对角3个方向上的情况，还兼顾了以节点为圆心，2倍网格步长度为半径的圆作为搜索方向。通过对一个在纵向上分布为3个山脊和2个山谷，且山脊与山谷之间有的坡度陡峭，有的坡度平缓的网格数据模型的测试说明，该算法不但很好地保留了关键网格点(顶点、凹点)，最大限度地消除了冗余高程点，消除率达50%以上；而且保证了转换前后模型的精度。

GRID; TIN; 三维可视化; 模板; 数字高程模型

在DEM中，格网模型(GRID)和不规则三角网(TIN)有着各自的优缺点，适用于不同的场合和应用目的[1]。但由于数据的来源格式不一定符合当前的应用和要求，这就有可能需要将GRID模型转换为TIN模型。目前GRID向TIN的转换主要有2种算法：①保留重要点法(VIP, Very Important Point)；②启发丢弃法(DH, Drop Heuristic)。VIP方法在保留关键网格点方面(顶点、凹点)最好，但没有很好的考虑在重构TIN模型时边选取的一些规则，没有最大限度的消除冗余点；DH方法在每次丢弃数据点时确保信息丢失最少，但要求计算量大[2]。这2种算法都没有实现效率与精度的最佳融合。易法令等[3]、朱理等[4]分别根据Delaunay三角形的特点和高程点的法向量来作为选点条件，研究了GRID向TIN的转换算法，在消除冗余点方面取得了较好的效果，但精度评价只是和ArcInfo提供的算法进行了对比。下面，笔者以最大限度的消除冗余点、保证转换精度为目标，设计了一种新的模板——“方孔钱”模板，很好的实现了效率与精度的兼容。

1 转换算法

1)转换算法选点一般原则 当空间某一点的高程数据能由已知点的高程数据推导时，该高程数据是冗余的,可删除。为了增加重构三角网时TIN模型的稳定性和规则性，在筛选时遵循了Delaunay三角网重构时的选取方法，也用到了Delaunay三角网的一些特性[5～7]。因此在判断某一点的高程数据为冗余后，还应判断删除该点后在重构TIN模型时还能否满足Delaunay三角网的特性。

2)模板说明 通过对TIN模型的构网方法与Delaunay三角网的特性研究论证出了2类可删除高程数据的情况。具体说明如下：

图1 第1类可删除的高程点

①第1类可删除的情况。当A22=(A12+A32)/2；A22=(A21+A23)/2；A22=(A11+A33)/2并且A22=(A13+A31)/2，A22可删除。如图1示，当A22点高程数据被删除后，可构成的TIN模型如图1(b)，(c)。根据Delaunay三角网的特性三角形的外接圆内不存在其他点[3～7]，图1(b),(c)是满足Delaunay三角网要求的。在图1(b)中A22的高程数据能由A21，A23推导，在图1(c)中A22的高程数据能由A12,A32推导，因此A22的高程数据可删除。要求A22=(A11+A33)/2和A22=(A13+A31)/2是考虑到精度的需求。

图2 第2类可删除的高程点

图3 模板形状

②第2类可删除的情况。当A22=(A12+A32)/2并且在模版的圆框内不存在两点过线段A12A32时；或者当A22=(A21+A23)/2并且在模版的圆框内不存在两点过线段A21A23时，A22可删除。如图2所示，高程点5的值能由高程点3、4的值导出。当删除点5的高程数据后，在形成Delaunay三角网时可出现12或34两条线段来实现三角化，如果是12线段来实现三角化则点3在点1、2、4所形成的外接圆内显然是不满足Delaunay三角网的特性的，也就是说在这种条件下删除5号点后在生成TIN模型只会选择34。而高程点5的值能有34导出。即要求12线段的长度超过34线段的长度时5号点才能删除。在模板中即要求圆框内不存在过线段3，4的线段。

根据GRID与TIN模型的特性，依据上述分析，可以归纳为模板形状如图3所示，其中A11…A33是高程数据在GRID中的保存形式，外圆是以线段A21A23的长度为半径，以点A22为圆心绘制。

3)精度保证 为了保证转换过程中模型的精度，在进行第2类情况的判断时，应先判断A22是否为“重要点”，所谓重要点是指在第一类情况中删除了高程点的情况下，那些保留下来的、能推导出已删除点高程数据的点。如果是重要点则即使满足条件也不应删除，不是则可按照上面的判断条件进行高程点的删除。

4)算法的灵活性 该模板不仅实现了效率与精度的最佳融合，并且还可根据不同的要求对删除条件进行调整以达到特定的要求。如精度要求相当高时，可将模板中的外圆去掉。效率要求相当高时，可在高程的比较中采用设置阀值的方法，还可适当的调整模板的外圆大小，以达到最大限度的消除冗余点，提高建TIN模型时的速度。

2 新算法测试及评估

为了检查新算法的效果，特挑选了一个具有典型特征的网格数据(见图4(a))，该数据模型在纵向上分布为3个山脊和2个山谷，且山脊与山谷之间有的坡度陡峭，有的坡度平缓。为了方便对比，在VC6.0下调用OpenGL提供的三维图形软件开发包(glu32.lib、opengl32.lib、glaux.lib)；将转换后的数据和Z轴上的属性值按Delaunay三角网规则构建TIN模型，实现了格网模型和TIN模型的三维可视化(图4(b))。这样，不仅有助于分析原始网格模型的典型地形特征，而且还有利于算法之间、模型之间的相互比较和评价。

图4 选点前后模型比较

笔者选择了保留重要点法中最经典的3×3模板算法与该算法进行了比较，如表1所示。可以看出，随着GRID模型的网格数目的增加，该算法去掉冗余点的数目越来越多，基本都超过了50%，但3×3模板算法冗余点的消除变化不大。该算法与3×3模板算法对比可以看出，该算法冗余点消除的百分比多达10%以上。在精度比较过程中，选择了表1中的第3组数据进行转换前后的比较(图5)，从图5分析得到，该算法不但在保留关键网格点方面(顶点、凹点)相当好，而且在坡度平缓区域中大大消除了冗余点。

表1 新算法与3×3模板比较

3 结 语

随着DEM模型在社会生活中的广泛应用，GRID和TIN模型的相互转化也会得到进一步的深入研究。笔者根据GRID模型和TIN模型的特点，以保留重要点法为基础，提出基于“方孔钱”模板的GRID向TIN的转换算法。通过在三维可视化的环境下的测试表明，该算法不但很好地保留了关键网格点(顶点、凹点)，而且最大限度地消除了冗余高程点，冗余高程点的消除率达50%以上，而且保证了转换前后模型的精度。可见，该算法有较高的实用价值。

[1]周启鸣, 刘学军. 数字地形分析[M]. 北京: 科学出版社, 2006：57-62.

[2]JAY Lee. Compparison of existing methods for building triangular irregular netwoek models of terrain from grid digital elevation models[J]. International Journal Geographical Information Systems，1991, 5(3): 267-285.

[3]易法令, 韩德志, 谢云. GRID转换为TIN的选点算法[J]. 计算机工程, 2003,29(11):62-63.

[4]朱理, 胡超. 一种有效的规则网格到不规则三角网的转换算法[J]. 计算技术与自动化, 2006,25(2):67-70.

[5]刘学军, 符锌砂, 赵建三. 三角网数字地面模型快速构建算法研究[J]. 中国公路学报, 2000, 13(2): 31-36.

[6]Tsung-Pao Fang and Les A. Piegl. Delaunay Triangulation Using a Uniform Grid[J]. IEEE Computer Graphics &Applications，1993,13(3):36-47.

[7]Lewis B A, Robinson J S. Triangulation of Planar Regions with Applications [J]. The Computer Journal, 1978, 21(4): 324-332.

[编辑] 洪云飞

10.3969/j.issn.1673-1409.2011.04.022

TP311

A

1673-1409(2011)04-0068-03