王超　逄超

摘要：本文分析了基于平三角形搜索消除平三角形的算法中存在的问题，通过对现有1：1万基础地理信息数据特点的研究和对已有算法的改进，得到一种新的、基于等高线的TIN模型中平三角形处理算法，并阐述了其原理和思路。通过对在不同情况下的等高线反演DEM进行实验，证明了该方法对于消除平三角形、提高1：1万比例尺DEM精度具有良好的效果。

1.引言

DEM（数字高程模型）是一种能够通过格网及其属性表现地形起伏的数据存储方式，也是基础地理信息数据的一个重要组成部分。DEM通常采用空间数据插值方法进行大批量生产，而空间数据插值算法主要包括两类：一类为基于等高线及高程点的约束形地形内插方法；另一类是完全根据地面离散的高程点进行地形内插的方法（通常为克里金内插法）。在内插效率方面，克里金内插算法具有较为突出的表现，但是对于1：1万比例尺基础地理信息数据而言，其内插精度无法完全满足要求，后期需要大量人工修改。因此，在实际生产中通常采用第一类方法。基于等高线及高程点的地形内插算法最核心的步骤便是构建不规则三角网，不规则三角网（TIN）是由连续的三角面组成，三角面的形状和大小取决于不规则分布的测点的密度和位置，既能够避免地形平坦时的数据冗余，又能按地形特征点表示数字高程特征，因而成为DEM的主要组织形式之一。

在利用等高线数据构建不规则三角网TIN的过程中，TIN模型的构网的方式通常采用基于边约束条件的Delau-nay三角剖分。由于等高线数据缺少地形特征点和特征线信息，因而在等高线弯曲较大的地区或山顶等区域常会出现平三角形（三角形三个顶点的高程值相等），从而无法保证所生成的DEM有较高的质量。因此，就需要对TIN中的平三角形进行有效处理。

2.TIN模型中平三角形的消除

平三角形出现的情况主要有四种：第一种是在一条等高线较为曲折的地方，这是最为常见的一种情况；第二种是在山顶或谷底地区闭合等高线的内部，由于其内部没有任何其他地形特征点或线，因此会在其内部完全生成平三角形区域；第三种是在具有两个或多个山头地区或周围有相同高程值等高线的谷底所形成的鞍部地区；第四种是在图幅边界地区，由于单条等高线与图幅之间的封闭地区缺少任何其他特征点，所以即使等高线在此处并不曲折，也会形成平三角区域。除在第三种情况中平三角形会出现在不同等高线之间，在其余三种情况下，平三角均会出现在同一等高线上。

之前曾有学者提出先将平三角形区域作为一个整体提取出来（如图1所示），之后取非平三角形△ABC的几何中心点，记为T，T点的高程由△ABC的平面方程确定，将点T与两个原始TIN三角形的四个顶点A、B、C、D相连并删除公共边BC，重构三角形网，形成四个新三角形，△ABT、△BDT、△DCT、△CAT；然后再计算△CDT的几何中心，依照上述方法计算插入点的平面位置和高程。

该方法是由最外边的三角形逐渐向内依次处理平三角形的过程，其优点是不用构造地性线树，因而从数据结构和处理过程的角度上讲，该算法非常简单高效。然而，这种方法存在一个严重的问题：当从外向内直接插入特征点时，相邻特征点的高程差将会逐渐减小，当平三角形区域中的三角形较多的时候，插入的特征点的高程差将趋近于0，这将导致区域末端的平三角形无法被全部处理，这里将这一现象称为插入点高程的退化现象。显然，这种算法对于地形特征点的高程计算并不合理，因此，需要对其进行改进。

2.1数据预处理

数据的预处理是实现本算法的一项重要的前提性工作，对于保证算法所处理数据的质量起着重要的作用。数据预处理包括以下三项内容：

对等高线数据进行简单的数据错误排查，找到高程突变点（远高于或低于周围邻近地形点高程值）和高程超出陆地最高或最低高程范围（-392m～8845m）的点，对其进行删除。

使用Douglas抽稀算法利用适当的距离阈值对等高线进行处理，除去不必要的冗余点和重复点。

在原始的TIN三角网中找到各个由平三角形相邻构成的平坦区域，并找到各区域中的平三角形的相邻关系以及入口平三角形。

2.2数据结构

在进行地形线树的构建过程中，应将每个地形特征点视为树的节点，对于每个节点有如下数据结构：

public class Node

{publie double x；

public double y；

public double z：

public node leftnode；//左子节点

public node rightnode；//右子节点

public int deep；//节点深度

public double distance；//该节点距上一节点的距离}

对于每个由TIN构成的不规则三角形，根据边与等高线的位置关系可分为软边（softedge）与硬边（hardedge）：软边为不与等高线重合的边，硬边为构成等高线一部分的边。故，不规则三角形边的数据结构中需加入枚举类型EdgeType，其值为soft和hard。

2.3算法的基本思想

首先，找到与人口三角形相邻的非平三角形的几何中心（重心），其坐标值为该三角形三点平面坐标的算术平均值，这样可以保证所插入的特征点落在该三角形内，以防止后来出现某些较为狭长的平三角形无法得到有效消除的可能情况；然后，将所找到的点作为二叉树的根节点Node进行存储，其平面坐标x，Y均已确定，z值可根据该三角形所代表的平面方程予以确定，其deep为0，distance为0，左右子节点leftnode和rightnode暂时为空，待稍候步骤中进行确定；之后，再找到入口三角形的软边中点，并计算其x，Y分量的坐标值（软边两端点坐标值平均值），将该节点作为二叉树的第二个节点存储，同时将其作为上一个节点的左子节点（由此可知第一个节点的右子节点必为空），该节点的deep较上一节点的deep加1，变为1，计算该节点到上一节点的水平距离作为该节点的distance的值，其z坐标暂时不确定，平面坐标值已算出，左右节点待下一步确定；之后，将新找到的节点同与入口平三角形相邻的平三角形构成四边形，继续计算其重心坐标并建立节点，此时可能会找到两个平三角形与其相邻，这样就会出现二叉树的分支，将首先找到的一个分支定为左分支，随后找到的定为由分支，依照上述方法继续确定各节点的相关信息，直到将平三角形区域中所有的三角形遍历完毕。当搜索到底部的三角形时，由于这样的三角形不再有相邻的平三角形。所以，此处节点的左右子节点均为空。此时形成的二叉树，其各个节点的信息只有高程值z尚未确定。

在确定了内插特征点二叉树的存储结构以及其平面位置相关信息后，再来确定各特征点的高程值。首先搜索到deep值最大的节点，再根据节点之间的相关关系，从叶节点向根节点回溯，计算回溯路径的长度（各节点的distance之和），并以此来确定树的主干；当该步回溯结束后，将根节点的高程和叶节点的高程之差，按照各节点之间的距离（dis-tance）为其按照距离加权分配高程差，就得到了各节点的高程值z。

2.4特殊地形的处理

对于鞍部平三角形区域，由于其拥有两个甚至多个入口平三角形，因此对其处理的方式应予以调整，应对其各个入口三角形依次遍历，以便从各个入口向内依次处理。此时应该注意的是，由于鞍部的中心没有其他高程信息，导致在从外部处理到中心时，无法同一般情况那样进行回溯处理，将其几何中心的点的高程值定为外部等高线高程与平三角形高程的均值，即二分等高距处的高程。在处理到中心平三角形后，可以对每一条路径分别利用回溯的方法对内插特征点的高程进行确定。

对于山顶地区的平三角形区域，由于其是由闭合等高线所形成的，既没有入口三角形也没有中心的额外高程信息，所以其处理方法应继续予以调整。本文仿照艾廷华所提出的面状区域中心确定方法，按照平三角形周围面积最均衡的原则，找到中心平三角形，将其重心作为此类型的平三角区域的重心，并作为内插特征点树的根节点，从此点开始，向周围处理，直到遇到等高线上的点，然后进行回溯处理，确定各点高程。

对于入口边处于图幅边缘的平三角形区域，其处理方式为：将边缘处的平三角形找到，计算其重心位置（三点坐标平均值），找到与该平三角形相邻的非平三角形（以硬边相邻），设非平三角形的高低点（不在硬边上的顶点）为zr，平三角形高程为zq，则所找到的重心的高程为Zp=Zq-2/Zr-Zq然后以该点为根节点，按照上述插点回溯算法确定各内插特征点的相关信息。

3.实验与结论

为了验证算法对于TIN的模拟精度的影响效果，进行如下实验：首先，利用已有的高程控制点的平面坐标在原始TIN模型中通过内插计算得到的理论高程；然后再利用相同的方法在利用本文所提出的算法重构后的TIN模型中计算得到另一组理论高程；将两组理论高程与控制点的实际高程进行对比，可以发现该算法对于TIN模型的模拟精度有大幅度提高，其高程误差在1/2等高距以内。该算法对于平三角形区域的处理有较好效果，与其他地形特征点内插方法相比，其在运行效率及精度指标上均具有较大优势，能够很好地满足1：1万比例尺DEM数据的生产要求。