有许多种表达TIN拓扑结构的存储方式，一个简单的记录方式是：对于每一个三角形、边和节点都对应一个记录，三角形的记录包括三个指向它三个边的记录的指针：边的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它的两个顶点的记录的指针；也可以直接对每个三角形记录其顶点和相邻三角形（图4）。每个节点包括三个坐标值的字段，分别存储X，X，Z坐标。这种拓扑网络结构的特点是对于给定一个三角形查询其三个顶点高程和相邻三角形所用的时间是定长的，在沿直线计算地形剖面线时具有较高的效率。当然可以在此结构的基础上增加其它变化，以提高某些特殊运算的效率，例如在顶点的记录里增加指向其关联的边的指针。xyz顶点邻接三角形xyz155x62/Yz+243XYZ324Y+14X1311X/Y56f区z6XPxYz77P84+83.a点文件三角形文件图4：三角网的一种存储方式不规则三角网数字高程由连续的三角面组成，三角面的形状和大小取决于不规则分布的测点，或节点的位置和密度。不规则三角网与高程矩阵方法不同之处是随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形平坦时的数据亢余，又能按地形特征点如山脊、山谷线、地形变化线等表示数字高程特征。7.2.4层次模型层次地形模型（LayerofDetails，LOD）是一种表达多种不同精度水平的数字高程模型。大多数层次模型是基于不规则三角网模型的，通常不规则三角网的数据点越多精度越高，数据点越少精度越低，但数据点多则要求更多的计算资源。所以如果在精度满足要求的情况下，最好使用尽可能少的数据点。层次地形模型允许根据不同的任务要求选择不同精度的地形模型。层次模型的思想很理想，但在实际运用中必须注意几个重要的问题：
有许多种表达 TIN 拓扑结构的存储方式，一个简单的记录方式是：对于每一 个三角形、边和节点都对应一个记录，三角形的记录包括三个指向它三个边的记 录的指针；边的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它 的两个顶点的记录的指针；也可以直接对每个三角形记录其顶点和相邻三角形 （图 4）。每个节点包括三个坐标值的字段，分别存储 X，X，Z 坐标。这种拓扑 网络结构的特点是对于给定一个三角形查询其三个顶点高程和相邻三角形所用 的时间是定长的，在沿直线计算地形剖面线时具有较高的效率。当然可以在此结 构的基础上增加其它变化，以提高某些特殊运算的效率，例如在顶点的记录里增 加指向其关联的边的指针。 1 X Y Z 邻接三角形 2 X Y Z 3 X Y Z 4 X Y Z 5 X Y Z 6 X Y Z 7 X Y Z 8 X Y Z 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 顶点 5 6 8 7 5 4 2 3 6 5 7 4 6 5 4 4 8 8 8 7 2 1 X 3 1 2 6 4 5 3 4 X X 5 8 7 X 6 2 8 6 7 X X 点文件 三角形文件 1 1 1 2 5 4 4 3 图 4：三角网的一种存储方式 不规则三角网数字高程由连续的三角面组成，三角面的形状和大小取决于不 规则分布的测点，或节点的位置和密度。不规则三角网与高程矩阵方法不同之处 是随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能 够避免地形平坦时的数据冗余，又能按地形特征点如山脊、山谷线、地形变化线 等表示数字高程特征。 7.2.4 层次模型 层次地形模型（Layer of Details，LOD）是一种表达多种不同精度水平的 数字高程模型。大多数层次模型是基于不规则三角网模型的，通常不规则三角网 的数据点越多精度越高，数据点越少精度越低，但数据点多则要求更多的计算资 源。所以如果在精度满足要求的情况下，最好使用尽可能少的数据点。层次地形 模型允许根据不同的任务要求选择不同精度的地形模型。层次模型的思想很理 想，但在实际运用中必须注意几个重要的问题：
1）层次模型的存储问题，很显然，与直接存储不同，层次的数据必然导致数据元余。2）自动搜索的效率问题，例如搜索一个点可能先在最粗的层次上搜索，再在更细的层次上搜索，直到找到该点。3）三角网形状的优化问题，例如可以使用Delaunay三角剖分。4）模型可能充许根据地形的复杂程度采用不同详细层次的混合模型，例如，对于飞行模拟，近处时必须显示比远处更为详细的地形特征。5）在表达地貌特征方面应该一致，例如，如果在某个层次的地形模型上有一个明显的山峰，在更细层次的地形模型上也应该有这个山峰。这些问题目前还没有一个公认的最好的解决方案，仍需进一步深入研究。7.3DEM模型之间的相互转换在实际应用中，DEM模型之间可以相互转换。大部分DEM数据都是规则格网DEM，但由于规则格网DEM的数据量大而不便存储，也可能由于某些分析计算需要使用TIN模型的DEM，如进行通视分析。此时需要将格网DEM转成TIN模型的DEM。反之，如果已有TIN模型的DEM数据，为满足某种应用的需要，也需要转成规则格网的DEM。7.3.1不规则点集生成TIN对于不规则分布的高程点，可以形式化地描述为平面的一个无序的点集P，点集中每个点p对应于它的高程值。将该点集转成TIN，最常用的方法是Delaunay三角分方法。生成TIN的关键是Delaunay三角网的产生算法，下面先对Delaunay三角网和它的偶图Voronoi图作简要的描述。Voronoi图，叫泰森多边形或Dirichlet图，它由一组连续多边形组成，多边形的边界是由连接两邻点线段的垂直平分线组成。N个在平面上有区别的点，按照最近邻原则划分平面：每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Delaunay三角形是Voronoi图的偶图，如图9-6所示
1）层次模型的存储问题，很显然，与直接存储不同，层次的数据必然导致 数据冗余。 2）自动搜索的效率问题，例如搜索一个点可能先在最粗的层次上搜索，再 在更细的层次上搜索，直到找到该点。 3）三角网形状的优化问题，例如可以使用 Delaunay 三角剖分。 4）模型可能允许根据地形的复杂程度采用不同详细层次的混合模型，例如， 对于飞行模拟，近处时必须显示比远处更为详细的地形特征。 5）在表达地貌特征方面应该一致，例如，如果在某个层次的地形模型上有 一个明显的山峰，在更细层次的地形模型上也应该有这个山峰。 这些问题目前还没有一个公认的最好的解决方案，仍需进一步深入研究。 7.3 DEM 模型之间的相互转换 在实际应用中，DEM 模型之间可以相互转换。大部分 DEM 数据都是规则格网 DEM，但由于规则格网 DEM 的数据量大而不便存储，也可能由于某些分析计算需 要使用 TIN 模型的 DEM，如进行通视分析。此时需要将格网 DEM 转成 TIN 模型的 DEM。反之，如果已有 TIN 模型的 DEM 数据，为满足某种应用的需要，也需要转 成规则格网的 DEM。 7.3.1 不规则点集生成 TIN 对于不规则分布的高程点，可以形式化地描述为平面的一个无序的点集 P， 点集中每个点p对应于它的高程值。将该点集转成TIN，最常用的方法是Delaunay 三角剖分方法。生成 TIN 的关键是 Delaunay 三角网的产生算法，下面先对 Delaunay 三角网和它的偶图 Voronoi 图作简要的描述。 Voronoi 图，又叫泰森多边形或 Dirichlet 图，它由一组连续多边形组成， 多边形的边界是由连接两邻点线段的垂直平分线组成。N 个在平面上有区别的 点，按照最近邻原则划分平面：每个点与它的最近邻区域相关联。Delaunay 三 角形是由与相邻 Voronoi 多边形共享一条边的相关点连接而成的三角形。 Delaunay 三角形的外接圆圆心是与三角形相关的 Voronoi 多边形的一个顶点。 Delaunay 三角形是 Voronoi 图的偶图，如图 9-6 所示
图l：Delaunay三角网与Voronoi图下面简要介绍Delaunay三角形产生的基本准则：Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点[Delaunay1934]。Lawson[1972]提出了最大化最小角原则：每两个相邻的三角形构成的凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。LawSon［1977]又提出了一个局部优化过程LOP（LocalOptimizationProcedure）方法。如图2所示。先求出包含新插入点p的外接圆的三角形，这种三角形称为影响三角形（InfluenceTriangulation）。删除影响三角形的公共边（图b中粗线），将P与全部影响三角形的顶点连接完成p点在原Delaunay三角形中的插入。b.应用最大化最小角原则a.插入新点Pc.修改后的狄洛尼三角形图2：向Delaunay三角形中插入点
图 1：Delaunay 三角网与 Voronoi 图 下面简要介绍 Delaunay 三角形产生的基本准则： Delaunay 三角形产生准则的最简明的形式是：任何一个 Delaunay 三角形的 外接圆的内部不能包含其它任何点[Delaunay 1934]。Lawson[1972]提出了最大 化最小角原则：每两个相邻的三角形构成的凸四边形的对角线，在相互交换后， 六个内角的最小角不再增大。Lawson [1977]又提出了一个局部优化过程 LOP （Local Optimization Procedure）方法。如图 2 所示。先求出包含新插入点 p 的外接圆的三角形，这种三角形称为影响三角形（Influence Triangulation）。 删除影响三角形的公共边（图 b 中粗线），将 p 与全部影响三角形的顶点连接， 完成 p 点在原 Delaunay 三角形中的插入。 图 2：向 Delaunay 三角形中插入点
将该点集转成TIN，最常用的方法是Delaunay三角剖分方法，生成过程分两步完成：1）利用P中点集的平面坐标产生Delaunay三角网；2）给Delaunay三角形中的节点赋予高程值。7.3.2格网DEM转成TIN格网DEM转成TIN可以看作是一种规则分布的采样点生成TIN的特例，其目的是尽量减少TIN的顶点数目，同时尽可能多地保留地形信息，如山峰、山脊、谷底和坡度突变处。规则格网DEM可以简单地生成一个精细的规则三角网，针对它有许多算法，绝大多数算法都有两个重要的特征：1）筛选要保留或丢弃的格网点：2）判断停止筛选的条件。其中两个代表性的方法算法是保留重要点法和启发丢弃法。7.3.3保留重要点法该方法是一种保留规则格网DEM中的重要点来构造TIN的方法[Chen、Gauvara（1987）］。它是通过比较计算格网点的重要性，保留重要的格网点。重要点（VIP，VeryImportantPoint）是通过3*3的模板来确定的，根据八邻点的高程值决定模板中心是否为重要点。格网点的重要性是通过它的高程值与8邻点高程的内插值进行比较，当差分超过某个阅值的格网点保留下来。被保留的点作为三角网顶点生成Delaunay三角网。如图3所示，由3*3的模板得到中心点P和8邻点的高程值，计算中心点P到直线AE，CG，BF，DH的距离，图右图表示，再计算4个距离的平均值。如果平均值超过阈值，P点为重要点，则保留，否则去除P点。BACDHEGFAPE图3：VIP方法示意7.3.4启发丢弃法（DH一DropHeuristic）
将该点集转成 TIN，最常用的方法是 Delaunay 三角剖分方法，生成过程分 两步完成： 1）利用 P 中点集的平面坐标产生 Delaunay 三角网； 2）给 Delaunay 三角形中的节点赋予高程值。 7.3.2 格网 DEM 转成 TIN 格网 DEM 转成 TIN 可以看作是一种规则分布的采样点生成 TIN 的特例，其目 的是尽量减少 TIN 的顶点数目，同时尽可能多地保留地形信息，如山峰、山脊、 谷底和坡度突变处。规则格网 DEM 可以简单地生成一个精细的规则三角网，针对 它有许多算法，绝大多数算法都有两个重要的特征： 1）筛选要保留或丢弃的格网点； 2）判断停止筛选的条件。 其中两个代表性的方法算法是保留重要点法和启发丢弃法。 7.3.3 保留重要点法 该方法是一种保留规则格网 DEM 中的重要点来构造 TIN 的方法[Chen、 Gauvara（1987）]。它是通过比较计算格网点的重要性，保留重要的格网点。重 要点（VIP，Very Important Point）是通过 3*3 的模板来确定的，根据八邻点 的高程值决定模板中心是否为重要点。格网点的重要性是通过它的高程值与 8 邻点高程的内插值进行比较，当差分超过某个阈值的格网点保留下来。被保留的 点作为三角网顶点生成 Delaunay 三角网。如图 3 所示，由 3*3 的模板得到中心 点 P 和 8 邻点的高程值，计算中心点 P 到直线 AE，CG，BF，DH 的距离，图右图 表示，再计算 4 个距离的平均值。如果平均值超过阈值，P 点为重要点，则保留， 否则去除 P 点。 P A B C D E G F H Z A P E d 图 3：VIP 方法示意 7.3.4 启发丢弃法（DH—Drop Heuristic）