（计算机应用技术专业论文）无级比例尺gis的线状要素化简算法研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 线状要素综合作为制图综合领域中最重要的研究区域，经历了几 十年的发展后，仍然是专家学者们研究的热点。这一方面是由线状要 素在地图要素的图形表达上的重要性决定的；另方面是由于制图综 合和线状要素综合本身的理论和技术还不完善、不成熟。此外，作为 描述空间信息的重要组成部分，线状要素的分析、处理在g i s 占有重要 地位。随着g i s 应用领域的不断扩展币d i n t e r n e t 技术的发展，现有的g i s 数据处理机制已经不能满足信息社会的需要，其中一个重要的原因就 是g i s 无法解决矢量空间数据随比例尺变化而产生的信息量增减的问 题，即无级比例尺g 1 s 空间信息压缩与复现问题。因此，对线状要素 综合特别是化简技术进行研究很有必要。 本文重点研究无级比例尺g i s 线状要素的化简算法、算法实现以 及线状要素化简系统的设计与初步实验，主要内容如下： 从多比例尺g i s 、数据库的多重表达、无级比例尺g i s 和地图 自动综合角度，探讨了线状要素化简算法的研究意义及现状。 介绍了线状要素化简的基本算法，重点研究d o u g l a s p e u c k e r 算法。为提高算法效率，采用队和栈的数据结构实现该算法； 对该算法中闽值的选择和算法实施过程中建立的二叉树结构 进行了深入研究和分析，并说明了该结构在无级比例尺g i s 中的应用。 分析了线状要素化简算法导致错误拓扑关系的原因；采用平面 扫视法对化简操作产生的相交线段进行判定，为降低实现该算 法的难度及节省内存空间，提出了基于相交线段端点位置关系 的实现方法。 采用局部细节扩充策略对d o u g l a s p e u c k e r 算法进行完善，避 免了化简过程产生的相交与自相交。 介绍了评价化简算法的数学量度指标，建立了线状要素化简试 验系统，并以等高线数据为基础，对本文工作进行初步实验。 实验结果表明：本文提出的d o u g l a s p e u c k e r 算法的实现方法和用 于无级比例尺g i s 的二叉树结构，以及消除该算法产生的曲线相交与 自相交所采用的局部扩充策略是正确的，且化简过程中采用的平面扫 西南交通大学硕士研究生学位论文第l i 页 西南交通大学硕士研究生学位论文第1 ii 页 a b s t r a c t l i n e g e n e r a l i z a t i o n ，o n e o ft h em o s t i m p o r t a n t f i e l d so ft h e c a r t o g r a p h i cg e n e r a l i z a t i o n ，i ss t i l lac e n t r a li s s u ef o re x p e r t sa n ds c h o l a r s a f t e r m a n yy e a r s d e v e l o p m e n t t h a t h a st w or e a s o n s ：o n ei st h e i m p o r t a n c eo fl i n ei nm a pr e p r e s e n t a t i o n ，t h eo t h e ri st h ei m p e r f e c t a b i l i t y a n d i m m a t u r i t y o ft h e t h e o r y o fc a r t o g r a p h i c g e n e r a l i z a t i o n a n dl i n e g e n e r a l i z a t i o n i t s e l f i n a d d i t i o n ，a s am a i n p a r t i t i o n o f s p a t i a l i m f o r m a t i o nr e p r e s e n t a t i o n ，a n a l y s i sa n dd e a lo fl i n ep l a ya ni m p o r t a n t r o l ei ng i s w i t ht h ee x p a n s i o no fg i sa p p l i n gf i e l da n dd e v e l o p m e n to f i n t e r n e tt e c h n i q u e ，n o wa v i l i a b l ed a t ap r o c e s s i n gs y s t e mo fg i sc o u l d n t m e e tt h er e q u i r e m e n t so ft h ei n f o r m a t i o ns o c i e t y o n eo ft h ei m p o r t a n t r e a s o n si st h a tg i sc o u l d n ta d j u s tt h eq u a n t i t yo f s p a t i a li n f o r m a t i o nw i t h d e r i v i n gs m a l ls c a l ef r o ml a r g es c a l ea u t o m a t i c a l l y , w h i c hi s a l s oc a l l e d s p a t i a l i n f o r m a t i o n c o m p r e s s i o n a n d r e a p p e a r a n c e o fs c a l e l e s sg i s c o n s e q u e n t l y , i t s e s s e n t i a lt o p a y a t t e n t i o n st ot h er e s e a r c hi nl i n e s i m p l i f i c a t i o nm o r e t h a ni nl i n eg e n e r a z a l a t i o n t h i sp a p e rf o c u s e so nl i n e s i m p l i f i c a t i o na l g o r i t h m si ns c a l e l e s sg i s a sw e l la s a l g o r i t h m si m p l e m e n t a t i o n ，a n dd e s i g n s a n de s t a b l i s h e sa l i n e - s i m p l i f i c a t i o ns y s t e m t h ep r i n c i p a l c o n t e n t si nt h i st h e s i sa r ea s f o l l o w s ： s t u d y i n gs t a t u sa n dr e s e a r c h i n gm e a n i n gi nt e r m so fm u l t i s c a l e g i s ，m u l t i p l er e p r e s e n t a t i o n d a t a b a s e ，s c a l e l e s s g i sa n d a u t o m a t i cc a r t o g r a p h i cg e n e r a l i z a t i o n i n t r o d u c i n gb a s i ca l g o r i t h m so fl i n e s i m p l i f i c a t i o n ，e s p e c i a l l yt h e d o u g l a s p e u c k e ra l g o r i t h m t h eq u e u ea n ds t a c kd a t as t r u c t u r e i s p u t f o r w a r dt or e a l i z et h e d o u g l a s - p e u c k e ra l g o r i t h m f o r i m p r o v i n g t h e e f f i c i e n c y , a n d t h e s e l e c t i n g o ft h r e s h o l da n d b i n a r yt r e es t r u c t u r et h a tb u i l d si nt h i sa l g o r i t h ma r ec o n s i d e r e d a n da n a l y s i z e dt h o r o u g h l ya sw e l la si t s a p p l i c a t i o ni ns a c l e l e s s g i s a n a l y s i z i n g t h er e a s o nt h a tw h y l i n e - s i m p l i f i c a t i o na l g o r i t h mc a n 西南交通大学硕士研究生学位论文第l v 页 l e a dt oe r r o rt o p o l o g i c a lr e l a t i o n s t h ep l a n e s w e e pa l g o r i t h mi s u s e dt od e t e r m i n et h ei n t e r s e c t i o no fl i n e s e g m e n tc a u s e db y s i m p l i f i c a t i o n i no r d e rt or e d u c et h ed i f f i c u l t yo fi m p l e m e n t a t i o n a n ds a v e m e m o r y , a ni m p l e m e n t a t i o n o ft h i s a l g o r i t h m i s a d v a n c e d ，w h i c hi sb a s e do i lp o i n t s sp o s i t i o no fi n t e r s e c t i n gl i n e s e g m e n t s a d o p t i n gl o c a l - d e t a i l - e x p a n d i n gt a c t i c st o a v o i di n t e r s e c t i o na n d s e l f i n t e r s e c t i o nc a u s e db y d o u g l a s p e u c k e ra l g o r t i t h m i n t r o d u c i n g m a t h e m a t i c a lm e a s u r e st oe v a l u a t e l i n e s i m p l i f i c a t i o na l g o r i t h m a n dal i n e s i m p l i f i c a t i o ns y s t e mi s d e s i g n e d ，w h i c ht e s t s t h ew o r ko ft h i s p a p e rb a s e do nc o n t o u r d a t a s ， e x p e r i m e n t a l r e s u l t ss h o wt h a tt h e i m p l e m e n t a t i o n o f d o u g l a s p e u c k e ra l g o r i t h m b a s e do nq u e u ea n ds t a c ks t r u c t u r ea n d b i n a r yt r e eu s e di ns c a l e l e s sg i s i sc o r r e c ta sw e l la st h el o c a l e x p a n d i n g t a c t i c sa p p t i e dt oe l i m i n a t et h ei n t e r s e c t i o na n ds e l f - i n t e r s e c t i o n ；a n dt h e i m p l e m e n t a t i o n o f p l a n e - s w e e pa l g o r i t h m u s e di n s i m p l i f i c a t i o n i s f e a s i b l e k e yw o r d s ：s c a l e l e s sg i s ；l i n e - s i m p l i f i c a t i o na l g o r i t h m ；p l a n e s w e e p m e t h o d ；i n t e r s e c t i o na n ds e l f - i n t e r s e c t i o no fl i n e 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 。1 研究背景及意义 在数字化系统中，一个线状物体总是由对其采样所得到的离散点列来 描述的，采样点越密，则描述原始地物的能力越强，越能真实的反映原物 体。但随之而来的数据量急剧增大，对数据管理和分析都带来很大困难。 因此，有必要进行线状要素的数据压缩。这个过程也称为线状要素化简， 或者线状物体抽样，即用尽可能少的采样点来描述原始地物，并保证在容 许的误差限度内，再现地物的形态特征。从信息论上来讲，线状要素数据 化简技术实质上是一个信息压缩问题，即从组成曲线的点序集合中抽取一 个点序子集，用这个子集作为一个新的信息源，在规定的精度范围内该子 集从内容上尽可能真实地反映原集合，而在数量上则尽可能精简。 1 。1 1 数据库的多重表达和多比例尺g i s 地理信息系统( g e o g r a p h i c i n f o r m a t i o ns y s t e m ，g i s ) 的主要功能是 采集、管理、分析和表达与地球相关的信息。随着g i s 应用领域的不断扩 展和相关技术的发展，多比例尺g i s ( m u l t i s c a l eg i s ) 中的数据库多重 表达( m u l t i p l er e p r e s e n t a t i o nd a t a b a s e ) 已经成为当前国内外g i s 领域的热 点、难点问题之一 实际上，“数据库多重表达”并不是近几年才出现的名词，早在1 9 8 8 年，美国地理信息和分析国家中，l 、( n c g i a ) 就提出了这一概念，并将这一 问题列入该中心的基金课题之一。按照n c g i a 给出的定义，数据库多重 表达是指“随着在计算机内存储、分析和掐述的地理客体的分辨率( 比例 尺) 的不同，所产生和维护的同一地理客体在几何、拓扑结构和属性方面 的不同数字表达形式”“1 。也就是说，它尝试将不同固定比例尺水平上的 单一表达，集成到一个一致的多重表达之中，使具备“多重表达”机制的 o i s b 够以不同分辨率或比例尺的表达性“数据集”的方式来表达其数据 库内容。多重表达数据库也可以称为“多比例尺数据库”( m u l t i s c a l e d a t a b a s e ) 。以多重表达数据库为核心的g i s 被称为“多比例尺g i s ”。 下面用一个例子来帮助阐述这个概念。考虑同一个地区的1 ：1 0 0 0 、1 ： 西南交通大学硕士研究生学位论文第2 页 2 5 0 0 0 、1 ：1 0 0 0 0 0 、1 ：2 5 0 0 0 0 的地图，对于1 ：1 0 0 0 的地图来说，在个 特定的居民区，其住处也许可以用他们的详细轮廓来表示：在1 ：2 5 0 0 0 的地图中建筑物就要用简化的矩形来表示了，某些建筑的多边形甚至会被 合并到一起；在另一个更小的1 ：1 0 0 0 0 0 的地图上，地区用街道网络和城 市边界所定义的彩色街区来表示，这就变成了更大、更不规则的多边形： 最后，在1 ：2 5 0 0 0 0 的地图上只能显示街区的集合，整个城市表示为个 多边形特征物，并且小的城镇转化为点符号来表示。根据上述不同地图的 特征，建立不同尺度的数据库，并全部进入g 【s ，在实际应用时，根据不 同的要求选择不同的数据库进行数据处理。在这种情况下，g i s 数据库能 在不同等级上表示实体，并支持对数据的不同详细级别的修改。 近几年来，多比例尺g i s 已经成为g i s 研究领域内的热点问题之一。 在一系列国际g i s 会议和空间论坛上，“m u l t i s c a l eg i s ”均被列为中心 议题“1 ；1 9 9 6 年中国地理信息系统协会第二属年会的“数据库和数据模 型”分会场的热门话题之一也是多比例尺g i s ；在1 9 9 5 年( 西班牙巴塞罗 那) 和1 9 9 7 年( 瑞典斯德哥尔摩) 两届国际制图协会( i n t e r n a t i o n a l c a r t o g r a p h i cc o n f e r e n c e ，i c 舢会议上，若干篇与该问题有关的论文亦被 列为大会重点宣读论文“。 1 1 。2 无级比例尺g l s 随着g i s 应用领域的不断扩展和需求层次的日益提高，人们越来越多 地需要在不同分辨率、不同空间尺度上对地理现象进行观察、理解和描述， 即越来越多地需要对多尺度的空间数据进行分析、处理和表达。从上述对 多比例尺g i s 的介绍，可以看出其优点是明显的，但其不足也是显而易见 的，如数据的重复存储、数据更新不方便以及需要更多的时间和费用来建 库等，所有这些最终都导致了对无级比例尺g i s ( s c a l e l e s sg i s ) 的需求。 与此同时，随着“数字地球”和i n t e m e t 技术的发展，现有的g i s 数据处理 机制已经不能满足信息社会的需要，其中一个重要的原因就是g i s 无法解 决矢量空间数据随比例尺变化而产生的信息量增减的问题，即无级比例尺 g i s 空间信息压缩与复现问题。 所谓无级比例尺g i s 是以一个大比例尺单精度空间数据库为基础数 据源，在一定空间区域内通过空间对象的信息量随比例尺的变化自动增减 的方法，来使g i s 空间信息的压缩和复现与比例尺实现自适应的一种信息 西南交通大学硕士研究生学位论文第3 页 处理技术“”。作为无级比例尺g i s 的基础数据源，大比例尺单精度空间数 据库是由某区域范围( 如中国全境) 的大比例尺( 如1 ：1 0 0 0 ) 基础地理 和专题信息所构成的大型空间数据库，该数据库通常由数千或数万幅同比 例尺的系列图幅( 如地形图、专题图) 在统一的地理坐标参照下无缝拼接 而成。应用所需的任意小比例尺的数据从大比例尺数据自动派生而成。仍 以上述例子加以说明，对l ：1 0 0 0 、1 ：2 5 0 0 0 、l ：1 0 0 0 0 0 、l ：2 5 0 0 0 0 的 地图而言，在无级比例尺g i s 中，g 1 s 只是按照1 ：1 0 0 0 的尺度建立数据库， 实际应用中所需的其他任意小比例尺地图都是在此基础上进行数据压缩 来实现的。正是因为具备多比例尺g i s 所不具备的优点，无级比例尺g i s 是地理信息系统最终的目标。 1 1 3 地图自动综合 从大比例尺数据自动派生生成小比例尺数据的本质是地图自动综合。 地图综合( c a r t o g r a p h i cg e n e r a l i z a t i o n ) 是根据地图的用途、比例尺和制 图区域的特点，以概括、抽象的形式反映出制图对象的带有规律性的类型 特征和典型特点，而将那些对该图来说是次要的、非本质的物体舍掉“。 在传统的绘图方法中，地图综合用于地图比例尺缩小过程中减小地图表示 内容的复杂度，强调精华、摈弃糟粕、维护地图对象间的逻辑关系与唯一 关系，以保证地图审美质量。因此，地图综合的主要目的是创建高清晰的 地图，以便识别和理解地图所表达的信息。也可以说，地图综合等同于“通 过选择和简化适当表示地图的比例或对象的代表特征”( 国际制图协会， 1 9 7 3 ) 。 地图自动综合是一个世界公认的难题，这一点可以在现有的相关文献 及地图综合目前存在的诸多问题中看出，而目前国际上在建立国家( 或区 域性) 地图数据库时仍采用多比例尺地图数据建库方法就是一个更有力的 证明。影响地图综合的因素有很多，这些因素很难用简单的数学和逻辑语 言来描述。因此，要在有限的地图幅面内，并在满足最佳目视效果的条件 下，使空间信息随着比例尺的变化而自动增减是非常困难的，目前尚无理 想的解决方案“。在很多情况下，通过化简的途径由大比例尺数据迅速地 派生出小比例尺数据是有意义地的。例如，将原地图进行比例尺缩减变成 目标地图时，会导致地图特征物之间的空间竞争，这种情况是由两个累积 效应产生的：首先，在缩减比例尺时，地图上用于置放表达地图特征物符 西南交通大学硕士研究生学位论文第4 页 号的位置变小；与此同时，为了维持地图对象的大小关系和易读性，符号 大小相对于它覆盖的实际地面来说增加了。为解决上述冲突，制图者在操 作时可以只选择表达要素的一部分特征子集来简化要素。 g 1 s 中的图形数据信息主要通过线状图形要索来表达。例如，点状 要素可看成是特殊的线，面状要素由一条或多条线状要素围成。g i s 中 的线状要素包括道路、河流、境界、等高线、管线和面状要素的边界等， 线状数据作为g i s 数据中重要的组成部分，它的处理关系到整个空间数 据库系统的性能。因此很有必要进行线状要素综合特别是化筒的研究。 线状要素综合作为制图综合领域中最主要的研究领域，在经历了几十 年的发展后，仍经久不衰，一方面是由于制图综合和线状要素综合本身的 理论和技术还不完善、不成熟：另一方面是由于线状要素在地图要素的图 形表达上的重要性，曲线一般要占地图图形的8 0 以上( t h a p a ，1 9 8 8 ) “”， 并且曲线是由点序列来描述，本身又可在一定程度上抽象成点，加之曲线 是构成面的主导因素，曲线与点、面的特殊关系，使得线状要素综合的研 究成为制图综合领域中的一个主题，已有许多学者投身于此领域的研究。 严格的线状要素综合包括化简( s i m p l i f i c a t i o n ) 、光滑( s m o o t h i n g ) 、 位移( d i s p l a c e m e n t ) 、增强( e n h a n c e m e n t ) 以及综合后的评估等。其中 化简是最主要的方面，狭义上的线状要素综合就是指曲线的化简。由于线 状要素是地图数据的重要组成部分，因此许多学者都对它进行了研究，产 生了大量的算法。 1 2 现有成果分析 对线状要素进行简化，其目的是：使存储量最少，且保持线状要素的 主要特征。目前主要用到的化简算法有：间隔取点法“”、d o u g a s - p e u c k e r 算法“7 ( 部分文献称之蔓j s p l i t t i n g 算法) 、垂距算法“、角度算法“”等。事 实上，线的化简算法在计算机视觉、图形识别中也有很多介绍，如平面曲 线的数据压缩。由于算法比较多，因此有很多学者对这些化简算法进行比 较，并提出新的改进算法，或说明某算法的使用范围。如：顾及精度的 较长距离边端点寻求法”、消除曲线上微凹凸现象的d o u g l a s p e u c k e r 改进 算法“、光栏法”以及纯几何的渐进式方法”等。 e r i ck v a nh o r n ( 1 9 8 5 ) 考虑地图数据库中的线在计算机显示器上显示 时，由于分辨率的限制和显示比例尺的缩小，采用d o u g l a s p e u c k e r e l 简算 西南交通大学硕士研究生学位论文第5 页 法会使线状要素图形产生变形，因此在用d o u g l a s p e u c k e r 算法之前，先用 点的重定位技术，即把点先归算到最近的格网点( 显示器上的阵点) 上。 但该方法同样会产生自相交问题，他提出的解决办法是手工纠正”。 b a r b a r ap lb u t t e n f i e l d ( 1 9 8 9 ) 把线分为依尺度的和自相似的，因此线 的简化算法也应当这样区分1 。他认为，即使是同一条线，自相似性也 有一定的存在范围，即在某一给定的尺度范围内自相似性才会存在，那么 在线状要素化简时，如何保持线的分形特征就受到学者的关注。在计算线 的长度时，采用不同步长，得到不同的长度，也即不同精度条件下，线的 长度不同。通常线的长度随精度的降低而减少，这种规律在计算线的分维 时是常用的，但最好采用非线性回归方法来模拟步长和线的长度之间的关 系，从回归参数和回归图形中可以找到线的地理特征。”。 有的学者把线状要素化简算法分为两类：以数据压缩为目的的统计方 法和以图形显示为目的的制图方法。如地图高精度扫描并矢量化后删除抖 动的算法“”、滤波法”、曲线拟合方法等就属于前者。对于制图综合，学 者们不仅对已有方法进行了比较，同时为了满足视觉感受的需求，模拟手 工综合，对已有的线简化算法迸行了大量的改进。女f z e s h e nw a n g ( 1 9 9 6 ) 把线的自动综合和线的手工综合进行了详细的对比分析，总结出线状要素 自动综合要遵循的四条规则”：( a ) 小弯曲应删除，大弯曲保留；( b ) 两 个弯曲、三个弯曲可合并成一个弯曲，依次类推；( c ) 独立性强的弯曲应 该保留或者夸大；( d ) 自然的线不能变成几何上的直线。他所采用的自动 综合方法是弯衄的迭代式删除，条件是弯曲面积的大小，为了保证不同形 状的弯曲在综合时有所考虑，采用了弯曲图形的紧凑系数，以便识别不同 形状的弯曲。 在数字化系统中，对线状要素进行化简时，化简算法是基于有序的离 散点集，但实际中曲线是以光滑的图形方式存在的，因此有的学者就探讨 了线的简化算法和线光滑算法的综合运用，r o b e r tb m c m a s t e r 把线的光 滑和综合联系在一起，并提出了实燕此方法的五个步骤。”。 在线状要素化简的各算法中，参数设置通常由用户根据具体情况来进 行设置，一般不能自动化或智能化，这是当前制图综合的一个难点和重要 研究方向。在现有的很多线状要素简化算法中都必须己知阈值，但是用 个阈值作用于不同的线，其效果并不理想，因而阈值的选择就成了一个难 题。b a r b a r apb u t t e r f i e l d 提出先确定线的结构，即使是同一条线也应当区 分出不同类型的段，他使用古典式聚类分析方法”。c r o m l e y 和c a m p b e l l 西南交通大学硕士研究生学位论文第6 页 ( 1 9 9 2 ) 指出，阀值和综合比例尺没有简单的关系；参数的变化也不是线 性的”“。m a r t i na f i s c h l e r 等认为应当根据视觉感知的规律对曲线进行分 区l a 4 ) 也有学者认为应当根据线的图形特征进行分段，使每一段线的弯 曲特征保持一致”“。通过大量的实验，入们发现综合前后点数的关系遵 循开方根定律”。 j c m u l l e r ( 1 9 8 7 ) 认为在线的简化过程中应当强调点的最优密度“”， 也有学者探讨使用最优化方法使得线的简化达到最优化( r gc r o m e l y 等， 1 9 9 2 ) ，其基本思想是：随着比例尺的缩小，条线内的线段数依开方根 规律变化，在线段数己知的条件下，选取哪些点就是该算法的核心。 线状要素化简过程中，特征点的保留非常重要，它包括几何特征点和 地理含义的特征点( g f j e n k s ，1 9 7 9 ) 。z h i l i nl i ( 1 9 9 5 ) 在分析了大量的线的 特征点探测方法后，把它归为三类：拐角探测法、多边形( 多角) 式拟合 和前两者的混合方法”。在进行线状要素化简时，线的几何特征描述非常 重要的“。线的长度是按什么样的规律变化，p h i l i pb a c k e t t ( 1 9 7 7 ) 并- d v g a r d i n e r ( 1 9 7 7 ) 进行了详细的探讨。r o b e r t b m c m a s t e r 等( 1 9 9 6 ) 在分 析地图综合的质量评价量度指标的同时，建立了一套理论框架，他强调线 与线之间的关系，不再只针对单根线“。特征点在计算几何、计算机视 觉中有大量应用，在g i s 中的数据压缩方面也起了很重要的作用“。 考虑地理环境的线状要素化简，拓扑一致性是基本要求，即在化简过 程中必须考虑各个要素之间的空间关系。为解决化简过程中线的自相交和 线与其他要素的相交，z h i l i nu $ 1 s t a no p e n s h a w 提出了基于“客观综合 的自然规律”的线状要素化简算法“”；m v i s v a l i n g a m 和j d w h y a t l 提出 了基于最小面积的重复式点删除方法“，该方法提出应该先搜索“瓶颈” 式区域或图形复杂部分：m a r kd eb e r g ，m a rv a i lk r e v e l d 和s c e f a ns c h i r r a ( 1 9 9 5 ) 提出一种新的线化简方法再分区式化简“；w us h i n t i n g 和m e r c e d e s 提出了一种基于星形的d o u m a s p e u c k e r 算法，该算法要求先对 线状要素进行分块，然后对各块分别用d o u g l a s p e u c k e r 算法依次进行化简 “”；郭庆胜提出了纯几何的基于面积的渐进式化简算法和基于“弯曲” 单元的渐进式化简算法泓1 ；田鹏，郑扣根等提出了一种基于s t r i p t r e e “7 】 的线状要素化简算法，该算法在实施化简算法后判断是否存在自相交或相 交，若有则对发生相交或自相交的线段对进行扩充，重复判断、扩充，直 至化简后的曲线不存在相交或自相交情况为止”1 。 线状要素的化简评估中，m a r kd e b e r g ( 1 9 9 8 ) 称其体现在三个方面： 西南交通大学硕士研究生学位论文第7 页 最大误差、特征点位置( 相对线) 的保持、无自相交“。m c m a s t e r ( 1 9 8 7 ) 提出化简算法的评估应从曲线的长度、角度、点数，以及矢量位移和面积 偏差等几个方面来进行”。b u t t e n f i e l ( 1 9 8 5 ) 提出曲线按条带进行划分的 方法来对曲线进行定量研究”。目前算法的综合评估已成为制图综合的一 个重要方面，有关学者正在进行相关的研究。 1 3 本文工作和论文组织 本文主要围绕无级比例尺g i s 矢量空间的线状要素化简技术，重点研 究线状要素化简算法、算法实现及算法产生的线状要素的相交与自相交的 解决策略；同时，以等高线数据为基础，对线状要素化简系统进行了设计 和实验。本文的组织结构如下： 第一章，介绍无级比例尺g i s 线状要素化简技术的背景及化简算法的 国内外研究现状，阐述了研究化简算法的重要性和必要性，以及论文的组 织结构。 第二章，阐述空间数据质量的概念和标准，介绍了数据误差的类型、 来源及解决策略，重点是线状要素化简前的预处理操作。 第三章，讨论常见的线状要素化简算法，重点研究d o u g l a s - p e u c k e r 算法，主要包括该算法的实现方法、层次结构和阈值选择。 第四章，分析线状要素化简算法产生要素冲突的原因，讨论现有的几 种解决该问题的算法，重点研究如何解决d o u g l a s p e u c k e r 算法产生的相交 与自相交，主要包括利用平面扫视法从整体上判断化简产生的相交线段， 并采用局部扩充策略消除判断所得的相交线段。 第五章，介绍了线状要素化简算法的评价指标，对线状要素化简系统 进行设计，主要包括预处理模块、化简模块和算法评价模块，并以等高线 数据为依托进行实验，验证了本文工作的正确性与可行性。 最后，总结论文工作，阐述了论文的不足并对今后线状要素化简算法 的发展方向做出了展望。 西南交通大学硕士研究生学位论文第8 页 第2 章曲线数据的预处理 2 1 空间数据质量 2 1 1 空间数据质量的概念 空间位置、专题特征以及时间是表达现实世界空间变化的三个基本要 素。空间数据是有关空间位置、专题特征以及时间信息的符号记录。而数 据质量则是空间数据在表达这三个基本要素时，所能够达到的准确性、一 致性、完整性，以及它们三者之间统一性的程度”“。 空间数据是对现实世界中空间特征和过程的抽象表达。由于现实世界 的复杂性和模糊性，以及人类认识和表达能力的局限性，这种抽象表达总 是不可能完全达到真值的，而只能在一定程度上接近真实值。从这种意义 上讲，数据质量发生问题是不可避免的；另一方面，对空间数据的处理也 会导致一定的质量问题。例如，在某些应用中，用户可能根据需要来对数 据进行定的删减或扩充，这对数据记录本身来说也是一种误差。 因此，空间数据质量的好坏是一个相对概念，并具有一定程度的针对 性。尽管如此，我们仍可以脱离具体的应用，从空间数据存在的客观规律 性出发来对空间数据的质量进行评估和控制。 2 1 2 空间数据质量标准 空间数据质量标准是生产、使用和评价空间数据的依据。数据质量是 数据整体性能的综合体现。目前，世界上已经建立了一些数据质量标准， 如美国f g d c ( 美国联邦地理数据委员会) 的数据质量标准等。 空间数据质量标准的建立必须考虑空间过程和现象的认知、表达、处 理、再现等全过程。空间数据质量标准要素及其内容如下： ( 1 ) 数据情况说明：要求对地理数据的来源、数据内容及其处理过程 等作出准确、全面和详尽的说明。 西南交通大学硕士研究生学位论文第9 页 ( 2 ) 位置精度( 或称定位精度) ：指空间实体的坐标数据与实体真实位 置的接近程度，常表现为空间三维坐标数据的精度。包括数学基础精度、 平面精度、高程精度、接边精度、形状再现精度( 形状保真度) 等。平面 精度和高程精度又可分为相对精度和绝对精度。 ( 3 ) 属性精度：指空间实体的属性值与真值相符的程度。通常取决于 地理数据的类型，且常常与位置精度有关，包括要素分类与代码的正确性、 要素属性值的准确性及其名称的正确性等。 ( 4 ) 时间精度：指数据的现势性。可以通过数据更新的时间和频度来 表现。 ( 5 ) 逻辑一致性：指地理数据关系上的可靠性，包括数据结构、数据 内容( 包括空间特征、专题特征和时间特征) ，以及拓扑性质上的内在一 致性。 ( 6 ) 数据完整性：指地理数据在范围、内容及结构等方面满足所有要 求的完整程度，包括数据范围、空间实体类型、空间关系分类、属性特征 分类等方面的完整性。 ( 7 ) 表达形式的合理性：主要指数据抽象、数据表达与真实地理世界 的吻合性，包括空间特征、专题特征和时间特征表达的合理性等。 2 1 3 误差的来源及类型 空间数据的质量通常用误差来衡量，而误差定义为空间数据观测值与 其真值的差别。g i s 中的误差是指g i s 中描述的物体与其在现实世界中的 真实情况的差别。这些误差的类别包括随机误差、系统误差以及粗差。 数据是通过对现实世界中的实体进行解译、量测、数据输入、空间数 据处理以及数据表示而完成的。其中每一个过程均有可能产生误差，从而 导致相当数量的误差积累。例如，g i s 的原始录入数据本身包含着数据采 集过程中引入的源误差；另外，在原始数据录入到空间数据库以及随后的 数据分析处理和结果输出过程中，也会引入新的误差。图2 - 1 显示了g i s 中数据的误差源。“。 根据p _ a b u r r o u g h ( 1 9 8 6 ) 的建议“，可以将g i s 数据误差的来源 归纳为三类，如表2 1 所示。 西南交通大学硕士研究生学位论文第1 0 页 r 。一 _ 引 i 一 同 f 菱霎b l 二一 数据源及产生过程_ _ 卜 g i s 中的误差源 圈2 - 1g i s 数据的误差源” 表2 1 空间数据误差的来源“ 误差类型误差来源误差特征 数据年代；数据的空间覆盖范围：地图比例尺；观 明显 明显误差( 源误差)测数据的密度及其分布模式：数据格式；数据与用 易探测 途的一致性：数据的采集处理费用 由自然变化或原始位置误差；属性误差：质量和数量方面的误差：数不明显 测量引起的误差据偏差；输入输出错误、观测者偏差；自然变化 难探测 计算机字长引起韵误差：拓扑分析引起的误差；逻 复杂数据处理过程引起 辑误差、地图叠置操作；分类与综合引起的误差： 的误差 难探测 分类方法、分类间隔、内插方法 g 1 s 数据的来源是多方面的，主要有：直接从现场利用g p s 或全站仪 采集的数字数据、现有纸质地图的数字化数据、航空影像和遥感图像数据 或统计调查数据等。这些数据部分或全部受表2 1 中前两类误差来源的影 响。从图2 1 中可以看出，除了g i s 原始录入数据本身带有的误差外，空间 数据在g i s 的模型分析和数据处理等操作中还会引入新误差，如：由计算 机字长引起的误差，拓扑分析引入的误差等，即表2 - 1 中第三类误差。这 类误差通称为操作误差，是所有误差中最难于量测的，因为它不仅与所使 用的数据有关，而且与所采用的算法、数据结构有关。一般来说，源误差 远大于操作误差，因此，要想控$ 1 j g i s 产品的质量，良好的原始录用数据 是首要的。 西南交通大学硕士研究生学位论文第1 1 页 2 2 误差与错误的检查与编辑 在数字化系统中，表示地理现象的空间数据从几何上可以抽象为点、 线、面三类，要表现现实中的实体或现象必须有能完整地描述这些空间实 体或现象的空间数据和属性数据。对于任意一种数据来说，通过矢量数字 化或扫描数字化所获取的原始空间数据，都不可避免地存在着错误或误 差。所以，对图形数据和属性数据进行一定的检查、编辑是很有必要的。 图形数据和属性数据的误差主要包括以下几个方面： ( 1 ) 数据的不完整或重复：主要包括空间点、线、面数据的丢失或重 复、区域中心点的遗漏、栅格数据矢量化时引起的断线等； ( 2 ) 空间数据位置的不准确：主要包括空间点位的不准确、线段过长 或过短、线段的断裂、相邻多边形结点的不重合等； ( 3 ) 空间数据的比例尺不准确； ( 4 ) 空间数据的变形； ( 5 ) 空间属性和数据连接有误； ( 6 ) 属性数据不完整： 为了发现并有效消除误差或错误，一般采用如下方法进行检查： ( 1 ) 叠合比较法：是空间数据数字化正确与否的最佳检验方法，按与 原图相同的比例尺把数字化的内容绘在透明材料上，然后与原图叠合在一 起，在透光桌上仔细的观察和比较。一般，对于空间数据的比例尺不准确 和空间数据的变形马上就可以观察出来，对于空间数据的位置不完整和不 确定须用粗笔把遗漏、位置错误的地方明显地标注出来。如果数字化的范 围比较大，分块数字化时，除检查一幅图内的差错外还应核对己存入计算 机的其他图幅的接边情况； ( 2 ) 目视检查法：指在屏幕上用目视检查的方法，检查一些明显的数 字化误差与错误，包括线段过长或过短，多边形的重叠和裂口、线段的断 裂等： ( 3 ) 逻辑检查法：根据数据拓扑致性进行检验，将弧段连成多边形， 进行数字化误差的检查。另外，对属性数据的检查一般也最先用这种方法， 检查属性数据的值是否超过其取值范围。 对空间数据比例尺的不准确和变形，可以通过比例变换和纠正来处 理。 西南交通大学硕士研究生学位论文第1 2 页 对于空间数据的不完整或位置的误差，主要是利用图形编辑功能，如 删除( 目标、属性、坐标) ，修改( 平移、拷贝、连接、分裂、合并) ，插 入等操作进行处理。 2 3 曲线数据的预处理 对任意一条曲线而言，在数字化过程中，从数据集里去掉人为误差及 重复的坐标是很有必要的。应用“清洁化”软件对其筛选、整理，这些经 过清洁化的数据文件代表了化简过程的最初阶段，正如j e n k s ( 1 9 7 9 ) 指出 的：“精确、没有误差、最小的数据文件已经建立起来。用这种文件绘制， 所得到的是与原曲线几乎完全样的拷贝”。这种整理实际上是一种不可 察觉的范围内的化简，在这种化简中，不会发觉曲线有什么变化。除了曲 线的原始数据误差外，对曲线进行化简操作，作为化筒算法的起始状态和 结束状态，必须确定曲线的起点和末点。但对于封闭曲线，首、末两点位 置重合，不存在这两点的连线，化简操作无法实施。为了合理的利用化简 算法对其进行化简操作，必须用恰当的方法对封闭曲线一分为二。 2 3 1 消除重复点 在对线状要素进行数字化采样或者录入数据库时，可能会因为人为的 失误或者仪器本身的原因造成曲线数据的重复，为了保证空间数据质量， 必须对其进行处理，即消除多余的坐标点。在本文的等高线化简实验系统 中，用数组a 存放每条等高线的数据集，并动态的为其分配内存。等高线 的首、末两点作为曲线的支撑点必须保留，实施该策励的算法如下： f o r i = o t ond o i f ( ( a f 】为首点) o r ( a f 为末点) ) t h e n 输出a 【i 】点到新建的等高线数据文件： e l s ei f 似 f a - j ) t h e n 输出a 【i 】点