（摄影测量与遥感专业论文）TIN模型的构建方法研究.pdf

摘要 摘要 近年来，随着g i s 技术迅猛发展以及在各个领域中的应用不断深入，对d e m 数据的要求越来越高t 矾数据作为d e m 数据的其中一种表达方式，在不同层 次和空间上表达地面复杂地表具有优越性。然而，t i n 数据数据结构复杂，其使 用和管理也较为复杂，而且在数据量很大的情况下运行速度比较慢，这在一定程 度上限制了t i n 的发展。因此，改进t i n 构建模型，提高t i n 构建精度与地形 描述逼真度以及t i n 构建算法效率成为t i n 研究的热点问躁 本文首先对当前常规的t i n 模型构建方法进行了分析，总结其不足，提出了 结合外部有效边界线和内部约束地性线来共同构建t i n 数据的方法。其次对通 过离散商程点数据自动提取出其实际有效的边界，再将离散点数据进行预处理成 栅格数据，应用平面曲率和坡形组合法提取出地面盼蛆性结构线的算法进行了研 究，保证了地形描述的逼真度；最后基于凸包技术，利用内外部约束条件共同构 建更高精度和逼真度的t i n 数据进行了程序实现。 本文主要研究内容如下： 1 分析总结当前构建t i n 的几种常用的方法，并探讨其优缺点。最后选择了 基于“凸壳技术”快速构建的算法，并对凸包算法进行改进以“凹包”即实际的 有效范围线作为起始外部范围，可以有效的提高t i n 在其边缘地带的精度。 2 对离散高程点数据的实际有效边界进行了研究，优化并实现了基于凹包的 有效边界线提取算法，并且在有效边界线提取过程中有效地解决外围点的遗漏和 范围线在复杂区域连接交叉的问题。有效地改进了传统的凸壳边界存在的边界不 真实的问题。 3 分析了从规则格网中提取地性线的方法，并总结其优缺点，根据其优越性， 最后选择结合平面曲率和坡形组合法提取地性线，可通过参数设置调节地性线提 取的宽度使提取的地性线更符合实际地貌情况。 4 基于改进的“凸壳技术”并结合内、外部约束条件，利用a r c o b j e c t s 在 v c + + 6 0 环境设计开发一个t i n 的构建模型的实验系统。并在系统上，利用多 组真实地形数据进行分类对比试验，并进行精度分析验证了本文所提出方法的优 越性。 关键词；数字高程模型、范围线、她性线、不规则三角网 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：聋堡也2 0 0 7 年6 月8 日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布泡括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：盏键超 2 0 0 7 年月d 日 第一章绪论 1 1 研究背景 第一章绪论 在上世纪5 0 年代美国麻省理工学院摄影测量实验室主任c h a i r e s l m i l l e r 教 授首次提出数字地面模型的概念。数字地面模型( d i g i t a lt e 玎a i nm o d e l 简称 d t m ) 是地形表面形态属性信息的数字表达，是带有空间位置特性和地形属性 特征的数字描述。d t m 是定义在某一区域d 上的m 维向量的有限序列，其向量 的分量为地形、植被、矿产资源、土地利用、人口分布等多种信息的定量或定性 的描述。当只考虑d t m 的地形分量时，通常被称为数字商程模型d e m ( d i g i t a l e l e v a t i o nm o d e l ) t j 。 目前d e m 已经成为地理信息系统( g i s ) 的重要组成部分，g i s 的许多分 析功能是以d e m 为基础。d e m 包含了丰富的地形特征信息，比如描述地表高 低起伏的高程、坡度、坡向等地貌信息。 数字高程模型一般包括规则格网模型( g 甜d ) 、等高线描述法模型、不规则 三角网( t r i a n g u l a t e d i r r e g u l a r n e t w o r k ，t i n ) 模型。 规则格网模型是人们普遍采用的一种d e m 模型。该模型利用固定大小的格 网蒙在地形图上，逐格读取每一格代表的高程值构成d e m 。这种2 维矩阵数据 排列，结构简单，容易理解。便于计算坡度、坡向、描述河流的流域范围等，同 时也便于计算机的处理，所以规则格网成为最常见的d e m 。但是它的缺点也是 显而易见的，主要就是存储量大。在一幅栅格d e m 中，由于格网的选取一般比 较适中，这样在地形平坦地区容易出现大量冗余数据，而在地形起伏较大地区采 样点不足，不能准确反映地形的突变“1 。 等高线描述法模型可以看作一系列逼近的嵌套多边形，数字化的等高线在描 述坡度阴影或三维着色图时显得无能为力，所以通常将它转化为规则格网或不规 则三角网。 不规则三角网模型( 1 1 n ) 将测量采样点连接成一系列连续的三角形，三角 网的形状和大小取决于不规则分布的采样点的密度和位置。所以t i n 模型能以 不同层次的分辨率来描述地形表面，在某一特定分辨率下能以较少的空间和时间 更加精确地表示复杂地地表t i n 模型与g r i d 模型的区别在于能随地形的起伏 变化而改交采样点的密度和决定采样点的位置，从而能够克服平坦地区产生数据 冗余问题，压缩数据，节省存储空间。同时t i n 模型能够更好的顾及断裂线、 构造线、山脊线、山谷线、地形变化线等地性特征线，从而更精确合理地表达复 河海大学硕士论文 杂地表形态。 三种模型各有优缺点，根据工程的需求采用相应的d e m 模型，本文主要对 t i n 模型进行研究。 1 2 国内外研究现状 在数字高程模型( d e m ) 中，t i n 模型较规则格网( g r i d ) 更能顾及到地 性线，能够较真实地模拟复杂的地形表面，精度高。数据冗余小，存储效率高， 适合多层次表达。目前在构建t i n 的工作中，广泛采用的是d e l a u n a y 三角网， t i n 的数据结构复杂，使用和管理复杂。因此构建t i n 主要围绕两个方面：一是 如何改进模型描述地形的逼真度和精度，二是如何提高构建t i n 算法的运行效 率 如何快速、高效地构建d e l a t m a y 三角网，提高算法的效率和效果一直是众 多学者研究和关注的焦点。d e l a u n a y 三角网是互相邻接且互不重叠的三角形的集 合，每个三角形的外接圆内都不包含其他顶点。d e l a u n a y 三角形由三个相邻点连 接而成，与这三个相邻点相对应的v o r o n o i 多边形有一个公共的顶点。 在用三角网来拟合地形表面时，对三角网有三项基本要求： ( 1 ) t i n 模型d e l a u n a y 三角形是唯一的； ( 2 ) 尽量使三角形有最佳的几何形状，尽量使每个三角形都接近等边三角形； ( 3 ) 确保最邻近的点构成三角形，并使三角形的边长之和最小。 基于上述三项基本要求，在各种三角网中，d e l a u n a y 三角形在地形拟合方面 最佳。d e l a u n a y 三角网具有“圆规则”或“最大最小角规则”，即任意三角形的 外接圆不包括其它节点，从而最大可能地避免了尖锐内角的出现，在制图综合中 可以利用该模型进行目标问邻近关系搜索和冲突的探测( w a r e ，e ta l ，1 9 9 7 b ；p e n g ， 1 9 9 5 ) c a o 从国内外这几十年来关于d e l a u n a y 三角网的研究算法来看，出现了较多构 建d e l a u n a y 三角网算法，但主要研究重点集中在四种算法及其优化和改进。四 种方法为：逐点插入法、三角网生长法、分治算法、凸包算法。1 。 ( 1 ) 逐点插入法 首先定义一个包含所有数据点的初始多边形：从数据集中任意选择一个点 ( 如a ) ，插入到初始多边形中建立初始三角网；然后按以下步骤进行迭代计算。 直至所有数据点均被处理：插入一个离散采样点p ，在初始三角网中找出包含 p 的三角形t ，把p 与t 的三个顶点相连，生成3 个新的小三角形；o 用局部优 化法( l o c a lo p t i m i z a t i o np r o c e d u r e ，l o p ) 从里到外优化三角网，确保所有内插 2 第一章绪论 后的三角网为d t i n 。该算法虽然实现较简单、占用内存较小、但它时间复杂度 差、效率较低，所以目前较少使用。 图l l 逐点插入法的原理 ( 2 ) 三角网生长法 首先找出离散点集中相距最短的两点，连线成为d - t i n 的初始基线；然后 按d - t i n 的判断法则找出包含此基线的d e l a u n a y 三角形的第3 端点，若该端点 位于基线的右侧；连接新点与原来两点形成两条新边；再按d - t i n 的判断法则 找出包含此两边的另外两个d e l a u n a y 三角形的第3 端点；依次循环处理所有新 生成的边，直到所有离散点均成为d - t i n 的端点。该算法的大部分时间花费在 搜索符合要求的给定基线的邻域点过程中，效率低，目前较少使用。 ( 3 ) 分治算法 s h a m o s 和h o e r y 基于v o r o n o i 图的构建，提出分治算法的思想。l e w i s 和 r o b i n s o n ( 1 9 7 8 ) 将分治算法的基本思想用于d - t i n 的构建。算法采用递归分割 点集直至每个子集中仅含3 个离散点而形成三角形的方法，经自下而上逐级合并 生成最终的三角网。此后，- i ：2 e 和s c h a c h t e r ( 1 9 8 0 ) 改进、完善了l e w i s 和r o b i n s o n 的算法，首先将数据排序，分成两个互不相交的子集，在每个子集中构建t i n 后，然后将两个t i n 合并生成最终的d - t i n ；o w y e r ( 1 9 8 7 ) 对分治算法进一步 改进，将数据分成垂直条块，然后用相交边界将条块再一次细分成区域，应用带 约束条件的l a w s o nl o p 将对角线进行交换，从而可以处理带约束条件的数据。 不同的实现方法主要区别于点予集的划分和子网的合并方法的不同。 该算法比较高效，但相对而言复杂度较高，但由于需要深度递归对计算机的性能 要求较高，同时对于多约束条件存在下，该算法使分割难以实现。 ( 4 ) 凸包算法 凸包( c o n v e x h u l l ) 是由包含二维平面上的点集中所有点的最小凸多边形。 首先将x m j 。、y m i 。、) 【| l i 。、y 一的点连接起来作为初始凸包，并按逆时针方向存储 于链表中；然后对凸包进行修改，寻找位于链表中相邻的两点构成线段右侧距离 最大的点，点若存在，将点插入链表中上述两点之间，形成新的链表；否则，不 河海大学硕士论文 插入。以此循环，直至所有点被包含在内，形成最终凸包。( 如图1 2 ) 所示该 算法可以有效控制t i n 范围线，从外围向内部开始构建t i n 。该算法的时间复杂 度下限为o ( o i o g l l ) ，运行效率较高。 ( a ) 建立初始凸包( b ) 修改凸包( c ) 形成最终凸包 图1 2 凸包建立过程 在这四种t i n 生成算法中，逐点插入法实现简便，但是时间复杂度差，运行 速度慢，同时由于它在开始构建的第一步使用一个包含所有点的多边形，这很容 易导致在t i n 模型边界地带引起失真，降低模型的逼真度和精度：三角网生长法 能较好的解决了时问复杂度的问题，但是易出现退化现象，从而影响了其生成模 型的可靠性，这使对逼真度和精度方面的影响难以估计；分治算法是采用深度递 归方法，实现较难，同时运行时需占有大量内存空间。该算法首先对矢量数据点 进行分割，然后在进行分别构建模型，最后再统一合并。这虽然解决了模型构建 过程中的时间问题但是由于数据分割也破坏了矢量数据的整体性，地形数据的特 征信息容易损失，从而影响了t i n 的精度和逼真度。凸包算法是设定一个包含所 有矢量数据的凸包，然后由外向内进行构建，由于只需寻找第三点的时间，有良 好的时间效率，但是由于设定的初始凸包不一定符合实际地貌，对内也没有地性 线约束也会带来地形失真。该算法相比其他三种算法比较占优，所以本文选择该 算法作为基础进行改进，首先引入符合实际有效范围线作为外部约束，同时也选 取地性线对内进行约束，提高算法的精度和逼真度。同时也使时间效率能较好的 得到保证 在凹包提取的算法中有以下两种为主要代表，李江雄等人提出采用格网剖分 法，其步骤为：首先找到点集的初始包围盒，然后将一定间隔的矩形网格将包围 盒剖分，该网络包含狈4 量点的格网进行保留，形成外围边界。”。但是这种方法在 实际使用过程中只能适合点位疏密程度大致相等的情况，而实际采样点数据的间 隔不可能是等距的，这样就带来一个问题，在点位密集的区域采样一定宽度的格 网，而在点位稀疏的区域一定不合适，同理适合稀疏区域的格网也不适合点位密 集的区域，两者不能兼顾，算法具有一定的局限性。 周秋生等人提出四步法，( 1 ) 确定初始边界；( 2 ) 边界膨胀；( 3 ) 计算边界 线段的最大长度；( 4 ) 边界收缩。其一，算法过程中边界膨胀的过程中，其算法 4 第一章绪论 选用了角度比较法。即寻找点与边夹角 z 3 1o 该算法选用角度进行了比较，并未 对点在线段的外侧这一情况进行判断，这样就会带来寻找的点不是位于线段内侧 所真正要寻找到的点，造成连接线出现交叉的情况，严重时会出现死循环的情况。 其二，在边界收缩的情况过程中，该算法只考虑了在线段的左侧搜索点，而在实 际搜索过程中这样会造成部分外围点的遗漏。这样形成的凹包可能不是包含所有 点的外围线。 本文采用周秋生的四步法，但对其中的部分算法进行了优化和改进。点到线 段距离的远近作为的约束判断条件，同时在构建凹包的过程中，由于点都包含在 逆序凸包的左侧，所以只需要判断点位于线段的非右侧就可以，这样做的好处是 便于判断，同时在凹包连接的过程中位于凸包线段上的点连接入边界中，从而保 证了外围点加入，避免了在复杂情况下外围遗漏点的情况使得提取的凹包为包 含所有外围点的范围。在点寻找过程中，为了减少循环遍历时间和判断次数，采 用按新加入点进行逆序循环而不是按原始初始点进行循环。这样可以减少大量的 循环次数和判断条件，从而提高了算法的运行效率。 在构建t i n 时，若需将约束线段( 如地性线) 作为约束条件添加到三角网中， 这时t i n 便成为带约束条件的t i n 。带约束条件t i n 的构建方法与前面介绍的四 种构建t i n 的方法相似，只是带约束条件的t i n 考虑了预先给定的约束条件。 将约束条件添加到t i n 中，形成最终的带约束条件的t i n 可归纳为以下五种 方法： 1 约束图法：l e e 和l i n ( 1 9 8 6 ) 提出了基于约束图计算带约束条件的t i n 构造方法。约束图是用图论方法表示一个几何约束系统的方法。几何约束图定义 为图g = ( v ，e ) ，其中，v 代表几何约束问题的集合元素的集合；e 代表几何约束问 题的几何约束的集合；g 称为几何约束问题的约束图。他们首先用o ( 砰) 的时间 计算约束数据域的可见性图，然后用o ( n 2 ) 的时间检测优化可见性图并形成最终 的带约束条件的t i n 数据啪。 2 分治算法：l e e 和s c h a c h t e r ( 1 9 8 0 ) 提出无约束条件的t i n 分治算法， 后经c h e w 将其推广到带约束条件的t i n ，j e o 和w a n g 也提出了相类似的算法。 正如前面提到的一样，分治算法虽然执行效率较高，但对约束条件的存在使得分 割过程的实现变异常困难瑚。 3 加密算法；b o i s s o n n a t 是将约束数据转换成为非约束数据，即对约束线 段按空外接圆规则进行加密，然后对加密后的数据进行无约束t i n 的构建。这种 算法虽然简单易实现，但是加密点的存在不但加大了数据量，而且也改变了原始 数据集” 4 s h e l l 三角化算法：p i e g l 和r i c h a r d ( 1 9 9 3 ) 提出由任一约束线段开始， 以可见性和空外接圆特性为准则寻找可扩展的第三点，其实质是前面提到的三角 河海大学硕士论文 网生长法在约束数据域中的推广“1 5 两步法：首先对约束数据集建立无约束t i n 的构建，然后再引入约束线 段进行调整。b e r n a l 、s l o a n 提出在初始三角网建构过程中不区分约束和无约束 点，而是在约束线段调整过程中，使三角网满足约束线段条件；s l o a n 利用连续 的对角线交换法实现约束线段的潜入，要求可交换对角线的四边形是严格凸四边 形而这一点在实际应用中难以满足。后来f l o r i a n i 提出更加灵活的算法，只 建立无约束t i n ，然后在初始t i n 中插入约束线段。 根据比较以上5 种方法的优缺点，本文结合了两步法中的v l o r i a n i 和s l o a n 方法，利用地性线来改善t i n 构建的逼真度。 1 3 研究目的和意义 数字商程模型 d e m ) 作为地理信怠系统数据库中最重要的空问地理信息 的数据模型，显然d e m 质量的好环直接关系到通过d e m 空间分析成果的精确 性。在地形复杂地区，t i n 模型比其他d e m 数据模型( 比如等高线、栅格数 据) 更能较好顾及到地形特征，能以较少的空间数据模拟复杂的地形表面，是 种比较占优的d e m 数据模型，研究t i n 模型的优化具有重大意义。本文就围绕 t i n 模型的描述地形的逼真度、精度和t i n 模型算法的运行效率，这三个方面做 一些探讨。 随着计算机的运算速度越来越快、存储空闻越来越大，对于算法的运行效率 方面的要求不像以前那么重要。加上在整体g i s 系统中采集数据构建t i n 的工 作属于一次性的工作。对时间的要求不像其它工作那么严格。因此提高算法的逼 真度和精度成为一个重要的研究课题。在计算机技术迅猛发展的今天。算法在考 虑到逼真度和精度的同时，进一步要考虑到效率。在同等的逼真度和精度的情况 下，当然算法耗时越少越好 寻找一种既适合一般地区也适合复杂地带的方法，提高t i n 逼真度且运算 效率又高的算法，在地形三维模拟领域内是一个十分重要的研究问题。 1 4 本文的研究思路与内容 d e m 在地球环境科学的所有分支学科以及工程领域，军事领域都有着广泛 的应用。基础d e m 数据在g i s 研究和应用过程中尤为重要，但在现有的条件下， 基础d e m 数据在许多领域还不能完全满足实际应用的要求。 本文研究的主要思路是充分利用反映地貌特征的地性线和能满足精度要求 的有效范围线来构建1 1 n 网。为了实现这一想法，达到预期目的，主要研究工 作如下： 6 第一章绪论 1 理解t i n 算法以及相关的数学理论，并分析比较不同数学解决方法的优 劣，最后结合地形特征，提出适合的解决方案。 2 对离散高程点数据的实际有效边界进行了研究，优化并实现了基于凹包的 有效边界线提取算法，并且在有效边界线提取过程中有效地解决外围点的遗漏和 范围线在复杂区域连接交叉的问题。有效地改进了传统的凸壳边界存在的边界不 真实的问题。 3 分析了从规则格网中提取地性线的方法，并总结其优缺点。根据其优越性， 最后选择结合平面曲率和坡形组合法提取地性线，可通过参数设置调节地性线提 取的宽度使提取的地性线更符合实际地貌情况。根据结合地性线及有效范围构建 t i n 算法，开发实验模型。该实验数据接口和图像显示部分采用a r c o b j e c t s 接口， 算法核心计算部分采用c 抖编写。 4 对实验的结果进行分析和评价，利用多组真实地形数据进行分类对比试 验，并进行精度分析验证了本文所提出方法的可行性和有效性。 其技术总体路线如图1 3 所示： 图1 3t i n 建立基本流程 本论文主要内容如下： 第一章绪论：总结当前t i n 算法的发展，分析算法的现状与不足，提出了结 合地性线和有效范围线来构建t i n 数据，并简要阐述了这一研究的现实意义。 第二章离散点有效范围的提取：简述有效范围选取的意义，研究对于凹包的 处理及有效范围的提取 第三章地性线的自动提取：总结分析了地性线提取的算法。优化各种影响因 子，使地性线的自动提取的误差尽量小，并对特殊地带的处理方法进行讨论。 第四章结合地性线以及有效范围构建t i n 以及精度分析：基于a r c o b j e c t s 4 - v c 6 0 环境实现t i n 的构建实验是本研究的核心，也是验证本文提出方法可行 性的关键。本实验通过检查点法和剖面法两种方法进行检验。验证此方法的可行 7 河海大学硕士论文 性，且在精度上比常用的t i n 方法有某种程度的提高。 第五章结论及展望：总结本文主要工作和内容以及在t i n 模型构建研究、实 验系统设计和实现过程中存在的不足，展望今后进一步改进的工作。 第二章离散点有效范囝的提取 第二章离散点有效范围的提取 本章将主要介绍由离散的高程采集数据点提取t i n 模型边界有效范围的方 法。首先介绍离散点的凸壳精细到离散点凹包的处理过程，然后按离散数据点的 采样密度和测量精度等指标进行有效范围的提取，并对提取过程中影响提取效果 的影响因子进行讨论。研究离散点有效范围的提取问题就是确定由离散点所表达 的区域形状。 2 1 范围线选取的意义 在实际测绘工作中，通常按照地形变化特征来进行高程数据点的采集，获得 的离散高程点成不规则分布，这导致了测绘采样点的区域边界也成不规则分布。 常见的边界形状多为凹多边形。如果用简单的包含所有采样点的凸壳模型作为边 界来表示实际测绘边界为凹多边形的模型，则会在凹进区域内，由于没有采样数 据点而将产生精度失真。这样构成t i n 模型必然在边界及其在边界附近影响t i n 模型的精度。所以就需要根据边界构成的精细程度和不确定性，制定提取的边界 标准，能自动识别提取出模型边界“。 2 2 离散点边界识别 在数字高程模型的采样过程就是确定何处的点要测量记录的过程，这个过程 取决于三个要素：数据分布( 包括位置、结构) 、数据密度和数据精度，即数字 高程模型数据源的三大属性( 李志林等，2 0 0 3 ) i o l 。 1 数据分布 数据分布是指采样数据位置及分布。位置可由直角坐标系统中的x 、y 坐标 值决定。而布点的形式一般如表2 1 所示1 ： 表2 1 数据分布 二维规则格网 按矩形格网分布采样数据点 规则分布 按正方形格网分布采样数据点 按三角形分布采样数据点 特殊规则分布 按六边形采样数据点 维分布 剖面 不规则分布 沿等高线采样数据点 链表分布 沿断裂线等特征线分布采样数据点 随机分布随机分砸采样点 9 河海大学硕士论文 由表2 1 可知，采样点的分布分为规则和不规则两类。规则二维数据由规则 格网采样或渐近采样生成，其形状有矩形格网、正方形格网或由两种形成的分层 结构等，其中正方形格网数据最为常用。由于各方面的缺点，特殊的规则形状如 三角形或六边形等应用不如剖面数据或规则格网数据在实际中使用的广泛。不规 则分布，将其分为两类：一类是没有特征的随机分布数据，按照一定概率随机分 布，没有任何特定的分布形式；另一类是具有特征的链状数据，按照一定的特征 线分布而采样的数据，例如，沿河流、断裂线、山脊线、山谷线等特征线而采集 的数据。 对于地形图数字化、野外测量或摄影测量，一般采用如下6 种测量方法n 1 1 ： ( 1 ) 沿等高线采样：在地形复杂的陡峭地区较为常用，而在地形平坦地区不 宜使用。 ( 2 ) 规则格网采样：规则格网采样能确保所采集数据的平面坐标具有规则格 网形式。通过规定的x 和y 轴方向的间距形成平面格网，在立体模型上测量格网 点上的高程。 ( 3 ) 剖面法：与规则格网法类似，它们之间的区别在于，格网法测量是在格 网的两个方向上都规则采样，而在剖面法中，只沿剖面一个方向上进行采样。通 常点以动态测量，速度较静态采集的规则采样快，但其精度却比规则采样低。 ( 4 ) 渐近采样( m a k a r o v i c 。1 9 7 3 ) ：是与地形相结合，平坦地区采样相对较 少，地形复杂地区采样相对较多的一种采集方法。虽然能减少固有数据的数据冗 余问题，但这种方法仍存在，在地形突变的复杂地区数据仍有较高冗余，且跟踪 路径太长，时间效率低的缺点。 ( 5 ) 选择性采样：为了准确反映地形，可根据地形特征进行选择性的采样， 例如，沿山脊线、山谷线、断裂线以及离散特征点( 山顶点) 等进行采集。这方 法突出的优点在于只需采集少量的点便可描述地形特征实际上，没有一种采样 程序单纯以这种方法采样的，这种方法并不常用。 ( 6 ) 混合采样：是一种将选择采样与规则格网采样相结合或是选择采样与渐 近采样相结合的采样。该采样方法在地形突变处( 如山脊线、山谷线、断裂线等) 以选择采样的方式进行，然后将这些特征线和特征点加入到规则格网数据中。在 实际的测量过程，这种混合采样能解决实践遇到的问题0 1 。 2 数据密度 数据密度是指采样数据的密集程度，与研究区域的地貌类型和地形复杂程度 有关。数据点的密度有多种表现形式，比如两相邻点之间的距离、单位面积内的 点数、截至频率、单位线段上的点数等。 3 数据精度 采样点的精度与数据源、数据采集方法、数据采集仪器以及数据采集人员有 1 0 第二章离散点有效范围的提取 密切关系。不同的数据源有着不同的特点，因此有着不同的精度。各种数据源的 精度从高到低一般是野外测量、影像测量、地形图扫描及数字化。但有些影像数 据源的采样精度还是比较高的，如激光扫描、干涉雷达。 在实际测量中，一般采用混合采样方法按地形分布变化特征以一定的数据密 度和精度进行高程数据点的采集，获得的离散数据点成不规则分布，如图2 1 描述的是某区域的测绘高程采样点分布情况。离散点的边界由测绘采样点的所表 达的区域形状来表示。 如果用简单的包含所有采样点的凸壳模型来表述采样点的边界则如图2 2 所示。显然，如果单纯将这样的凸壳作为采样点区域的边界，则在区域周边地区 由于缺少采样点会产生较大的边界失真。为了得到实际采样点的边界形状，必须 对离散点所表达的边界进行进一步的精细。但是由于测绘采样点实际情况复杂， 再者人的主观认知上的差别，这将导致边界的结果千差万别。图2 3 ( a ) 。( b ) 是由两人识别的结果。 图2 1 不规则离散点分布 图2 2 离散点的凸壳 ( f t )( b ) 图2 3 不同人识别的结果 由上述图识别离散点边界结果可知，不同的结果反映了连接边界的精细程度 上的差别。图2 2 离散点的凸壳是精细化程度最低的边界。图2 3 ( a ) 的边界较 图2 2 离散点凸壳精细度高，而与图2 3 ( b ) 相比较，其精细化程度又低离散 河海大学硕士论文 点边界的精细化程度是一个不确定性的概念，若仅仅是以识别边界结果的定性衡 量标准，并且边界的精细程度并不一定是越高越好。精细化程度太低，将导致包 含大量非测量区域，这必将影响t i n 的精度；精细化程度太高，将导致遗漏某些 测量区域，这也将影响t i n 精度的损失。所以边界的精细化程度不是人为随意取 定的，而应根据测量的实际精度来确定，这样的精细程度才能与实际地貌相吻合。 为减小人为判断失误和减少工作量，需要设计出离散点边界自动提取算法。 这需要对边界的精细化程度给出定量的描述。由图2 3 ( a ) 和2 3 ( b ) 可知，边界 的精细程度不仅与形成区域形状的周长和面积有关，而且与组成边界线段的边数 和长度有关。区域边界的精细化程度越低。边界线段的边数越少，边界线段的长 度越长；区域边界的精细化程度越高，边界线段的边数越多，边界线段的长度越 短。由上分析得出，可选用边界线段的长度作为衡量区域边界精细化程度的标准。 在实际数字地面模型的采样过程中，我们得到的采样点分布以一定的精度和 密度成不规则分布的。而不规则的采样点的密度是不均匀的，但按照测量规范， 相邻采样点之间的平均距离应满足一定的要求。边界线段的长度应与相邻采样点 之闻的平均距离有关。设d 为相邻采样点之间的平均距离， 设d 。为边界线段 的最大长度，则 “。= k x d ( 2 - 1 ) 其中，k 为边界搜索系数。若k 值取得越大，边界线段越长，边界的精细化 程度越低；k 值取得越小，边界线段越短，边界的精细化程度越高。 2 3 边界提取算法实现 2 3 1 确定初始边界 设采样点的坐标为：“，只) i = l ，2 ，n 计算采样点坐标的极值 ( 2 2 ) 得到4 个点a ，b ，c ，d ( 特殊情况可能得到3 或2 个点) ，如图2 4 所示由 此四个点构成一个多边形作为采样点的初始边界。该多边形为凸多边形，边界点 以逆时针的顺序排列组成p o l y l i n e 作为边界线 芝 钏 一一黧 臣 第二章离散点有效范围的提取 2 3 2 求区域凸壳 l 圉2 4 不规魁离散点初始边界 1 凸壳技术相关定义 凸壳的数学定义，设s 是平面上非空点集，p l 、p 2 是s 中任意两点，如果 p 1 、p 2 两点的相连线段全部位于点集s 中，那么称s 为凸壳。 对一个散乱点集( 不共线) 生成三角网( t i n ) 时，最= 5 i - n 边所构成的多边形 是凸多边形，这个凸多边形成为这个点集的凸壳，并且规定组成凸壳的所有有向 边( 称为凸壳边) 必须是首尾相接的当凸多边形是逆时针时称为逆时针凸壳， 凸多边形是顺时针时称为颐时针凸壳。 2 凸壳的实现过程 离散采样点分布区域的凸壳是指包括该区域所有离散采样点的最小凸多边 形。沿初始边界的走向，在每一条边界线( 妞a 8 边) 的右侧搜索一点p ，使p 点与a p 和p b 两边的夹角_ _ a p b 最小。若p 点找到，则将p 点插入点集中a 点和 b 点之间。即用两条边界线段( a p 和p b ) 代替原来的一条边界线段( a b ) ；若这样p 点不存在 即边界线右侧没有离散点) ，则这条边界线段保存原样不变 如此按逆时针在初始多边形的每条边界线段上搜索一周后，得到一些新的边 界点( p ，q ，r ) ，形成新的边界多边形。如图2 5 所示重复循环这一过程，边 界不断向周边膨胀，直至搜索一周后边界右侧没有新的离散采样点为止，结束 循环。这对边界已经澎胀为离散采样点的凸壳。 河海大学硕士论文 c b 图2 5 不规则离散点边界膨胀 在新边界点的搜索过程中为了提高三角网的连结效率，就需要在每次向凸壳 边界中增加新点时，设法减少新加入点与已有凸壳边之间的矢量乘积的判别次 数。这就必然需要在每次判别过程中，尽量减小凸壳边判断数目和搜索点的数目。 这样可以有效的缩短搜索时间，提高搜索效率。沿初始固定凸壳边的走向，在每 一条边界线段( 如a b 边) 建立以起始点a 点为圆心a b 边界线段的长度为半径建 立一个点缓冲区。在这个点缓冲区中根据判别新加入点与凸壳边的位置关系函数 和判断点与边的夹角函数判别出在边界线段( 如a b 边) 右侧的一点p 。并使p 点 与a b 边的距离最远。 这样按逆序在初始边界搜索一周。发现所有待加入点都加入新点形成新的边 界线。重复循环这一过程，直到搜索一周后边界右侧没有点可加入为止，这样离 散点的凸壳建好 3 凸壳实现中运用的算法和函数 ( 1 ) 判断点与边的距离远近 设两边蜀为已知点a 和b 组成，s 2 为判断点与a 点组成，s 。为判断点与b 点组成；通过分析可得p 点到& 的距离为h ： h = 2 x p ( p s 。) q s 2 ) ( 1 - s o s i ( 2 3 ) 1 4 第二章离散点有效范围的提取 式中p = ( s + s 2 + q ) ，2 从公式( 2 3 ) 可得出点到边的距离，这个判断一个点与边的距离远近时只 要通过三点的x 和y 平面坐标值计算三边的距离就可判出断出该点到边距离。 ( 2 ) 判别毅加入点与凸壳边的位置关系 a 对于逆时针凸壳，只有当新加入点位于凸壳的右侧时，新加入点才能与这 条凸壳边构成合理的三角形，成为新的边界点( 如图2 6 中，点f 只有位于凸壳 边b c 的右侧才能与已有凸壳边形成新的凸壳边) 。 b 对于顺时针凸壳，只有当新加入点位于凸壳边的左侧时，新加入点才能与 这条凸壳边构成合理的三角形( 如图2 7 中，点f 只有位于凸壳边c b 的左侧 才能与已有凸壳边形成新的凸壳边) 。 、f ， a = x j + y l j + o k ，凸壳边起始点到新加入点b f 构成的矢量为 丑= x 2 i + y 2 j + o k ( 其中f ，瘌詹分别是三维空间的而巾z 方向的单位矢量 而= t 一心，y l = 儿一“，屯= x 一，y 2 = j ，一儿) ，则矢量月和矢量口的 4 丑= l 主；j ：氧= 。；+ 。，+ g 。y ：一x ：，。，t c z a ， 根据矢量乘积的右手定理x l y ：一x ：y 。的值可以用来表示两个矢量的相对空 可海大学硕士论文 间位置关系，进而可以获得新加入点与有向凸壳边的位置关系，如下： ( 2 - 5 ) ( 3 ) 判断点是否在凸壳边的内侧 在进行判断点与凸壳边的位置关系前先要判断点是否在凸壳边的内侧。如下 图所示： 1 6 f p t i qp t 2 图2 8 点与线段的关系 和p f 2 构成直线的斜率： k = ( p t 2 一p t l y ) ( p t 2 一i j ) ( 2 6 ) i 和p t 2 构成直线方程为： y = k x ( x - p t l x ) + p t l y ( 2 7 ) 若存在垂足q 则点p 到q 的直线方程为： y = ( 一哟( x - p 1 x ) + p y ( 2 8 ) 由公式( 2 7 ) 和公式( 2 8 ) 联解可得到： j q x = ( k 2 p t l x + k ( p y p t l y ) + p x ) ( k 2 + 1 )( 2 9 ) 【q y = k ( x p t l x ) + p t l y 然后判断垂足( q x ，q y ) 是否在p t l 和p t 2 构成的线段上： i f ( ( m i n ( p t l j ，p t 2 x ) q j m a x ( p t l v , p t 2 x ) ) a n d m i n ( p t l 以p t 2 y ) s q y s m a x ( p t l , y ，p t 2 y ) ) 两条件同时成立，则说明垂足( q x q y ) 点在p t l 和p t 2 构成的线段上所 侧 侧 右 ： 左 的 线 的 边 共 边 勉 蛾 触 凸 壳 凸 针 凸 针 时 针 时 逆 睁 逆 于 逆 于 好 驰 好 点 点 点 入 入 入 加 加 加 新 新 新 时 时 时 o 0 o m m m 晚 巍 勋 一 一 一 儿 儿 雎 当 当 当 ，、i 第二章离散点有效范围的提取 构成的线段。若垂足不在线段上，则计算两端点到垂足之间的距离。选择较近的 端点返回 经过点位置的判断可以有效遏制边界点乱连，出现死循环现象，可以保证点 按位置关系逆序形成点集，从而形成边界 2 3 3 边界收缩 对于2 3 2 小节中建好的凸壳，并不能最终作为t i n 的边界因为凸壳中在 其边界区域包含大量的无采样点的区域。这样构成t i n 模型必然在边界及其在边 界附近影响t i n 模型的精度。所以就必然需要根据边界构成的精细程度和不确定 性进一步的操作 根据本文2 2 小节中离数点边界识别小节中结果，区域边界的辕细化程度越 低，边界线段的长度越长；区域边界的精细化程度越高，边界线段的长度越短。 由此分析得出，可选用边界线段的长度作为衡量区域边界精细化程度的标准。在 实际数字地面模型的采样过程中，我们得到的采样点分布以一定的精度和密度成 不规则分布的。而不规则的采样点的密度是不均匀的，但按照测量规范，相邻采 样点之问的平均距离应满足一定的大小要求。为了取得恰当的区域边界精细化程 度。 若设d 为相邻采样点之间的平均距离， 设d 一为边界线段的最大长度。为 了确定“。为边界线段的最大长度，这需要对于相邻采样点之间的平均距离进行 估算。为了计算出采样点之间的平均距离。一般利用采样点的数目n 和凸壳多边 形面积s 计算出离散点的密度p ，即： p = n s 2 - t 0 1 式中，凸壳多边形面积s 的计算采用下式： s = 必杰k m + i - - x + + i y + ) ( 2 - i t ) 按下式估算相邻离散点的平均距离： d 2 万1 ( 2 1 2 ) 再由公式( 2 1 ) 选取适当边界搜索系数七，( 一般可取七= 3 9 ) 计算出边 1 7 阿海大学硕士论文 界线段的最大长度d 。 依次沿建立好的凸壳线段判断其边长是否大于d 。，若其边长大于厶。，则 在线段非右侧搜索一个点r ，且点r 位于线段两点的内侧，使该点与线段的距离 最近，同时该点不是原边界上已构成线段的两端点，则将r 点加入边界线段中， 即用两条边界线段代替原来的一条边界线段，形成新的边界线段。 如此按逆时针循序搜索一周后，判断识别后得到一些新的边界点。将点加入 到边界多边形中。重复这一过程，边界不断向内收缩。不断接近采样点数据的实 际范围，直到搜索一周后没有新的边界点产生为止。 2 4 本章小结 本章分析了范围线选取基本原理，并对范围线提取的解决方法进行了详细的 阐述和探讨。同时对范围线提取的意义作了简要的概述，并就范围线的提取对 t i n 模型的构建的影响进行了分析和探讨。对其中最关键的凹包边界线提取问题 进行了详细的分析和处理。本章是本论文的基础部分，也是为第四章结合范围线 构建t i n 模型提供了前置条件。本章所做工作主要有以下几个方面： i 分析了范围线提取的基本原理和意义。 2 分析了实际测绘工作中，离散数据采样点的分布情况、采样点密度和精 度对边界识别的影响，并对范围线的提取对t i n 模型的构建的影响进行了分析。 3 详细阐述了凹包的边界线提取的关键问题和解决方法。并对第四章t i n 模型的构建奠定了基础。 i g 第三章地性线的自动提取 第三章地性线的自动提取 地性线地形特征要素是指对地形地貌在地表的空间分布特征具有控制作用 的点、线或面状要素。地形特征要素构成地表地形与起伏变化的基本骨架。地形 特征要素从表示的内容形态上分为地形特征点和特征线( 即地性线) 两大类。地 形特征点主要包括山顶点、凹陷点、脊点、谷点，鞍部点平地点等；脊点、谷 点分别是指区域内相对高程最高和最低的点集；地形特征线包括山脊线、山谷线， 鞍点即是山脊线与山谷线的交点；山脊线和山谷线构成了地形起伏变化的分界线 ( 或者说是骨架线) 。另一方面，对于水文物理过程研究而言，由于山脊、山谷 分别具有分水性和汇水性，山脊线、山谷线的提取实质上也是分水线和汇水线的 提取。 地形特征线( 山脊线、山谷线) 和其它地性线( 断裂线、地类界线) 则是地貌形 态的骨架线。如果将整个采样点区域按照这些地形特征线分成若干个平面，然后 再建立每个平面的数学模型，一方面将采样点大区域划分成小区域，达到简化计 算、提高速度而不影响精度的目的；另一方面，由于每个平面是依地形特征线划 分的，因而每个平面内是连续、坡度变化均匀的，从而在每个平面内部可建立简 单的处理模式( 数学模型) ，即可有效地表达地形地貌及测量特征。因此它对地形 地貌研究具有非常重要的意义。 3 1 离散点构建初步规则格网 在已有的自动提取地性线的方法中，可根据使用的数据大致分为三种。1 ： 1 ) 基于数字化等高线数据的方法； 2 ) 基于规则格网d e m 数据的方法； 3 ) 基于d e l a u n a y 三角网和v o r o n o i 图数据的方法。 在上述的三种方法中，基于规则格网d e m 数据的方法是最主要的，也是众多 研究学者所关注的方法。大多数的算法都是基于规则格网d e m 数据来设计的。由 于本文采用的原始数据是用离散点数据。所以要从原始数据中获取得地性线，首 先需要把离散点数据进行空间插值成规则格网数据。 1 格网间距的确定 格网间距的确定往往取决于采样点的密度和精度，以及建立d 跏所用的比例 河海大学硕士论文 尺及其精度要求，其原则是每个格网点的密度等于或略大于采样点的密度。具体 做法是首先根据地形的复杂程度和精度要求，先计算出采样点之问的平均距离 d 。平均距离的计算方法采用第二章2 3 3 边界收缩小节中的公式( 2 一l o ) 、( 2 - i ! ) 先根据计算采样点之间的平均距离一般采样点的数目疗和凸壳多边形面积s ，计 算出离散点的密度p ，再由相邻离散点的平均距离的估算公式( 2 1 2 ) 得到。然 后由平均距离来确定格网的间距。 2 插值方法的选择伽 进行空间数据内插的方法依据不同的分类标准，有着不同的分类方法。可以 从内插时使用已知测量点的范围分为两大类：整体拟合法和局部拟合法；也可以 从内插的具体内容分为两大类：测量点的内插和测量区域的内插 整体拟合，是指内插模型是基于研究区域内所有测量点的特征值建立的。比 如趋势面分析，多元回归分析，傅立叶级数等。整体拟合法通常适用于大范围、 长周期变化情况，不适用于表现局部特征特性。 局部拟合，是指仅用邻近于未知点的少数已知测量点的特征值来推算未知点 的特征值，比如反距离加权插值法、样条函数插值法、克里金( k r i g i n g ) 插值 法、半变异函数插值法、自然领域插值法等。 ( 1 ) 反距离