（地图学与地理信息系统专业论文）等高线模型的时空数据组织与局部更新处理.pdf

中南大学硕士学位论文 摘要 摘要 数字高程模型是对地形地貌的数字化表达。数字高程模型已经广 泛应用于地形分析和相关研究领域。等高线数据是目前应用得最为广 泛的d e m 数据之一，等高线数据的时空数据组织与更新是时空数据 更新的重要内容。因此本文研究了等高线的时空数据组织与局部更新 问题。论文的主要研究内容与创新点如下： ( 1 ) 本文针对等高线更新处理问题，设计了相应的时空数据组 织和更新结构，即在原有的数据结构基础上添加了对时间信息的描 述。 ( 2 ) 在使用逐点插入法方法生成d e l a u n a y 三角网过程里的建立 拓扑关系这一影响构网效率的关键步骤中引入了q i 算法，简化了生 成d e l a u n a y 三角网时的复杂度，提高了构网的效率。 ( 3 ) 针对当前数字高程模型更新过程中等高线更新存在的问题， 本文提出了一个局部变化地区等高线自动更新的方法，该方法实现了 等高线的自动更新，解决了传统等高线更新过程中依靠人工进行更新 所带来的工作量大，效率低，更新质量受人为因素影响大。 ( 4 ) 在当前等高线模型的更新过程中，通常没有对历史数据进 行保存，本文则在保证完成等高线模型的更新基础上，针对历史数据 进行保存操作，即在本文提出等高线模型时空数据组织方法基础上实 现对历史数据的保存操作。 最后采用c 语言由底层开发方式完成一个试验系统，在运行多 组地形数据后所得到的实验结果表明本文所提出的等高线增量更新 算法能够得到正确的实验结果。 关键字数字高程模型，等高线，时空数据组织，局部，增量更新 中南大学硕士学位论文 a b s t r a c t a bs t r a c t d i g i t a le l e v a t i o nm o d e l ( d e m ) i st h ee x p r e s s i o no ft h ed i g i t a l t e r r a i n d e mh a sb e e nw i d e l yu s e di nt h ea n a l y s i sa n dr e l a t e dr e s e a r c h r e g i o n c u r r e n t l y , c o n t o u rd a t ai so n eo ft h em o s tw i d e l yu s e dd e m d a t a t h e o r g a n i z a t i o na n du p d a t eo f c o n t o u r ss p a t i o t e m p o r a ld a t ai sa n i m p o r t a n tp a r to fs p a t i o t e m p o r a ld a t au p d a t i n g t h e r e f o r e ，t h e o r g a n i z a t i o na n d l o c a lu p d a t e so fc o n t o u r ss p a t i o t e m p o r a ld a t aa r e s t u d i e di nt h i sp a p e r t h em a i nc o n t e n t sa n di n n o v a t i o n so ft h i sp a p e ra r e l i s t e da sf o l l o w s ： ( 1 ) d e s i g nt h ec o r r e s p o n d i n gs p a t i o t e m p o r a ld a t aa n du p d a t e s t r u c t u r et or e s o l v et h eu p d a t eo fc o n t o u rp r o b l e m s o nt h eb a s i so ft h e o r i g i n a ld a t as t r u c t u r ea d d ad e s c r i p t i o no ft h et i m ei n f o r m a t i o n ( 2 ) a f t e ra n a l y z i n gt h ep r o c e d u r e f o rt h ec o n s t r u c t i o no f d e l a u n a y t r i a n g u l a t i o nw i t h o u tc o n t r o lb o u n d a r yu s i n gp o i n t i n s e r t i o nm e t h o d ，t h e a u t h o ri n t r o d u c e dt h eq ia l g o r i t h mt ot h ek e ys t e po f b u i l d i n g n o d e t o p o l o g yt oi m p r o v et h ee f f i c i e n c y ( 3 ) i n o r d e rt or e s o l v et h ec u r r e n tc o n t o u r su p d a t ei s s u e ，t h ea u t h o r p r e s e n t san e w c o n t o u ra u t o m a t i cu p d a t e sm e t h o di nl o c a lc h a n g e sa r e a t h i sm e t h o dr e a l i z e dt h ec o n t o u r s u p d a t e sa u t o m a t i c a l l y , a n di ts o l v e s t h ev a r i o u sp r o b l e m st h a tc a u s e db ym a n u a lu p d a t ei nt r a d i t i o n a lc o n t o u r s u p d a t e ，s u c ha sh e a v yw o r k l o a d ，i n e f f i c i e n t ，u p d a t eq u a l i t yb yh u m a n f a c t o r s ( 4 ) t h eh i s t o r i c a ld a t au s u a l l yi sn o ts a v e di nt h ec u r r e n tc o n t o u r u p d a t ep r o c e s s i nt h i sp a p e r ，t h ea u t h o rs a v e dt h eh i s t o r i c a ld a t au s i n g c o n t o u rs p a c e t i m ed a t ao r g a n i z a t i o nm e t h o da st h es a m et i m ea s c o m p l e t et h ec o n t o u ru p d a t e n 中南大学硕士学位论文 a b s t r a c t a tl a s t ，t h ea u t h o ri m p l e m e n t e da ne x p e r i m e n ts y s t e mu s i n gc j | j t h e nt h ea u t h o re x p e r i m e n ts e v e r a ls e t so ft e r r a i nd a t ab yt h ee x p e r i m e n t s y s t e ma n dt h er e s u l t ss h o wt h a tc o n t o u ri n c r e m e n t a lu p d a t i n ga l g o r i t h m a r ec o r r e c t k e yw o r dd e m ，c o n t o u r , s p a t i o t e m p o r a ld a t ao r g a n i z a t i o n ，l o c a l ， i n c r e m e n t a lu p d a t i n g i i i 中南大学硕士学位论文 第一章 1 1 引言 第一章绪论 地形是地理环境特征之一，与人们的工作生活息息相关，它深刻的影响着人 们的生存和生活，是许多学科的重要研究内容。从古至今，人们为了了解以及更 加精确、详细、简便的表达地形，不断尝试着各种方法。地图是一种古老而有效 并一直沿用至今的地表表达方式【l 】，随着地图制图学的发展，相继出现了写景、 晕漪、晕渲、等高线等多种多样表达地形可视化的手段和方法。2 0 世纪中叶以 来，随着新技术新方法的大量应用和普及，原有的地形表达的方式在不断的更新 升级，各种新的地形表达方式也不断的涌现出来，尤其计算机，遥感和测量技术 的发展使得数字化的地形表达方式得以迅速发展。由美国麻省理工学院于 1 9 5 5 1 9 6 0 年期间提出的数字地面模型( d t m ：d i g i t a lt e r r a i nm o d e l ) 即是计算机 与摄影测量技术的结合 2 1 ，用数字化的地形模拟方式来解决道路工程方面的问 题。数字地面模型是描述地形表面多种信息空间分布的有序数值序列【3 】，t e r r a i n 为地形地势的意思，所有地表上的不同信息都可以通过数字地面模型来表达，因 此数字地面模型是一个相对比较广泛的数字地形表达方式。 衍生自数字地面模型，数字高程模型( d e m ：d i g i t a le l e v a t i o nm o d e l ) 则单 纯的表达自然地表的高程信息，而不包含地表其他属性，如建筑物，植被等。 d e m 是以数值的方式记录地面上平面位置( x y ) 及高程( z ) 的坐标值【1 1 。d e m 除了可以反映地形起伏的高程特征信息外，也可以反映出各种天然构造物及人工 构造物，如河流山川及道路桥梁等。现在，d e m 已经是是g i s 空间数据库中的 重要组成部分，是空间数据处理及地形分析的核心数据，在地貌、水文、生态、 环境等方面都已有广泛的应用【4 】。 由于国民经济的发展和建设以及各种地质作用的影响，地形在不断的变化， 需要不停的更新地形数据以保证它的可靠性和现势性，而作为地形数据的主要承 载者，d e m 的更新问题就显得尤为重要。 1 2 数字高程模型的研究现状 1 2 1 数字高程模型的表示方法 可以采用多种方法来表达一个地区的地表高程变化。d e m 的表示方法主要 分为两类，数学方法和图形法。 中南大学硕士学位论文第一章 由于地形表面千变万化，极其复杂，简单数学曲面一般很难反应地形的变化 特征。理论上，任何复杂的曲面都可以用高次多项式以任意的精度去逼近1 4 6 ， 因此，整体范围内可以根据区域所有的高程点数据，采用傅里叶级数或高次多项 式来拟合统一的地面高程曲面。但是以此方式来逼近地形表面，需要很多的系数， 这些系数很难找出对应的物理意义，同时高阶多项式的保凸性较差，易产生震荡 现象而产生无意义的地表起伏h t i i 4 引，另外，为了求解高阶多项式众多的系数， 需要建立并求解高阶方程组，计算量大，效率低，且计算结果对舍入误差敏感， 不易得到稳定解。 因此，在实际中，除了使用傅里叶级数和高阶多项式来整体拟合地形表面外， 一般的，按一定的规律吧整个研究区域划分成数个简单的，具有相同曲面特征的 子区域，这样，每个划分后的子区域由于结构相对简单，单一，可以采用低次多 项式来拟合地形表面且维持一定的精度。这样整个地区相当于一个分块的多项式 函数。采用分块描述地形表面，一方面减少了多项式的系数，降低了计算量，每 个多项式的系数还容易找到对应的物理意义，另一方面较为灵活，可以针对不同 的地形表面采用不同的多项式拟合，不易丢失地形表面的细节特征【4 9 1 。采用分 块描述方法需要注意分块的方法，这里分为两种，一种是按照地形表面的特征分 块，例如结构线等，另一种则是规则数学分块。如图1 1 所示 图卜1d e m 的数学表示方法 图形方法是一种地形表面的模拟表达方法，包括点数据、线数据和图像表达 方法【5 1 。采用等高线的方式来表现地形表面是比较常见的方式。地形特征线也是 表达地面高程的重要信息源，如山脊线、谷底线、海岸线及坡度变换线等。 用离散采样数据点建立d e m 是d e m 建立常用的方法之一。数据采样可以 按规则格网采样，数据点的密度则可以根据地形复杂程度和采集区域的重要程度 来决定；可以是不规则采样，如不规则三角网、邻近网模型等；也可以有选择性 地采样，采集山峰、洼坑、隘口、边界等重要特征点，这些特征点在d e m 的构 建过程中有着重要的作用1 3 】。 2 中南大学硕士学位论文 第一章 图像表达法则通常采用航空影像、航天影像、遥感影像等来表现。如图1 2 所示。 图卜2d e m 的图形表示方法 1 2 2 数字高程模型的结构模型 数字高程模型的结构模型有很多种，其中最为常见的是规则格网模型，不规 则三角网模型和等高线模型这三种。 1 ) 规则格网模型是将地形表面划分成规则的格网单元，这些格网单元可以是 矩形，三角形，六边形等，其中尤其以正方形最为常见，同时也便于计算机存储 和操作处理。每一个规则格网单元都对应一个数字，这个数字是该格网单元对应 的地形表面的高程值。 芷方形梗型正三角形模型正六边形梗型 图1 - 3 多种规则格网划分方法 规则格网模型的构建主要是通过数学方法，将地形表面划分成规则格网，把 连续的地形表面离散为彼此相接，互不覆盖的规则格网，然后再对规则格网进行 赋值。在规则格网d e m 对地形的表达和数字地形的分析中，对格网对应数字的 定义有不同的理解，这里需要说明一下，一种观点认为每一个规则格网单元内部 是同质的，即规则格网单元对应的地面面积内高程处处相等，在这种观点理解下， 数字高程模型所表达的地形表面是不连续的【。另一种观点认为规则格网对应的 数值是其中心点的数值或者是整个规则格网的平均值，规则格网之间是连续的， 而在整个规则格网模型中的任意点都可以通过距离加权平均法、样条函数或克里 金插值法等而内插求出其对应值【1 1 。 中南大学硕士学位论文 第一章 由于规则格网模型拥有结构简单，规律明显的特点，因此它适宜计算机的存 储和处理，以及易于与影像数据匹配。但同时，由于其以上特点造成规则格网模 型的分辨率固定，不能根据地形表面的实际情况来进行适应性的调整，当地形相 对简单时，会造成数据的冗余，此时可以通过各种数据压缩方法如哈弗曼编码， 基于离散余弦变换或小波变换的有损压缩方式进行数据压缩来减少数据的冗余； 而对相对复杂的地形表面，则存在规则格网不够密集，表达不够详细，一些具有 特征的地形无法通过规则格网表达出来( 如山脊，河谷，海岸线，坡度变换线等) ， 此时则可通过附加地形特征数据以提高地形表面的表达精度与准确性。 2 ) 不规则三角网( t i n ，t r i a n g u l a t e di r r e g u l a rn e t w o r k ) 是另外一种表示数字 高程模型的方法【5 0 l 。它是直接使用野外采集的原始数据点构建一系列互不交叉、 互不重叠又彼此相接的三角形组成的三角网络，以此来逼近地形表面，因此不规 则三角网是一个三维空间的分段线性模型，在整个区域内连续但不可微。不规则 三角网模型不同于规则格网模型，由于直接使用了野外采集的原始数据点，可以 根据地形的变化来决定采集的数据点，所以可以很好的顾及实际地形中较复杂的 地形特征点与特征线，同时在地形变化平缓地区能够有效减少数据的冗余。 虽然不规则三角网相对于规则格网有以上的优点，但是由于其并非是规则结 构，因此在数据组织和存储数据方式上要比规则格网复杂。除了需要存储数据点 的坐标和高程外，组成三角形的结点，相邻三角形之间的拓扑关系，以及连接结 点间的拓扑关系等都需要加以记录。由于不规则三角网需要记录的数据较多，因 此针对不规则三角网的描述方法及数据组织方面的研究较多，链表结构、面结构、 点结构、点面结构、边结构、边面结构等【5 l 】都是用来描述和组织不规则三角网 的方法，但其中，以直接表示三角形和其邻接关系的面结构应用最为普遍。 目前为止，不规则三角网的构建方法研究相对成熟，其中最为常用的是 d e l a u n a y 三角网剖分，其算法的代表主要有三角网生成法，逐点插入法和分割合 并法【2 5 】等，这些方法会在本文后面进行详述。 3 ) 等高线模型是由一系列的等高线组成的集合，其类似于线状要素的矢量数 据，所不同的是，等高线模型还需记录每条等高线的标识符，组成等高线结点的 平面坐标以及每条等高线的高程信息等。等高线相比规则格网模型和不规则三角 网模型的是，它可以直观的描述地形表面，便于人们认知和理解地形表面的变化 规律。组成等高线模型的数据一般直接来自地形图的数字化、野外采集的数据点 或遥感影像提取，且等高线模型仅表达了研究区域内的部分高程信息，因此，在 需要确定其他高程信息，或其他点的高程时需要特定的插值方法来实现，因为需 要内插的高程点或高程线是落在两条已知等高线之间，因此通常只采用外包的两 条等高线高程进行插值。 4 中南大学硕士学位论文第一章 1 2 3 数字高程模型的优点与不足 与传统的地形图相比，d e m 作为数字化的地形表达方式有着如下优点： 第一，容易以多种形式显示地形信息。传统的地形图一经制作完成，比例尺 即确定下来，无法自动改变比例尺，如需改变或者绘制其他形式的地形图则需要 人工干预处理。而d e m 则可以根据实际需要，将所包含的地形数据通过计算机 软件处理后产生出多种比例尺的地形图，纵横断面图和立体图。 第二，精度不会损失。d e m 采用数字化的存储方式，因而能时刻保持精度 不变，而传统地形图通常采用纸质媒介，随着时间的推移，图纸变形将在所难免， 精度也很难维持不变。另外d e m 采用数字化的方式直接输出结果，精度可得到 控制，而传统地形图采用人工方式制作精度会受到损失【l 】。 第三，容易实现自动化、实时化。d e m 由于是数字化存储，所以增加和修 改地形数据只需将需要修改的信息输入到计算机中，通过特定的程序处理后添加 到原有地形数据中，即可完成更新，并实时输出各种最新的地形图。而常规地图 要增加或修改都必须重复相同的工序，劳动强度大，效率低下，不利于地形数据 的实时更新i i j 。 然而，数字高程模型尽管有如此多的优点，但它同样存在着一定的缺陷和不 足。它缺乏传统地形图的一览性和直观性。表面上看数字高程模型实际上只是一 组离散的有规则或无规则高程数据，其所包含的信息十分隐蔽，必须通过一定的 信息分析手段，将所需的地形属性和特征提取出来并加以处理和显示才能便于人 们的理解，满足人们的需要。同时，虽然通过数字形式存储地形数据的数字高程 模型特别适宜各类地形三维建模分析和地形定量化的描述，但是数字高程模型并 非是真实的地形表面，而仅是通过原始地形采样数据点对实际地形的逼近，其精 度受到原始地形采样数据点的准确性和分布、实际地形的复杂程度以及数字高程 模型分辨率等因素的影响，会包含不可避免的误差。大量的理论和实践研究表明， 地形分析和地形描述对数字高程模型的误差十分敏感。 1 2 4 数字高程模型的应用 在测绘领域，尤其是在摄影测量领域，数字高程模型已经成为主要的产品形 式和各种地形图派生品的基础。同样，作为地球空间框架数据的基本内容和其他 各种地形信息的载体，数字高程模型也成为了g i s 的基础数据和基本内容。特 别是g i s 中的三维可视化和虚拟现实更是离不开数字高程模型p j 。 通过数字高程模型来进行地形分析己十分普遍，例如借助数字高程模型进行 坡度、坡向分析，已经在极为广泛的领域中应用。作为重要的参考，数字高程模 中南大学硕士学位论文 第一章 型得出的分析结果通常被各种环境、资源、工程和地理模型所采用。图1 4 说明 了数字高程模型的主要应用范畴。 流 域 特 征 提 取 d e m 应用 水文学应用 地黼学叠态学应司0 工篱他 地 貌 、 地 形 分 类 模型舅 类中弓 地形屑 变量 图1 - 4d e m 的应用 1 3 时空数据组织与更新的研究现状 1 3 1 时空数据组织的表达方式 雏 对时空数据组织进行表达是一件十分复杂的工作，不同地理实体随时间的不 同，其空间分布状态和属性值是不断变化的。国内外对时空数据组织的表达方式 的研究各有优劣，下面我们主要对几种主要的模型进行分析。主要有时空立方体 模型、连续快照模型、基态修正模型、时空复合模型等【3 8 】【3 9 1 。 1 ) 时空立方体模型用二维图形沿着时间第三维发展变化的过程表达现实世 界平面位置随时间的演变给定一个时间位置值，就可以从三维立方体中获得相应 截面、立方体的状态。也可扩展表达三维空间沿着时间变化的过程【4 0 】【4 。 2 ) 快照模型在快照数据库中仅保留当前数据状态更新后的数据，旧数据的 变化值不再保留。而连续快照模型则是将一系列的时间片段快照保存起来，反映 整个空间特征的状态，根据需要对指定的时间片段的现实片段进行播放。由于快 照将未发生变化的特征重复进行存储，会产生大量的数据冗余【4 2 】。 3 ) 为了避免连续快照模型将每个未发生变化的部分的快照特征重复进行记 录存储，基态修正模型按一定的时间间隔采样，只存储某个时间片的数据状态( 基 态) 和相对于基态的变化量1 4 2 j 。 4 ) 时空复合模型将空间分割成具有相同时空过程的最大的公共时空单元， 每次时空对象的变化都将在整个空间内产生一个新的对象。对象把在整个空间内 的变化部分作为它的空间属性，变化部分的历史作为它的时态属性 3 9 1 。 6 中南大学硕士学位论文第一章 1 3 2 时空数据更新的方式 目前，主要的时空数据更新方式有三种【4 】： 1 ) 定期更新，也就是按照固定的更新周期进行更新。例如2 0 0 3 年开始实施 的北京测绘条例规定，“1 ：5 0 0 地形图至少每2 年更新一次，l ：2 0 0 0 地形 图至少每3 年更新次，1 ：1 0 0 0 0 地形图平原地区至少每4 年、山区至少每8 年更新1 次”。 2 ) 固定变化程度的更新，即根据变化信息所占比重，当变化达到一定程度 后就对数据库内容进行一次全面更新。如每幅地图上变化内容超过3 0 时，即重 新测量并出版一张新的地图。 3 ) 增量式更新，即变化一经发现、测定便立即更新数据库内容，用采集到 的变化信息来调整或修正数据库中的内容，并随时提供给用户使用的更新模式 c o o p e r p e l e d ，2 0 0 1 。增量更新的目的是实现变化信息的“随时发现、随时 测定、随时更新”，以“适时应需”的方式保证空间数据的现势性。 在三种更新模式中，前两种可统称为批量式更新，它们更新的内容是研究区 域的整体地理信息，原先数据库中的内容将会被新的地理信息全面替换，因而其 更新的代价大、耗时长且不易保持地理信息的现势性。而增量更新由于其方式灵 活方便且能最大程度地保证空间数据的现势性，是未来空间数据更新的主要趋 势。 1 3 3 时空数据研究的问题及发展方向 目前，国内外学者对时空数据模型研究表现出如下问题：提出的模型多，实 现的原型少理论研究多；应用研究少学术门派多，应用开发商少【4 3 】。特别是理 论与应用结合不够，一些时空数据模型往往偏重或停留于理论研究，许多理论有 待在应用实践中检验并进一步深入研究m 】。目前关于时空数据模型的研究并没 有统一的标准和方法，基本上是一种基于具体应用驱动的研究，为解决特定的问 题而创建，局限于具体的应用领域和范围h a l 。每一个模型仅仅关注某一类时空 现象，当用于处理其它现象和应用时，就显得无能为力。 因此，应该建立一个全面的模型框架，这个框架能够扩展到不同的应用领域， 而不是被不同应用驱动建立成不同的数据模型。 同时现阶段的时空数据模型大多是基于时间来建模，数据结构复杂，而且随 着时间的增加，数据量大大增加，不便于管理及分析。而面向对象数据模型提供 了丰富的数据建模机制对象封装、对象标识、类型与类、概括继承、多态、聚集、 传播等，它在复杂结构数据建模、数据和操作复用方面比关系、扩展关系、层次 中南大学硕士学位论文 第一章 数据、网络模型等有更大的优点，因此使用面向对象的技术进行时空数据建模， 并发展时空对象模型成为一条充满希望之路【4 5 i 。 1 4 论文研究思路及主要研究内容 1 4 1 研究中存在的问题 通过对数字高程模型和时空数据组织更新的研究现状分析，我们可以看出， 现阶段对于数字高程模型的构建，应用等相关研究已经相当深入。但在数字高程 模型更新方面的研究还有些不足，总结先前和现在的研究成果，发现存在如下问 题： 1 ) 针对数字高程模型的更新研究中关于规则格网模型和不规则三角网模型 的局部更新的研究方法已经相对成熟【9 】【1 0 1 1 ，而对等高线模型更新的研究则显得 有些不足，由传统的等高线更新方法可以看出局部等高线更新方法基本依靠人工 进行，工作量大，效率低，更新质量受人为因素影响大，很难保证处理后地貌数 据的空间数据质量。而且，目前国内外等高线更新方面的研究成果不多，常用的 空间数据处理软件( 如m a p l n f o 、a r c g i s 、南方c a s s 等) 也没有等高线自动更 新的功能。 2 ) 在数字高程模型更新方面的研究中，大多数研究都集中在非时态性的更 新方法以及数字高程模型的精度与误差分析方面，而针对数字高程模型更新后的 历史数据组织与管理研究相对较少，在数字高程模型的更新过程中，这些历史数 据没有得到记录。虽然满足了数字高程模型的现势性与可靠性，但是却无法进行 历史数据的回溯查询，历史数据与现实数据进行比较等操作。 1 4 2 论文研究思路 首先通过对现有研究成果的学习和借鉴，再针对前文所提到的问题进行研 究，主要从实际应用角度对等高线模型的数据组织结构进行研究，提出了一种等 高线模型的时空数据组织结构，在完成等高线模型的局部更新的前提下实现对历 史数据的保存，以便历史数据的后续操作，如历史数据的恢复、查询与显示，历 史数据与现实数据的比较等操作。同时针对等高线模型的局部更新主要依靠人工 进行的现状，提出了一种局部变化等高线的自动更新方法，用以实现等高线局部 更新的自动化。同时本文针对等高线模型，讨论了其所对应的增量更新方法。最 后我们在m i c r o s o f tv i s u a ls t u d i o2 0 0 5 开发环境下，以c 撑为开发工具，采用底层 开发模式开发出一个实验系统，并实现了局部等高线的自动更新，等高线的增量 更新，验证了其正确性及可行性。 8 中南大学硕士学位论文第一章 1 4 3 论文内容与章节安排 本文以研究讨论等高线模型的局部自动更新方法为中心，同时讨论了等高线 模型的时空数据组织结构及增量更新方法。 第一章主要介绍了数字高程模型的相关概念及研究现状，时空数据组织的表 达方式及时空数据更新方式，以及本文的研究内容、研究意义、本文的组织架构 等。 第二章提出了一种引入q i 算法改进的逐点插入法，用以提高等高线模型的 构建效率。 第三章首先介绍了等高线局部更新的研究现状，找出存在的问题与不足，并 根据问题和不足提出了一套局部变化地区等高线的自动更新方法 第四章主要针等高线模型结构模型，提出了对应的时空数据组织结构。并阐 述了等高线增量更新的思想及方法。 第五章编写程序实现并验证局部变化地区等高线自动更新方法的正确性及 可行性，实现等高线模型的增量更新。 第六章总结论文相关工作的内容及不足，提出了下一步的研究方向。 9 中南大学硕士学位论文 第二章 第二章变化地区等高线模型的局部重构 组成等高线模型的数据一般直接来自地形图的数字化、野外采集的数据点或 遥感影像提取，用以上方式获取的离散数据点构建规则格网模型或不规则三角网 模型，再由规则格网模型或不规则三角网模型内插等高线，完成等高线模型的构 建。本文采用由不规则三角网内插等高线的方式来构造等高线模型。 2 1 1 构建不规则三角网 2 1 1 不规则三角网构建的基本步骤 在所有可能的三角网中，d e l a u n a y 三角网在地形拟合方面表现最为出色【i 】， 因此本文采用d e l a u n a y 三角网来构建不规则三角网模型。 d e l a u n a y _ = 角网生成共有3 类，i i p g r e e n 和s i b s o n 提出的三角网生长算法 【5 2 】【5 3 】、l a w s o n 提出的逐点插入算法及其改进算法【5 4 1 和s h 锄o s 和h o e y 提出的分治 算法【5 5 1 。三种算法中，三角网生长法构网精度高，但算法复杂。分治算法中存 在递归，因此它需要较大内存空间。逐点插入法虽然实现过程相对简单，所需内 存较小，但它的时间复杂度高，运算速度较慢【5 们。所以，若可以提高逐点插入 法的构网效率，则逐点插入法无疑是构建d e l a u n a y - - - 角网的最佳选择。逐点插入 算法基本步骤包括：构建一个包含所有点的三角网，把它作为初始d e l a u n a y = 角网；从离散点中取出的一点插入d e l a u n a y _ 三角网内；在三角网中找出所有 外接圆包含该离散点的三角形，删除这些三角形，提取顶点，相对于该离散点按 照一定的方法进行排序，构建新的拓扑关系，最后两两与离散点组成新的三角形 并加入到原三角网中。重复第步，直到所有的点都被插入。最后去掉包 含初始d e l a u n a y - - - j 訇网顶点的所有三角形。 从基本步骤可以看出，第步调用的次数最频繁，对第步进行微小改进就 可以明显提高逐点插入法的构网效率。而在第步中，提取出三角形的顶点，相 对于该离散点进行排序时，通常都采用角度计算。本文则引入了q i 算法【2 6 】来替 换角度计算，以此来达到降低逐点插入法的时间复杂度，提高逐点插入法构网效 率的目的。 2 1 2q i 算法 q i 算法是1 9 9 6 年由齐华提出建立结点上弧一弧拓扑关系的一种算法。q i 算法的思想是：在分析射线之间的空间关系时，将射线之间的空间相邻关系转换 l o 中南大学硕士学位论文第二章 为射线与单位圆的外切矩形边的交点之间的相邻关系，从而将方位角计算简化成 q i 长度计算【2 6 1 ，如图2 1 所示。 厂 、 p k o ： 图2 - 1q i 算法 l c a = l 队= 2 ，= 5x ) l r , = 6 - a yhxlan=i 1a y a j l p c = 一 xj r - y i x i( x i o ) n ( y i 2 0 ) n ( x i y i ) 4 2 - 也a x y i 讼a y x i ；岱( a x x ；i 0 ，) n o 。( 缸a x ；i - a y y ；i ，) 6 4 以+ a x y 讼i a y x ；怆( a x x ；i 如 0 ，) n n 。( a y y ；i 如 0 ，) n n 。( a x x ；i _ s a y y i ；，) l 篡：= ：= 三篡 中南大学硕士学位论文 第二章 1 首先应建立一个包含所有离散点的凸包多边形，并由此凸包多边形组成最 初的d e l a u n a y 三角网。通常建立凸包多边形的方法是遍历离散点，建立一个由 离散点组成的包含所有离散点的凸包多边形。采用这种方法虽然便于构网者理 解，但是计算机的工作量很大，尤其当离散点数量很多时，最终的凸包多边形可 能会由很多离散点组成，计算机频繁遍历离散点数据来扩充凸包多边形；再加上 还要生成初始三角网，程序实现比较复杂，计算机所进行的判断和比较的次数也 比较多【5 7 1 。因此本文改进了逐点插入法中凸包多边形的构建方法，使该方法便 于实现。改进的基本原理为：首先建立一个足够大的，确保可以把所有数据点包 围起来的矩形，用此矩形构建包含两个三角形的初始三角网，然后引入q i 算法， 逐个对插入d e l a u n a y 三角网的离散点用d e l a u n a y 三角网的空圆法则来进行检测 优化，从而保证了当所有离散点都插入完后，所建立的三角网是d e l a u n a y 三角 网【5 舯。 为了满足上文所提到的初始多边形的构建，即初始多边形要包含所有的离散 点，因此这里需要根据离散点中的x ，y 坐标最大值和最小值求得初始多边形的 m i n x ，m a x x ，m i n y ，m a x y 。在这里需要注意的是，不能直接使用离散点中的 x ，y 坐标最大值最小值来构建初始多边形。因为如果离散点中有某一个点的x 坐 标与y 坐标同时是极值点时，该离散点会成为构成初始多边形的一个顶点，这样 就导致了在最后删掉包含初始d e l a u n a y 三角网顶点的所有三角形时把所有包含 该离散点的三角形删除，从而导致生成错误的结果。因此本文对m i n x ，m a x x ， m i n y ，m a x y 进行一下处理，来构建正确的初始多边形。 m i n x - - x 最小值a x m a x x - - x 最大值+ a x m i n y = y 最小值一y m a x y = v 最大值+ a y x 、v 为偏移量。 根据这些求得的极值确定初始的多边形。初始多边形的4 个点分别为： p o i n t l - - - n e wd i s p e r s e d p o i n t ( m i n x ，m i n y ) p o i n t 2 - - n e wd i s p c r s e d p o i n t ( m i n x ，m a x o p o i n t 3 - - n e wd i s p e r s e d p o i n t ( m a x x ，m i n y ) p o i n t 4 = n e wd i s p e r s e d p o i n t ( m a x x ，m a x 由于此初始多边形是矩形，因此初始三角网的建立也非常容易实现，只要连 接任意一条对角线即可实现拥有两个三角形的初始d e l a u n a y 三角网，如图2 2 。 1 2 中南大学硕士学位论文 第二章 图2 - 2 初始三角网的构建 2 把离散点逐次插入到三角网中，将三角网中外接圆包含此离散点的三角形 提取出来( 如图2 - 3 a ) ，并将这些三角形从三角网中删除( 如图2 - 3 b ) 。将这些 三角形顶点提取出来构成影响域多边形的顶点，由于此时这些点的顺序是未定 的，不能直接与离散点两两组合成新的三角形，因此需要将这些顶点以该离散点 为中心，重新排序，构建新的拓扑关系。通常采用角度计算来确定顺序，角度计 算虽然方法简单，便于理解，但是编程实现起来则比较复杂，需要应用复杂的三 角函数运算，而本文引入的q i 算法则将复杂的三角函数运算转换为长度计算， 可以减少运算次数，提高效率( 见表2 1 ) 。因此在本文中，以该离散点为中心用 q i 算法算得每个影响域顶点关于此离散点所对应的q i 值，将这些影响域顶点按 q i 值排序后即建立起新的拓扑关系( 如图2 - 3 e ) ，按照新拓扑关系两两与离散点 组成新的三角形并加入到原三角网中( 如图2 - 3 d ) 。 表2 - 1 运算方法执行次数比较 b c 2 - 3 带q i 算法的d e l a u n a y z 角网构建过 3 重复步骤3 ，直到所有的离散点都插入到三角网中。 4 将所有包含初始多边形顶点的三角形删除，即可得到最后的d e l a u n a y 三角 中南人学硕士学位论文 第二章 网。过程如图3 4 所示。 2 2 等高线内插 固 图2 - 4 删除初始多边形及多余三角形过程 当不规则三角网构建完成后，通过遍历结点坐标表，获取到高程最大值与高 程最小值，再根据所定的等高距确定等高线个数及每条等高线的高程值。然后开 始进行等高线内插操作，具体操作步骤如下【3 6 】： 在三角形结点记录表中逐次提取出三角形，判断三角形的三边是否与待插 值等高线相交，判断公式为： p = ( l 一f ) ( 2 - h f ) ( 2 1 ) 其中h l 、h 2 为三角形一某条边两个结点点的高程值，h i 为追踪的等高线高 程。若e 0 ，则等高线与该边没有交点。若三角 形三边都没有和待插等高线相交，则重复； 若三角形某条边与待插等高线相交，则根据如下公式内插出高程点水平坐 标x i ，y i 。其中x l ，y l ，x 2 ，y 2 为三角形与等高线相交的边的结点坐标值。 x ，：即争导( x 2 呐) 】2 一j 1 l = 五+ 糌吼叫) ( 2 - 2 ) 同时使用公式2 1 判断出余下两条边中与等高线相交边，使用公式2 2 求 出高程点坐标。 此时调用三角形邻接关系表，找出与此三角形相邻的三角形，使用公式 3 1 逐次判断三角形各个边，当出现相交情况时重复步骤，直到遍历三角形 邻接关系表结束。将内插出的等高线坐标存储到链条等高线数据结构中完成一条 等高线的内插工作。 获取下一高程值，重复步骤，直到所有高程值遍历结束，完成整个等高 线的内插工作。 2 3 等高线光滑 本文为了便于计算机认知存储等高线而采用了链表等高线数据结构，将实际 1 4 中南大学硕士学位论文第二章 是光滑曲线的等高线离散成一系列的折线结点，因此在输出显示等高线时需将折 线进行光滑处理1 2 。计算机绘制的光滑曲线实际上是由一系列密集点连接而成， 由此可以得出等高线光滑的基本思想，已知等高线的折线结点，通过一定的数学 方法进行插值和逼近，得到一系列密集的点列的坐标值，并确保在这些点列上具 有连续的一阶导数或连续的二阶导数，就可以保证绘出的曲线是光滑的。从等高 线光滑的基本思想中可以看出进行插值和逼近的方法有很多，用不同的方法进行 插值得出的光滑曲线也一定会有所不同。目前较常用的等高线光滑方法有5 种 f 2 刀，分别是贝塞尔曲线、b 样条曲线、三次多项式插值函数、张力样条函数、实 用三次样条函数。其中贝塞尔曲线和b 样条曲线光滑时不通过插值点，显然等 高线光滑时需要光滑曲线经过插值点以保证其精度，所以这两种方法并不适合等 高线光滑。三次多项式插值函数在对等高线进行插值过程中，当待插值等高线较 密集时会出现相交情况；张力样条函数在插值过程中曲线有时会产生震荡现象。 三次样条函数具有的一个显著特征，即有一个参数九。当护0 时，为线性插值函 数。九的最大值为1 ，当九由l 向0 递减时，三次样条函数插值所产生的曲线逐 渐趋向于线性插值所得到的曲线，这一特性对于解决等高线光滑时所产生的相交 问题具有重大的意义。因此本文选择三次样条函数作为等高线光滑的插值函数。 同时在本文中所使用的三次样条函数，其参数九为可调的，即由使用者决定等高 线光滑的形态，在保证光滑等高线不相交的前提下，尽量使得生成的等高线美观。 厂弋 x = o 0 x = o 0 x = o 3 x = o 0 x = o 6 x = o 0 x = o 9 图2 - 5 三次样条函数不同人参数比较 图2 5 为九取不同值时的光滑曲线形态与x = o ，即线性插值函数曲线的比较。 可以明显看出三次样条函数对于不同的九值具有不同的内收或外张趋势。 中南大学硕士学位论文 第二章 2 4 本章总结 不规则三角网模型在很多领域都有着广泛的应用，快速高效地生成不规则三 角网十分重要。同时在所有可能的三角网中，d e l a u n a y 三角网在地形拟合方面表 现最为出色，因此本章首先比较了几种生成d e l a u n a y 三角网的方法，根据需求 选择采用逐点插入法生成d e l a u n a y 三角网，然后深入研究了使用逐点插入法构 建d e l a u n a y 三角网的过程。并在使用该方法生成d e l a u n a y 三角网过程里的建立 拓扑关系这一影响构网效率的关键步骤中引入了q i 算法，从而简化该方法实现 生成d e l a u n a y 三角网时的复杂度，提高了构网效率。接着介绍了等高线内插的 方法和等高线光滑的思想，并对几种等高线光滑的方法，比较了其优缺点。根据 本文生成等高线的实际需要，选取了三次样条函数为本文等高线光滑的插值函 数。 1 6 中南大学硕士学位论文 第三章 第三章等高线模型的局部更新处理方法 传统等高线更新的方法是当大范围的地貌发生变化时，重新采集测区内所有 地形特征点，生成新的等高线取代原来等高线；在局部地貌变化情况下，首先采 集局部数据点，生成局部变化等高线，然后人工根据经验依次判断出每条新生成 等高线在原图上的对应等高线( 即高程值相等的等高线) ，采用线段剪切或延长 等方法，将变化后等高线添加至原图，然后采用曲线拟合的方法完成局部变化等 高线的更新。可以看出，上述局部变化等高线的更新方法基本依靠人工进行，工 作量大，效率低，更新质量受人为因素影响大，很难保证处理后地形数据的空间 数据质量。此外，目前国内外等高线更新方面的研究成果不多，常用的空间数据 处理软件( 如m a p i n f o 、a r c g i s 、南方c a s s 等) 也没有局部变化等高线的自动 更新功能【5 j 。 因此对局部变化地区等高线特点进行研究，并找出进行局部变化地区等高线 自动更新的方法显得十分重要。 3 1 局部变化等高线的自动更新思路 传统等高线更新的方法是首先将通过各种方式采集到的局部数据点，借助计 算机成图软件自动绘制局部等高线，然后人工根据经验依次判断出每条新生成等 高线在原图上的对应等高线( 即高程值相等的等高线) ，采用线段剪切或延长等 方法，将变化后等高线添加至原图，然后采用曲线拟合的方法完成局部等高线更 新【7 1 。 本文提出的局部变化等高线更新方法核心思想与传统等高线