第七章数字地面模型（DTM）及其应用7.1数字地形模型（DTM）与地形分析7.1.1 概述数字地形模型（DTM，DigitalTerrainModel）最初是为了高速公路的自动设计提出来的（Mi11er，1956）。此后，它被用于各种线路选线（铁路、公路、输电线）的设计以及各种工程的面积、体积、坡度计算，任意两点间的通视判断及任意断面图绘制。在测绘中被用于绘制等高线、坡度坡向图、立体透视图，制作正射影像图以及地图的修测。在遥感应用中可作为分类的辅助数据。它还是地理信息系统的基础数据，可用于土地利用现状的分析、合理规划及洪水险情预报等。在军事上可用于导航及导弹制导、作战电子沙盘等。对DTM的研究包括DTM的精度问题、地形分类、数据采集、DTM的粗差探测、质量控制、数据压缩、DTM应用以及不规则三角网DTM的建立与应用等。7.1.2DTM和DEM从数学的角度，高程模型是高程Z关于平面坐标X，Y两个自变量的连续函数，数字高程模型（DEM）只是它的一个有限的离散表示。高程模型最常见的表达是相对于海平面的海拔高度，或某个参考平面的相对高度，所以高程模型又叫地形模型。实际上地形模型不仅包含高程属性，还包含其它的地表形态属性，如坡度、坡向等。数字地形模型是地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述。数字地形模型中地形属性为高程时称为数字高程模型（DigitalElevationModel，简称DEM）。高程是地理空间中的第三维坐标。由于传统的地理信息系统的数据结构都是二维的，数字高程模型的建立是一个必要的补充。DEM通常用地表规则网格单元构成的高程矩阵表示，广义的DEM还包括等高线、三角网等所有表达地面高程的数字表示。在地理信息系统中，DEM是建立DTM的基础数据，其它的地形要素可由DEM直接或间接导出，称为“派生数据”，如坡度、坡向。7.1.3DEM的表示法一个地区的地表高程的变化可以采用多种方法表达，用数学定义的表面或点、线、影像都可用来表示DEM，如图1所示
第七章 数字地面模型（DTM）及其应用 7.1 数字地形模型（DTM）与地形分析 7.1.1 概述 数字地形模型（DTM, Digital Terrain Model）最初是为了高速公路的自动 设计提出来的（Miller，1956）。此后，它被用于各种线路选线（铁路、公路、 输电线）的设计以及各种工程的面积、体积、坡度计算，任意两点间的通视判断 及任意断面图绘制。在测绘中被用于绘制等高线、坡度坡向图、立体透视图，制 作正射影像图以及地图的修测。在遥感应用中可作为分类的辅助数据。它还是地 理信息系统的基础数据，可用于土地利用现状的分析、合理规划及洪水险情预报 等。在军事上可用于导航及导弹制导、作战电子沙盘等。对 DTM 的研究包括 DTM 的精度问题、地形分类、数据采集、DTM 的粗差探测、质量控制、数据压缩、DTM 应用以及不规则三角网 DTM 的建立与应用等。 7.1.2 DTM 和 DEM 从数学的角度，高程模型是高程 Z 关于平面坐标 X，Y 两个自变量的连续函 数，数字高程模型（DEM）只是它的一个有限的离散表示。高程模型最常见的表 达是相对于海平面的海拔高度，或某个参考平面的相对高度，所以高程模型又叫 地形模型。实际上地形模型不仅包含高程属性，还包含其它的地表形态属性，如 坡度、坡向等。 数字地形模型是地形表面形态属性信息的数字表达，是带有空间位置特征和 地形属性特征的数字描述。数字地形模型中地形属性为高程时称为数字高程模型 （Digital Elevation Model，简称 DEM）。高程是地理空间中的第三维坐标。 由于传统的地理信息系统的数据结构都是二维的，数字高程模型的建立是一个必 要的补充。DEM 通常用地表规则网格单元构成的高程矩阵表示，广义的 DEM 还包 括等高线、三角网等所有表达地面高程的数字表示。在地理信息系统中，DEM 是 建立 DTM 的基础数据，其它的地形要素可由 DEM 直接或间接导出，称为“派生数 据”，如坡度、坡向。 7.1.3 DEM 的表示法 一个地区的地表高程的变化可以采用多种方法表达，用数学定义的表面或 点、线、影像都可用来表示 DEM，如图 1 所示
1）数学方法用数学方法来表达，可以采用整体拟合方法，即根据区域所有的高程点数据，用傅立叶级数和高次多项式拟合统一的地面高程曲面。也可用局部拟合方法，将地表复杂表面分成正方形规则区域或面积大致相等的不规则区域进行分块搜索，根据有限个点进行拟合形成高程曲面。2）图形方法1.线模式等高线是表示地形最常见的形式。其它的地形特征线也是表达地面高程的重要信息源，如山脊线、谷底线、海岸线及坡度变换线等。2.．点模式用离散采样数据点建立DEM是DEM建立常用的方法之一。数据采样可以按规则格网采样，可以是密度一致的或不一致的：可以是不规则采样，如不规则三角网、邻近网模型等；也可以有选择性地采样，采集山峰、洼坑、隘口、边界等重要特征点。厂傅立叶级数整体高次多项式数学方法规则数学分块局部不规则数学分块厂密度一致规则L密度不一致DEM表示方法一厂三角网一点数据+不规则L邻近网山峰、洼坑L典型特征口、边界L图形法一水平线一山脊线一线数据十垂直线谷底线L典型线海岸线L坡度变换线图1：DEM的表示方法在地理信息系统中，DEM最主要的三种表示模型是：规则格网模型，等高线模型和不规则三角网模型。7.2DEM的主要表示模型
1）数学方法 用数学方法来表达，可以采用整体拟合方法，即根据区域所有的高程点数据， 用傅立叶级数和高次多项式拟合统一的地面高程曲面。也可用局部拟合方法，将 地表复杂表面分成正方形规则区域或面积大致相等的不规则区域进行分块搜索， 根据有限个点进行拟合形成高程曲面。 2）图形方法 1. 线模式 等高线是表示地形最常见的形式。其它的地形特征线也是表达地面高程的重 要信息源，如山脊线、谷底线、海岸线及坡度变换线等。 2. 点模式 用离散采样数据点建立 DEM 是 DEM 建立常用的方法之一。数据采样可以按规 则格网采样，可以是密度一致的或不一致的；可以是不规则采样，如不规则三角 网、邻近网模型等；也可以有选择性地采样，采集山峰、洼坑、隘口、边界等重 要特征点。 图 1：DEM 的表示方法 在地理信息系统中，DEM 最主要的三种表示模型是：规则格网模型，等高线 模型和不规则三角网模型。 7.2 DEM 的主要表示模型
7.2.1规则格网模型规则网格，通常是正方形，也可以是矩形、三角形等规则网格。规则网格将区域空间切分为规则的格网单元，每个格网单元对应一个数值。数学上可以表示为一个矩阵，在计算机实现中则是一个二维数组。每个格网单元或数组的一个元素，对应一个高程值，如图1所示。2591786350536344554035945816402505151OU10084.66425564665465511034784665665968249662D915619o6St8678570829828056155374b16962668388731458634570566274577174图1：格网DEM对于每个格网的数值有两种不同的解释。第一种是格网栅格观点，认为该格网单元的数值是其中所有点的高程值，即格网单元对应的地面面积内高程是均一的高度，这种数字高程模型是一个不连续的函数。第二种是点栅格观点，认为该网格单元的数值是网格中心点的高程或该网格单元的平均高程值，这样就需要用一种插值方法来计算每个点的高程。计算任何不是网格中心的数据点的高程值，使用周围4个中心点的高程值，采用距离加权平均方法进行计算，当然也可使用样条函数和克里金插值方法。规则格网的高程矩阵，可以很容易地用计算机进行处理，特别是栅格数据结构的地理信息系统。它还可以很容易地计算等高线、坡度坡向、山坡阴影和自动提取流域地形，使得它成为DEM最广泛使用的格式，目前许多国家提供的DEM数据都是以规则格网的数据矩阵形式提供的。格网DEM的缺点是不能准确表示地形的结构和细部，为避免这些问题，可采用附加地形特征数据，如地形特征点、山脊线、谷底线、断裂线，以描述地形结构。格网DEM的另一个缺点是数据量过大，给数据管理带来了不方便，通常要进
7.2.1 规则格网模型 规则网格，通常是正方形，也可以是矩形、三角形等规则网格。规则网格将 区域空间切分为规则的格网单元，每个格网单元对应一个数值。数学上可以表示 为一个矩阵，在计算机实现中则是一个二维数组。每个格网单元或数组的一个元 素，对应一个高程值，如图 1 所示。 图 1：格网 DEM 对于每个格网的数值有两种不同的解释。第一种是格网栅格观点，认为该格 网单元的数值是其中所有点的高程值，即格网单元对应的地面面积内高程是均一 的高度，这种数字高程模型是一个不连续的函数。第二种是点栅格观点，认为该 网格单元的数值是网格中心点的高程或该网格单元的平均高程值，这样就需要用 一种插值方法来计算每个点的高程。计算任何不是网格中心的数据点的高程值， 使用周围 4 个中心点的高程值，采用距离加权平均方法进行计算，当然也可使用 样条函数和克里金插值方法。 规则格网的高程矩阵，可以很容易地用计算机进行处理，特别是栅格数据结 构的地理信息系统。它还可以很容易地计算等高线、坡度坡向、山坡阴影和自动 提取流域地形，使得它成为 DEM 最广泛使用的格式，目前许多国家提供的 DEM 数据都是以规则格网的数据矩阵形式提供的。格网 DEM 的缺点是不能准确表示地 形的结构和细部，为避免这些问题，可采用附加地形特征数据，如地形特征点、 山脊线、谷底线、断裂线，以描述地形结构。 格网 DEM 的另一个缺点是数据量过大，给数据管理带来了不方便，通常要进
行压缩存储。DEM数据的无损压缩可以采用普通的栅格数据压缩方式，如游程编码、块码等，但是由于DEM数据反映了地形的连续起伏变化，通常比较“破碎”，普通压缩方式难以达到很好的效果；因此对于网格DEM数据，可以采用哈夫曼编码进行无损压缩；有时，在牺牲细节信息的前提下，可以对网格DEM进行有损压缩，通常的有损压缩大都是基于离散余弦变换（DiscreteCosineTransformation，DcT）或小波变换（WaveletTransformation）的，由于小波变换具有较好的保持细节的特性，近年来将小波变换应用于DEM数据处理的研究较多。7.2.2等高线模型等高线模型表示高程，高程值的集合是已知的，每一条等高线对应一个已知的高程值，这样一系列等高线集合和它们的高程值一起就构成了一种地面高程模型。如图2所示。图2：等高线等高线通常被存成一个有序的坐标点对序列，可以认为是一条带有高程值属性的简单多边形或多边形弧段。由于等高线模型只表达了区域的部分高程值，往往需要一种插值方法来计算落在等高线外的其它点的高程，又因为这些点是落在两条等高线包围的区域内，所以，通常只使用外包的两条等高线的高程进行插值。等高线通常可以用二维的链表来存储。另外的一种方法是用图来表示等高线的拓扑关系，将等高线之间的区域表示成图的节点，用边表示等高线本身。此方法满足等高线闭合或与边界闭合、等高线互不相交两条拓扑约束。这类图可以改
行压缩存储。DEM 数据的无损压缩可以采用普通的栅格数据压缩方式，如游程编 码、块码等，但是由于 DEM 数据反映了地形的连续起伏变化，通常比较“破碎”， 普通压缩方式难以达到很好的效果；因此对于网格 DEM 数据，可以采用哈夫曼编 码进行无损压缩；有时，在牺牲细节信息的前提下，可以对网格 DEM 进行有损压 缩 ， 通 常 的 有 损 压 缩 大 都 是 基 于 离 散 余 弦 变 换 （ Discrete Cosine Transformation，DCT）或小波变换（Wavelet Transformation）的，由于小波 变换具有较好的保持细节的特性，近年来将小波变换应用于 DEM 数据处理的研究 较多。 7.2.2 等高线模型 等高线模型表示高程，高程值的集合是已知的，每一条等高线对应一个已知 的高程值，这样一系列等高线集合和它们的高程值一起就构成了一种地面高程模 型。如图 2 所示。 图 2：等高线 等高线通常被存成一个有序的坐标点对序列，可以认为是一条带有高程值属 性的简单多边形或多边形弧段。由于等高线模型只表达了区域的部分高程值，往 往需要一种插值方法来计算落在等高线外的其它点的高程，又因为这些点是落在 两条等高线包围的区域内，所以，通常只使用外包的两条等高线的高程进行插值。 等高线通常可以用二维的链表来存储。另外的一种方法是用图来表示等高线 的拓扑关系，将等高线之间的区域表示成图的节点，用边表示等高线本身。此方 法满足等高线闭合或与边界闭合、等高线互不相交两条拓扑约束。这类图可以改
造成一种无圈的自由树。下图为一个等高线图和它相应的自由树（图9-4）。其它还有多种基于图论的表示方法。图3：等高线和相应的自由树7.2.3不规则三角网（TIN）模型尽管规则格网DEM在计算和应用方面有许多优点，但也存在许多难以克服的缺陷：1）在地形平坦的地方，存在大量的数据穴余：2）在不改变格网大小的情况下，难以表达复杂地形的突变现象；3）在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（TriangulatedIrregularNetwork，TIN）是另外一种表示数字高程模型的方法[Peuker等，1978]，它既减少规则格网方法带来的数据穴余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。TIN模型根据区域有限个点集将区域划分为相连的三角面网络，区域中任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常通过线性插值的方法得到（在边上用边的两个顶点的高程，在三角形内则用三个顶点的高程）。所以TIN是一个三维空间的分段线性模型，在整个区域内连续但不可微。TIN的数据存储方式比格网DEM复杂，它不仅要存储每个点的高程，还要存储其平面坐标、节点连接的拓扑关系，三角形及邻接三角形等关系。TIN模型在概念上类似于多边形网络的矢量拓扑结构，只是TIN模型不需要定义“岛”和“洞”的拓扑关系
造成一种无圈的自由树。下图为一个等高线图和它相应的自由树（图 9-4）。其 它还有多种基于图论的表示方法。 B A F C G E H D 图 3：等高线和相应的自由树 7.2.3 不规则三角网（TIN）模型 尽管规则格网 DEM 在计算和应用方面有许多优点，但也存在许多难以克服的 缺陷： 1）在地形平坦的地方，存在大量的数据冗余； 2）在不改变格网大小的情况下，难以表达复杂地形的突变现象； 3）在某些计算，如通视问题，过分强调网格的轴方向。 不规则三角网（Triangulated Irregular Network, TIN）是另外一种表示 数字高程模型的方法[Peuker 等，1978]，它既减少规则格网方法带来的数据冗 余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。 TIN 模型根据区域有限个点集将区域划分为相连的三角面网络，区域中任意 点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常 通过线性插值的方法得到（在边上用边的两个顶点的高程，在三角形内则用三个 顶点的高程）。所以 TIN 是一个三维空间的分段线性模型，在整个区域内连续但 不可微。 TIN 的数据存储方式比格网 DEM 复杂，它不仅要存储每个点的高程，还要存 储其平面坐标、节点连接的拓扑关系，三角形及邻接三角形等关系。TIN 模型在 概念上类似于多边形网络的矢量拓扑结构，只是 TIN 模型不需要定义“岛”和“洞” 的拓扑关系
有许多种表达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）
该方法将重要点的选择作为一个优化问题进行处理。算法是给定一个格网DEM和转换后TIN中节点的数量限制，寻求一个TIN与规则格网DEM的最佳拟合。首先输入整个格网DEM，迭代进行计算，逐渐将那些不太重要的点删除，处理过程直到满足数量限制条件或满足一定精度为止。具体过程如下（图4）：1）算法的输入是TIN，每次去掉一个节点进行迭代，得到节点越来越少的TIN。很显然，可以将格网DEM作为输入，此时所有格网点视为TIN的节点，其方法是将格网中4个节点的其中两个相对节点连接起来，这样将每个格网部分成两个三角形。2）取TIN的一个节点0及与其相邻的其它节点，如图4所示，0的邻点（称Delaunay邻接点）为A，B，C，D，使用Delaunay三角构造算法，将O的邻点进行Delaunay三角形重构，图4中实线所示。3）判断该节点0位于哪个新生成的Delaunay三角形中，如图4为三角形BCE。计算O点的高程和过O点与三角形BCE交点O’的高程差d。若高程差d大于阈值de，则0点为重要点，保留，否则，可删除。de为阈值。4）对TIN中所有的节点，重复进行上述判断过程。5）直到TIN中所有的节点满足条件d>de，结束。图4：DH方法转换格网DEM成TIN（左图虚线为以O为中心的Delaunay三角形，实线为新生成的Delaunay三角形右图为高差的计算[注意：此图描述了三维空间]】两种方法相比较[Lee，1991]，VIP方法在保留关键网格点方面（顶点、凹点）最好：DH方法在每次丢弃数据点时确保信息丢失最少，但要求计算量大。各种方法各有利弊，实际应用中根据不同的需要，如检测极值点，高效存储，最小误差，可以选择使用不同的方法。7.3.5等高线转成格网DEM
该方法将重要点的选择作为一个优化问题进行处理。算法是给定一个格网 DEM 和转换后 TIN 中节点的数量限制，寻求一个 TIN 与规则格网 DEM 的最佳拟合。 首先输入整个格网 DEM，迭代进行计算，逐渐将那些不太重要的点删除，处理过 程直到满足数量限制条件或满足一定精度为止。具体过程如下（图 4）： 1）算法的输入是 TIN，每次去掉一个节点进行迭代，得到节点越来越少的 TIN。很显然，可以将格网 DEM 作为输入，此时所有格网点视为 TIN 的节点，其 方法是将格网中 4 个节点的其中两个相对节点连接起来，这样将每个格网剖分成 两个三角形。 2）取 TIN 的一个节点 O 及与其相邻的其它节点，如图 4 所示，O 的邻点（称 Delaunay 邻接点）为 A，B，C，D，使用 Delaunay 三角构造算法，将 O 的邻点进 行 Delaunay 三角形重构，图 4 中实线所示。 3）判断该节点 O 位于哪个新生成的 Delaunay 三角形中，如图 4 为三角形 BCE。计算 O 点的高程和过 O 点与三角形 BCE 交点 O’的高程差 d。若高程差 d 大于阈值 de，则 O 点为重要点，保留，否则，可删除。de为阈值。 4）对 TIN 中所有的节点，重复进行上述判断过程。 5）直到 TIN 中所有的节点满足条件 d>de，结束。 图 4：DH 方法转换格网 DEM 成 TIN （左图虚线为以 O 为中心的 Delaunay 三角形，实线为新生成的 Delaunay 三角形； 右图为高差的计算[注意：此图描述了三维空间]） 两种方法相比较[Lee，1991]，VIP 方法在保留关键网格点方面（顶点、凹 点）最好；DH 方法在每次丢弃数据点时确保信息丢失最少，但要求计算量大。 各种方法各有利弊，实际应用中根据不同的需要，如检测极值点，高效存储，最 小误差，可以选择使用不同的方法。 7.3.5 等高线转成格网 DEM