数字地形模型.ppt

DEM表示方法 数学方法 用数学方法来表达 可以采用整体拟合方法 即根据区域所有的高程点数据 用傅里叶级数和高次多项式拟合统一的地面高程曲面 也可用局部拟合方法 将地表复杂表面分成正方形规划区域或面积大致相等的不规则区域进行分块搜索 根据有限个点进行拟合形成高程曲面 DEM表示方法 线模式 等高线是表示地形最常见的形式 其它的地形特征线也是表达地面高程的重要信息源 如山脊谷底线等 点模式 用离散采样数据点建立DEM是DEM建立常用方法之一 数据采样可按规则格网采样 可以是密度一致的或不一致的 可以是不规则采样 如不规则三角网 也可以有选择性地采样 采集三峰 洼坑 边界等重要特征点 图形表示法 DEM表示方法 DEM主要表示模型 规则格网 通常是正方形 也可以是矩形 三角形等规则格网 规则格网将区域空间切分为规则的格网单元 每个格网单元对应一个数值 数学上可以表示为一个矩阵 在计算机实现中则是一个二维数组 每个格网单元或数组的一个元素 对应一个高程值 规则格网模型 DEM主要表示模型 规则格网的高程矩阵 可以很容易地用计算机进行处理 它还可以很容易地计算等高线 坡度坡向 山坡阴影和自动提取流域地形 使得它成为DEM最广泛使用的格式 格网DEM的缺点是不能准确表示地形结构和细部 为避免这些问题 可采用附加地形特征数据 如地形特征点 三脊线 谷底线 断裂线 以描述地形结构 DEM主要表示模型 格网DEM的另一个缺点是数据量过大 给数据管理带来了不便 通常要进行压缩存储 DEM数据的无损压缩可以采用普通的栅格数据压缩方式 如游程编码 块码等 但是由于DEM数据反映了地形的连续起伏变化 通常比较 破碎 普通压缩方式难以达到很好的效果 可以采用哈夫曼编码 DEM主要表示模型 等高线模型表示高程 高程值的集合是已知的 每一条等高线对应一个已知的高程值 一系列等高线集合和它们的高程值一起就构成了一种地面高程模型 等高线模型 DEM主要表示模型 等高线模型 等高线通常被存成一个有序的坐标点对序列 可以认为是一条带有高程值属性的简单多边形或多边形弧段 由于等高线模型只表达了区域的部分高程值 往往需要一种插值方法来计算落在等高线外的其它点高程 DEM主要表示模型 不规则三角网 TriangulatedIrregularNetwork TIN TIN模型具有三个基本要求TIN是唯一的 力求最佳的三角形几何形状 每个三角形尽量接近等边形状 保证最邻近的点构成三角形 即三角形的边长之和最小 DEM主要表示模型 TIN模型根据区域有限个点集将区域划分为相连的三角面网络 区域中任意点落在三角面的顶点 边上或三角形内 如果点不在顶点上 该点的高程值通常通过线性插值的方法得到 在边上用边的两个顶点高程 在三角形内则用三个顶点的高程 DEM主要表示模型 有许多种表达TIN拓扑结构的存储方式 一般来讲 对于每一个三角形 边和节点都对应一个记录 三角形的记录包括三个指向它三个边的记录的指针 边的记录有四个指针字段 包括两个指向相邻三角形记录的指针和它的两个顶点的记录的指针 也可以直接对每个三角形记录其顶点和相邻三角形 DEM主要表示模型 有许多种表达TIN拓扑结构的存储方式 一般来讲 对于每一个三角形 边和节点都对应一个记录 三角形的记录包括三个指向它三个边的记录的指针 边的记录有四个指针字段 包括两个指向相邻三角形记录的指针和它的两个顶点的记录的指针 也可以直接对每个三角形记录其顶点和相邻三角形 DEM主要表示模型 空间数据模型通过空间数据组织和空间数据库对空间对象及其关系进行描述 对空间对象进行提取 空间数据模型有两种分类方法 1 从认知的的角度 分为基于对象 objectbased 的模型 基于网络 networkbased 的模型和基于场 fieldbased 的模型 2 从表达的方式上 分为矢量数据模型 镶嵌数据模型和组合数据模型 DEM主要表示模型 镶嵌数据模型的基本思想是 可以用相互连接在一起的网络来覆盖和逼近空间对象 数字高程模型通常用于刻画具有连续变化特征的空间对象 目前最典型的应用就是通过连续网格单元来实现地形曲面的模拟 应归类于基于场的镶嵌数据模型 DEM主要表示模型 当地形数据呈规则分布或由格网DEM向TIN转换时 其三角剖分与不规则数据域的三角剖分有很大的差异 由于规则格网分布采样数据的特性 对其进行三角形剖分可以有两类方法 1 直接对角线连接三角化 2 Delaunay三角剖分法 DEM主要表示模型 先来简要了解一下与Delaunay三角网密切相关的Voronoi图 Voronoi图又称为Dirichlet镶嵌 tessellation 其概念由Dirichlet于1850年首先提出 1907年俄国数学家Voronoi对此作了进一步阐述 并提出高次方程化简 1911年荷兰气候学家A H Thiessen为提高大面积气象预报的准确度 应用Voronoi图对气象观测站进行了有效区域划分 因此在二维空间中 Voronoi图也称为泰森 Thiessen 多边形 Voronoi图是Delaunay三角网的对偶 现在已经成为计算几何中的一种通用的基本几何结构 Voronoi图 空外接圆准则Delaunay三角形外接圆内部包含其它点的性质被用作从一系列不重合的平面点建立Delaunay三角网的基本法则 Delaunay三角形由三个相邻点连接组成 这三个相邻点对应的Voronoi多边形有一个公共的顶点 这个顶点同时也是Delaunay三角形外接圆的圆心 在进行Delaunay三角形剖分的过程中 每一个三角形都要经过空外接圆检测 目前常用的计算方法是计算三角形外接圆的圆心和半径 然后计算圆心和其他点的距离 通过距离和外接圆半径的比较进行判断 这种判断方法的计算包含了开方 除法 平方等复杂的运算 Delaunay三角网 最小角最大准则有很多种方法可以对三角形进行剖分 无论怎样进行三角剖分 采样点的高程值都是最准确的 就这个层面来看 无论怎样剖分效果差别都不大 但是就其外观的自然性而言 还是能比较出相对较好的一种效果 Delaunay三角网 地形的模拟方法有多种 可以区分为物理模拟和数字模拟两大类 数字模拟又分为数学描述和图形描述两类 其中不规则三角网 TIN 规则格网 Grid 和等高线地形图是三种典型的图形描述方法 随着计算机技术和计算机图形学的发展 人们处理大量地形数据和进行真实表达的能力得以提高 Grid和TIN因其直观易用 更新方便而逐渐成为主流的数字地形模拟方法 本节将重点研究如何应用Grid型DEM数据进行Delaunay三角剖分 D TIN的生成算法 分割合并算法 分割合并算法又称分而治之算法 Shamos和Hoey于1975年最早提出了这种算法 他们将该算法应用到了Vorinoi图的生成中 三年后Lewis和Robinson又将该算法应用到了D TIN的构建中 随后Lee和Schachter Dwyer等相继对Lewis和Robinson的算法进行了改进 Lee和Schachter的改进使其可以适用于无约束数据域的三角剖分 而Dwyer的改进则能处理带约束条件的数据 分割合并算法的基本思想是 首先将各数据点分割成易于进行三角剖分的子集 然后对各子集进行D TIN剖分并进行LOP优化 最后将各个自己建立的D TIN进行合并生成最终的整体三角网 分割合并算法的基本步骤为 第一步 把所有数据点的集合按升序排列 第二步 将数据集分割成点个数大致相等的左右两个子集 并对每一个子集进行如下操作 计算子集的凸壳 以凸壳为数据边界 对每一个子集分别进行D TIN三角剖分并进行优化 找到左右两个子集的凸壳的底线和顶线 并由底线到顶线进行三角网合并 第三步 如果数据集中的数据个数小于给定的阈值 则直接输出三角剖分结果 三角网生长算法 从生长过程的角度 三角网生长算法分为收缩生长算法和扩张生长算法 收缩生长算法是先形成整个数据域的数据边界 凸壳 并以此开始逐步缩小直至形成整个三角网 收缩生长算法与数据点的分布密度有关 实际情况往往比较复杂 例如当边界收缩后一个完整的区域可能会分解成若干个互相独立的子区域 这就增加了三角剖分的复杂性 扩张生长算法与收缩算法过程刚好相反 该算法是从一个三角形开始向外层层扩展 最终形成覆盖整个区域的三角网 对在直线Ax By C 0的同一侧的所有点 x y 实数Ax By C的正负相同 主要步骤为 第一步 生成初始三角形 在数据点中任取一点A 该点一般是位于数据点的几何中心附近 并寻找距离此点最近的点B 两者相连形成初始基线AB 如图2 7所示 利用空外接圆准则或张角最大准则 在数据域中寻找第三点C 从而形成第一个Delaunay三角形ABC 第二步 扩展形成三角网 以初始三角形的三条边为初始基线 利用利用空外接圆准则或张角最大准则寻找能与该三条初始基线形成Delaunay三角形的D E F点 在该过程中要注意 初始边界将整个区域分成两个部分 搜寻第三点一般是在初始三角形另一个顶点异侧范围内进行 例如若初始三角形为ABC 初始边界为AB 第三个顶点为C 能与三角形ABC共用AB边的另一个三角形为ABD D点要位于AB边的另一侧 而不能与C同侧 第三步 重复第二步直到所有的数据处理完毕 三角网生长算法最早由Green和Sibson在Voronoi图中实现 Brassel和Reif后来也发表了类似的算法 McCullagh和Ross通过把点集分块和排序来减少搜索时间 该算法思路清晰 算法简单 但实现效率不高 在该算法基础上有许多改进算法 主要集中在第三点的搜索和三角形全等的判定上 逐点插入算法从构网过程来看 分割合并算法和三角网生长算法属于静态剖分过程 在整个三角网形成过程中 新点的介入并不会破坏已经形成的三角网 而逐点插入算法则是一种动态的构网过程 新点的插入会导致已有的三角网进行改变 该算法最早由Lawson在1977年提出 随后LeeSchachter 1980 Bowyer 1981 Watson 1981 Sloan 1987 Macedonio和Pareschi 1991 Floriani和Puppo 1992 Tsai 1993 等人先后对其进行了改进 逐点插入算法的基本过程为 第一步 定义包含所有数据点的初始包容盒 并对该包围盒进行初始三角剖分 形成矩形包容盒的方法是找出数据域的坐标极值点 然后用这些点形成包容盒 第二步 对所有数据点进行循环 设当前处理的数据点为P 在已经存在的三角网中 查找包含P点的三角形t 将P与t的三个顶点相连 形成t的三个初始三角剖分 再用LOP算法对