（地图制图学与地理信息工程专业论文）gis中自动拓扑算法研究及组件化实现.pdf

辽宁i ：程技术大学硕七学位论文 摘要 地理信息系统( g i s ) 自从上个世纪6 0 年代的创立至今近半个 世纪的时间里，随着地图学、计算机技术以及其它科学领域的发展， 不断地与其它领域的技术相融合，在技术革新及应用上得到了长足 的发展，在制图以及数据处理上也r 趋自动化。 地图拓扑信息的构建一直就是g 1 s 的一个核心问题之一，到目 前为止还没能实现拓扑信息生成的完全自动化。多边形图中的岛与 桥的干扰一直是一个急待解决的问题。 本论文的主要研究内容为： a 对实测数据进行预处理，滤除其中的噪声； b 对传统的拓扑信息生成算法进行改进，以解决拓扑信息生成 中的桥和岛的问题： c 用实测大比例尺地籍数据进行测试； d 考虑到与其它系统的兼容问题将其做成组件的形式。 关键字：g i s ；组件；自动拓扑；多边形图；桥；岛 a b s t r a c t i th a sp a s s e da b o u th a l fac e n t u r yf r o mt h e o r i g i n a t i o no ft h e g e o g r a p h i c i n f o r m a t i o n s y s t e m ( g i s ) ， t h ea u t o m a t i o n o f c a r t o g r a p h ya n dd a t ap r o c e s s i n ga r em o r ea n dm o r eh i g h e r ，a st h e d e v e l o p m e n ta n da p p l i c a t i o no fc a r t o g f a p h y ，c o m p u t e ra n dt h eo t h e r s c i e n c e s t h ea u t o m a t i o no fb u i l d i n gt o p o l o g i c a li n f o r m a t i o ni so neo ft h e c o r e so fg i s a tp f e s e n tt h ep r o b l e m so fi s l a n d sa n db r i d 2 e si nt h e p o l y g o nh a v e n tb e e ns o l v e d ，a n dt h es o o n e r ， t h eb e t t e rt os o l v e t h e m t h et o p i c so ft h isa r t i c l ea r et h o s e ： 【1 】p r e p r o c e s st b er e a jd a t et od e a lw i t ht h en o i s e ： 【2 】i m p r o v et h et r a d i t i o n a la l g o r i t h mo ft h ea u t o m a t i cb u i l d i n g o ft h et o p o l o g i c a li n f o r m a t i o n ，a n ds o l v et h ep r o b l e m so ft h ej s l a n d s a n db r i d g e si nt h ep o l y g o n ； 【3 】t e s tt h en e wa l g o r i t h mw i t ht h eb i gs c a l ed a t eo fc a d a s t r e ： 【4 】 d e s i g n a c o m p o n e n tt o r e a l i z et h ef u n c t i o no f t h e p r e 。p r o c e s s i n ga n dt h en e wa l g o r i t h m k e yw o r d s ：g i s ；c o m p o n e n t ；a u t ot o p o l o g y ；p o l y g o n ；b r i d g e ；i s l a n d 辽。f i ：程技术人学硕士学位论文 l 引言 1 1 地理信息系统的定义 地理信息系统( g i s ) 是采集、存储、管理、检索、分析和描 述整个或部分地球表面与空阃地理分布数据的空间信息系统【1 1 。它 是一种能把图形管理系统和数据管理系统有机地结合起来的信息 技术，既管理对象的位置又管理对象的其它属性，而且位置和其它 属性是自动关联的。它最基本的功能是将分散收集到的各种空间， 非空间信息输入到计算机中，建立起有相互联系的数据库。当外界 情况发生变化时，只要更改局部的数据，就可维持数据库的有效性 和现实性。g i s 是一种空间数据库管理系统，是一个动态系统，所 以不能简单地把它同地图数据库混为一谈。目前，g l s 带动的产业 急剧膨胀，已经深入到市政工程、企业决策、资源管理、交通运输、 医疗保健、邮电通信、公安急救，市场销售，会融保险、石油化工、 水利电力、环境保护、旅游、科研、教育等各个方面。 1 2 g i s 的产生和发展 g i s 技术的创立和发展，与地理空间信息的表示、处理、分析 和应用手段的不断发展紧密相连。地理信息系统起源于地图，它们 都是地理信息的载体，具有获取、存储、编辑、处理、分析与显示 地理数据的功能。 地图是地理学的第二代语言，而g i s 将成为地理学的第三代语 言。g i s 是在地图学的基础上发展起来的，可分为以下几个阶段： a 开拓发展阶段。2 0 世纪6 0 年代，由于计算机硬件系统功能 较弱，限制了软件技术的发展。这一时期的软件主要是针对当时的 主机和外设开发的，算法粗糙，图形功能有限。 b 巩固阶段。2 0 世纪7 0 年代，计算机硬件和软件技术飞速发 展，为空间数据的录入、存储、检索和输出提供了强有力的手段。 辽0 。r ：程技术人学硕十学位论文 2 用户屏幕和图形、图像卡的发展增强了人机对话和高质量的图形显 示功能，促使g i s 朝着使用方向迅速发展。由于这一时期g i s 的需 求增加，地图数字化输入技术有了一定的进展，采用人机交互方式， 易于编辑修改，提高了工作效率，并出现了扫描输入技术系统，图 形功能扩展不大，数据管理能力较小。这一时期软件最重要的进展 是人机图形交互技术的发展。 c 突破阶段。随着计算机软件、硬件技术的发展和普及，g i s 也逐渐走向成熟，这一时期是g i s 发展的重要时期。g i s 软件技术 在栅格扫描输入的数据处理、数据存储和运算方面有了很大的突 破。随着硬件技术的发展，g i s 软件处理的数据量和复杂程度大大 提高，许多软件技术固化到专用的处理器中，而且遥感影像的自动 校正、实体识别、影像增强和专家系统分析软件也明显增加。在数 据输出方面，与硬件技术相配合，g i s 软件可支持多种形式的地图 输出。在地理信息管理方面，除了d b m s 技术已经发展到支持大型 地图数据库的水平外，专门研制的适合g i s 空间关系表达和分析的 空问数据库管理系统也有了很大发展。 d 社会化阶段。进入2 0 世纪9 0 年代，随着地理信息产业的建 立和数字化信息产品在全世界的普及，g i s 已经成为许多机构必备 的工作系统，尤其是政府决策部门在一定程度上受g i s 影响改变了 现有机构的运行方式、设置与工作计划等。而且，社会对g i s 的认 识普遍提高，需求大幅度增加，从而导致g i s 应用的扩大与深化。 自2 0 世纪9 0 年代以来，我国g i s 步入快速发展阶段。它为国民经 济重大问题提供了分析和决策依据，同时g i s 的研究和应用正逐步 形成行业，具备了走向产业化的条件。 1 3g i s 中的拓扑关系及拓扑信息自动构建研究 1 3 1g i s 中的拓扑关系 拓扑空间关系是一种对空间结构进行明确定义的数学方法，具 辽宁i ：程技术大学硕士学位论文 3 有拓扑关系的矢量数据结构就是拓扑数据结构。拓扑数据结构是地 理信息系统分析和应用功能所必须的，它描述了基本空问目标点、 线、面之间的关联、邻接和包含关系。【2 】 空间查询与分析是g l s 的核心，是g i s 最重要的和最具有魅力 的功能，也是g i s 有别于其他信息系统的本质特征。 空间查询与分析的基础是空间关系。空间关系包含三种基本类 型：拓扑关系、顺序关系以及度量关系。空间关系的描述与识别非 常重要。一方面是它为地理信息系统数据库的有效建立、空间查询 空自j 分析、辅助决策等提供了最基础的关系，另一方面是将空自j 关 系理论应用于地理信息系统查询语言，形成一个标准的s q l 空间查 询语言，从而通过应用程序进行空间特征的存储、提取、查询、更 新等。1 3 1 1 3 2 拓扑自动构建研究 从原始数据到拓扑空自j 关系的自动生成技术，即空白j 关系的自 动构建技术，一直是g i s 领域地研究的难点。 目前，对拓扑多边形的自动构建算法，学者们的研究各有侧重 点，但基本上都是从自动化程度、时间效率和算法的复杂性出发来 进行优化与改进的，其早期的算法一般都离不开人工干预，这对全 自动成图是不利的。f 4 j 文献【5 】提出了一种基于方位角计算的多边形自动构建快速算 法，该算法的时间效率较高，思路清晰易懂，程序实现的工作量较 小，但在确定多边形拓扑关系时，容易对多边形的相接，交叠等关 系产生错误的判断。 本文就是基于文献【5 】中的单个多边形自动构建的思想，采用自 己构建的三层拓扑的模型来完善传统算法中的交叠，相接等关系豹 判断，而且还对一直困扰着拓扑信息完全自动构建的桥和岛的问题 加以了解决，从而完全实现了拓扑信息构建的自动化。 由于实测的原始数据有其普遍性，能够将实际的情况真实地反 辽j 。j i ：程技术人学硕十学位论文 4 应出来，能够对算法的性能以及可靠性进行很好的测试，也利于在 投入生产中的适用性测试。所以，本文中使用的测试数据为实测数 据。 随之而来的就需要先对实测数据进行预处理，过滤其中的在构 建拓扑信息中的噪声，使拓扑能够顺利构建，同时也是对原始数据 的一次整合，使其与实际数据更加吻合。 辽宁。r 程技术人学硕十学馈论文5 2 组件技术与组件式g i s 2 1 组件及组件技术 2 1 1 组件的产生 随着计算机应用的功能越来越强大、实现越来越灵活，在过去 2 0 年或者更久的一段时间里，在软件开发领域遇到了一系列让人棘 手的问题，主要体现在以下几个方面【6 】： a 软件开发周期长，难于维护。 b 软件复杂度增加，管理大规模的程序代码困难。 c 软件升级和更新总是牵一发而动全身，大多数功能难以扩 展。 d 软件开发过程中重复工作较多，各个应用之自j 不易集成，一 个应用的数据和功能不能为另一个使用，即使它们是使用相同的语 言编写运行在同一个环境下。 在计算机领域，硬件技术及硬件性能的提高速度总是快于软 件，人们使用传统的软件设计方法己经远远不够。软件开发领域是 一个新的领域，这一领域工作的技术偏好者，他们必须想尽办法跟 上技术和方法的更新步伐。经过不懈的探索与尝试，人们曾相继采 用a p i 函数、面向对象程序设计等方法试图解决如上所述的在软件 开发中遇到的这一系列问题，但效果都不是很理想。面对复杂的分 布式应用，简单代码重用的面向对象设计方法已经显得力不从心， 重任最后落在了软件复用技术上。软件复用技术有很多种，最常用 最快捷也最有效的方法即是组装技术。组装技术的核心即是组件。 2 1 2 组件的概念及其基本属性 组件( c o m p o n e n t ) 也称构件或软构件。如今这几个名词己成为软 件界的热门话题，但对于究竟什么是组件，不同的学者有不同的理 解。下面是软件行业对组件的一些具有代表性的观点i7 】： 辽。l ：程技术人学硕+ 学位论文 6 a 组件是软件的基本量子，它具有一定的功能，可插用、可维 护。 b 组件是欹件开发中一个可以替换的单元，它封装了设计决 策，并作为一个在单元和其他组件组合起来。 c 组件是具有特定功能的，能跨越进程边界，实现网络、语言、 应用程序、开发工具和操作系统的“即插即用”的独立对象。 d 组件是指任何可被分离出来，具有标准化的、可重用的公开 接口软件。 无论从哪个角度来理解组件，其本质属性是不变的： a 组件是可独立配置的单元，内部独立设计、独立开发，可进 行独立测试，独立发布。 b 组件强调和其他组件的分离，因此组件的实现是严格封装 的，外界没有机会或没有必要知道组件内部的实现细节，为了尽可 能的消除软件之间或者是软件的不同部分之问的联系，组件内部强 调强内聚、组件之间追求松耦合。 c 组件可以在适当的环境中被不同形式的或不同层次的重复 使用，因此组件需要提供清楚的接口规范，可以与环境交互。 2 1 3 组件技术 在软件开发领域，一场新的革命正在悄悄兴起，这是由同趋成 熟的组件技术引发的。几年以i j ，当微软公司首先使用o l e 的时候， 其初衷是为了增强软件的互操作性。然而在使用过程中，人们逐渐 认识到这一技术背后的实质性内容和它在软件开发中所扮演的重 要角色。组件技术将以i ；i f 所未有的方式提高软件产业的生产效率， 这一点已逐步成为软件开发人员的共识。传统的c l i e n t s e r v e ：结 构、群件、中间件等大型软件系统的构成形式，都将在组件的基础 上重新构造。 组件技术的基本思想是： 将大而复杂的软件应用分成一系列的可独立实现、易于开发、 辽j i ：稃技术_ 人学硕十学位论文7 理解和调整的软件单元，也就是组件，每一个组件保持一定的功能 独立性，在协同工作时，它们通过相互之间的接口完成实际的任务。 应用组件思想进行软件开发，首先要根据软件的要求，按照不同的 应用功能将软件划分为各个组件模块。这些组件可以是不同厂商在 不同时期用不同的程序语言开发的，可以在不同操作系统的机器上 运行。不同的组件设计者再也不必担心自己所从事的这一部分不被 其它相关组件或整个系统所接纳，只要各个组件问提供一个能进行 互操作的接口即可。组件问的接口通过一种与平台无关的语言 i d l ( i n t e r f a c ed e f i n el a n g u a g e ) 来定义，而且是二进制兼容的，使 用者可以直接调用执行模块来获得对象提供的服务。早期的类库， 提供的是原代码级的重用，只适用于比较小规模的开发形式；而组件 则封装得更加彻底，更易于使用，并且不限于c + + 之类的语言，可 以在各种开发语言和开发环境中使用。 组件技术使近二十年来兴起的面向对象技术进入到成熟的实 用化阶段。在组件技术的概念模式下，软件系统可以被视为相互协 同工作的对象集合，其中每个对象都会提供特定的服务，发出特定 的消息，并且以标准形式公布出来，以便其他对象了解和调用。 软件组件技术是实现组件重用的核心技术之一，它包括组件建 模与实现、组件描述、组件分类与检索、组件获取以及组件组装等。 组件建模与实现是根据组件在领域中的功能和接口的需要设计算 法模型，并在某种语言环境下予以实现。组件描述是以组件模型为 基础，对组件的结构和功能进行描述，以增强组件的可用性。组件 分类与检索是根据组件的分类策略、组织模式及检索策略，建立组 件库系统，支持组件的可用性。组件获取是根据系统的功能需求， 在组件描述、分析和检索技术支持之下从组件库或已有系统中挖掘 提取组件。 从广义上讲，组件技术是基于面向对象的，以嵌入后马上可以 使用的即插即用型软构件概念为中心，通过组件的组合来建立应用 的技术体系。狭义上讲，它是通过组件组合支持应用的开发环境和 辽0 。i ：程技术人学硕十学位论文8 系统的总称。目前，采用组件思想开发的软件产品已相继出台，代 表了新一代软件开发的趋势，所带来的好处是人们所无法估量的。 2 2 组件式g i s 组件式g i s ( c o m p o n e n t sg i s ) 简称c o m g i s ，是由一系列可拆分、 可协作、可裁剪的g i s 组件构成的具有高度伸缩性的g i s 软件平台， 指基于组件对象平台、以一组具有某种标准通信接口的、允许跨语 言应用的组件提供的g i s 。这种组件称为g i s 组件。g i s 组件之问 以及g i s 组件与其它组件之间可以通过接口进行交互。组件接口技 术的出现使得g i s 底层处理过程的封装成了可能，即用户并不需要 确切的懂得对地理空闻数据以及关系的详细处理算法，便可以很轻 松使用软件提供商提供的控件或自动化服务器来进行开发，从而定 制自己所需的各种软件界面或完成自己所需要的任何功能。 2 2 1g i s 的组件化发展趋势 地理信息系统技术正处于一个重要的发展时期，新概念和新产 品层出不穷。在g i s 蓬勃发展的今天，g i s 的组件化发展趋势r 益 明显，已经成为g i s 的重要发展方向之一。g i s 的发展历程可以划 分为如图2 一l 所示的几个阶段，了解这一历程可以更好地认识g i s 组件化的趋势。 图2 lg i s 软件技术发展历程 匾 辽宁：i ：程技术人学硕十学位论文 9 在g i s 发展的早期阶段，由于受到技术的限制，g i s 软件往往 是只能满足于某些功能要求的一些模块，没有形成完整的系统，而 且各个模块之间不具备协同工作的能力。 随着理论和技术的发展，各种g i s 模块走向集成。逐步形成大 型g l s 软件包( g i sp a c k a g e ) ，即集成式g i s ( i n t e g r a t e dg i s ) 。例 如，e s r i 的的a r c i n f o 、g e n a s y s 的g e n a m a p 等均为集成式g i s 的 代表。集成式g i s 是g i s 发展的一个重要里程碑。优点在于其集成 了g i s 各项功能，形成独立完整的系统；缺点在于系统复杂、庞大， 从而导致高成本，难与其他应用或系统集成等。 另一类g i s 为随后出现的模块化g i s ( m o d u l a fg i s ) ，代表软 件有i n t e r g r a p h 的m g e 等。模块化g i s 的基本思想是把g i s 按照 功能划分为一系列模块，运行于统一的基础环境之上( 如 m i c r o s t a t i o n ) 。尽管许多集成式g i s 软件也可以划分为几个模块， 但模块化g i s 软件的模块被有目的地划分得更细。模块化g i s 具有 较大的工程针对性，便于开发和应用，用户可以根据需要选择所需 模块。但无论是集成式g i s 还是模块化g i s ，都很难与管理信息系 统以及专业应用模型集成高效、无缝的g i s 应用。 为了克服集成式g i s 与模块化g i s 的缺点，提出了核心式g i s ( c o f eg i s ) 的概念。核心式g i s 被设计为操作系统得基本扩展。 w i n d o w s 系列操作系统上的核心式g i s 提供了一系列动态连接库 ( d l l ) ，开发g i s 应用系统时可以采用现有的高级编程语言，通过 应用程序接口( a p i ) 访问内核所提供的g i s 功能。除了一些基本 得动态连接库以外，实现各种功能的动态连接库可以被拆卸和重 组。它提供了动态连接库一级的更底层的组件化方式，给用户提供 更大的灵活性。对数据库管理要求较多的用户甚至可以选择m i s 开 发工具构造g i s 应用系统，为g i s 与m i s 的无缝集成提供了全新的 解决思路。但是，核心式g i s 提供的组件过于底层，给应用开发者 带来一定难度，也不适应可视化程序设计的潮流。 随着计算机软件技术的发展，g i s 组件化发展到了一个全新的 辽宁i ：程技术人学硕+ 学位论文 l o g i s 基于标准的组件式平台，各阶段，出现了组件式g i s 。组件式 个组件之间不仅可以进行自由、灵活的重组，而且具有可视化的界 面和使用方便的标准接口。组件式平台主要有m i c r o s o f t 的c 0 m d c o m 和0 m g 的公共对象请求代理体系结构( c o m m o no b j e c t r e q u e s tb r o k e ra r c h “e c t u f e ，c o r b a ) 。目前，m i c r o s o f t 的c o m d c o m 占市场领导地位。基于应用为广泛的标准组件。新一代的组 件式g i s 也大都是a c t i v e x 空问或者其前身o l e 控件。组件式g i s 代表着当今g i s 发展的潮流。 国际上大多数g i s 软件公司把开发组件式软件作为重要的发展 战略。i n t e r g r a p h 公司声称已经进入组件式g i s 的时代，它推出的 g e o m e d i a 组件式g i s 软件是其庞大的j u p “e r 计划中的一部分e s r i 和m a p i n f o 也分别推出了m a p o b j e c t 和m a p x 。我国也正在研制国 产的组件式g i s 软件一一a c t i v e m a p ( 其升级版本现在更名为 s u p e r m a p ) 。它已经再“香港综合地理信息系统”、“南宁市土地信 息系统”、“香港之窗”等系统中成功应用并得到实践检验。 从g i s 模块发展到集成式g i s 式从分散到集中的过程，这是 g i s 发展历程中的一个重大进步。从集成式g i s 发展到模块化g i s ， 这是g i s 组件化的开始，随后发展到核心式g i s ，g l s 组件化趋势 越来越明显，并形成组件化的标准形式一一组件式g i s 和 w e b g i s 【10 1 。 2 2 2 组件式g i s 的特点 地理信息系统功能的涵盖范围非常广泛，包括图形操作、图像 处理、地图制图等涉及不同专业的各个领域。利用组件技术，可以 将不同专业领域的功能实现为组件，可以将满足不同功能的g i s 组 件组装起来，形成应用系统，这就是组件式g i s 系统开发的基本思 想。利用组件技术开发g i s 软件，除能够实现复用、互操作功能外， 还有以下传统g i s 开发方式所无法比拟的优点： a 小巧灵活、价格便宜。在组件模型下，各组件都集中地实现 辽宁t 程技术人学硕十学位论文l l 与自己最紧密相关的系统功能。组件化的g i s 平台集中提供空自j 数 据管理能力，并且能以灵活的方式与数据库系统连接。在保证功能 的前提下，系统表现得小巧灵活。 b 易于集成。组件的生产建立在严格的标准之上，因此，凡符 合标准的组件都可在目前流行的各种开发工具上使用。这样，v b 、 v c 、d e l p h i 、p o w e r b u i l d e r 、f o x p f o ：a c c e s s 等都可直接成为g i s 的优秀开发工具，它们各自的优点都能够得到充分发挥。这与传统 g l s 专门性开发环境相比，是一种质的飞跃。 c 强大的g i s 功能。新的g i s 组件都是基于3 2 位或更高系统 平台的，无论是管理大数据的能力还是处理速度方面均不比传统 g i s 软件逊色。小小的g i s 组件完全能提供拼接、裁剪、叠合、缓 冲区等空间处理能力和丰富的空问查询与分析能力。 d 伸缩性好，可扩展性强。由于传统g i s 结构的封装性，软件 变得越来越庞大，系统的开发难度很大。c o m g i s 提供空间数据的 采集、存储、管理、分析和模拟等功能，至于其它非g i s 功能则可 以使用专业厂商提供的专门组件( 如关系数据库管理、统计图表制作 等) 。在组件式软件技术背后，有一个十分庞大的组件资源库，用户 可以从不计其数的组件中挑选需要的组件和组件g i s 一起集成应用 系统，极大地扩展了g i s 的功能。 另外，传统的g l s 软件与用户或者二次开发者之间的交互，一 般通过菜单或工具条按钮、命令以及二次开发语言进行。c o m g i s 与用户和客户程序则主要是通过属性、方法和事件交互侧，如图2 2 所示。 图2 2c o m g l s 与集成环境及其他组件之间的交互 微软于2 0 0 2 年隆重推出了v is u a ls t u d i o n e tf r a m e w o r k 开发 平台，它通过把源代码编译为m i c r o s o f t 中间语占( i n t e r m e d i a t e 鬟 辽宁t ：程技术人学硕十学位论文 1 2 l a n g u a g e ) 然后公共语言运行库( c o m m o nl a n g u a g er u n t i m e ) 把 中白j 语言编译为平台专用的代码。这样不仅支持平台无关性，还支 持了语言的互操作性【1 1 】。由于上述n e t 的新的优良的特性，近年来 c o m 技术呈现出了逐渐被取代的趋势。 虽然v s n e t 有上述的诸多的优越性，但是它的这些优势都是 集中体现在最底层的开发中，而现有的绝大多数g i s 系统用的开发 平台是以前的非n e t 平台编制的，若是将其升级到n e t 语言不但需 要大量精通当初开发语言以及n e t 语言的程序开发人员，而且还是 一个相当庞大的工程。 而且现在的g i s 系统开发都是基于其它已有g i s 平台的二次开 发，当前的g i s 开发平台在功能上已经基本完善，只是在某些功能 方面有所欠缺，要是将其完全升级到新的n e t 开发平台，要消耗大 量的人力、物力以及时间，所以会得不偿失。 针对以上的具体问题，而且本设计的内容也只是g i s 数据处理 中的一个功能模块，并不是一个完善的系统，所以仍采用组件技术 来解决与已有软件的兼容问题。 辽，i ：程技术人学硕士学位论文 1 3 3 数据预处理 数据预处理在g i s 中起着重要的作用，数据预处理结果是否正 确关系到矢量数据的拓扑关系能否正确生成，并且数据预处理是进 行数据分析的最基础也是最繁琐的工作。数据预处理中最为重要的 算法主要是弧段的相交判断及处理以及结点匹配算法，提高这两个 算法的效率和自动化程度可以大大减轻编辑者的工作量，提高工作 效率 12 1 。 数据预处理的主要功能有删除重复弧段、相交弧段的判断和处 理、结点匹配、悬弧处理以及合并假弧段。 3 1 删除重复弧段 重复弧段既可能相交也可能不相交，相交时的交点可能有多 个，所以应将此功能放在相交弧段处理之前。而重复弧是指两条弧 之间的最大距离小于系统容差的弧。在未做结点匹配之前，重复弧 的首尾结点一般并不相同。 弧段重复可分为部分重合和完全重合两种情况。 具体的解决方法如下： 如图3 1 中a 所示，弧段l l 由点p 1 1 ，p 1 2 ，p 1 n ，p 1 m 构成， 弧段l 2 由p 2 1 ，p 2 2 ，p 2 n ，p 2 m 构成。 l l p 1 lp 1 2 ， p 2 lp 2 2 a b 图3 1 弧段重合处理示意圈 先比较弧段l l ，l 2 相同或相近( 在容差范围之内) 的结点p 1 ( p 1 1 ) 的下一个结点p 1 2 与p 2 2 ，若坐标相同或相近则继续比较下 。 步t 阻 一 么一比 辽f j ：1 ：程技术人学硕+ 学位论文1 4 一节点p l3 与p 2 3 ，否则在比较点的前一点如图3 1 所示点p ln ( p 2 n ) 处将弧段l 2 断开，其后的部分的点p 2 n ，p 2 m 构成新的弧段l 2 ， 如图3 - l 中b 所示。 如果两条弧段完全重合，则将只保留一条弧段，将另一条弧段 直接删除。 3 2 相交弧段的判断和处理 对于数字化的多边形图层大多数相交出现在弧段的首尾结点 附近，可以让程序自动处理这些相交情况，对于其它较少的相交情 况可以交给用户处理。这里涉及的最基本的算法是线段的相交判断 算法，算法需全面考虑各种相交情况，并做出正确判断。 线段相交算法是最基本的算法，弧段相交判断最终也是判断线 段是否相交。图3 2 总结了线段相交的所有情况，主要有以下几种： a d 人，。 图3 2 线段相交情况图 a 交点位于两条线段的内部； b 两条线段相交于端点； e c c 交点是其中的一条线段的一个端点； d 线段的4 个点共线并且有重叠； e 当点p 4 与线段p lp 2 的距离小于容差时为由于实测时造成 的误差，当大于容差时为不相交。 其它情况不相交。对于两条线段相交于端点的情况，在进行弧 辽宁l ：样技术人学硕十学位论文 1 5 段相交判断时，需区分交点是弧段的结点还是弧段的节点( 非端 点) ，只有在交点是弧段的节点时，才判断相交。 当前对于计算线段相交的算法主要有：参数方程法，符号判断 法以及混合积法。 3 2 1 参数方程法 线段a 仍的参数方程为善= 而+ f ( 而一毛) ，y = m + f ( y 2 一只) ，线段死p 4 的参数方程为工= 屯+ s ( x 。一而) ，j ，= 乃+ s ( j ，一乃) ，两个方程合起来求解 参数f 和5 得： f = ( ( 工3 一而) ( y 3 一y 4 ) 一( x 3 一工4 ) 0 3 一y 1 ) ) “x 2 一x j ，3 一y 4 ) 一( 工3 一x 4 ) ( y 2 一y j ) ) ( 3 一1 ) j = ( ( x 2 一而) o ，3 一乃) 一( 而一而) ( y 2 一乃) ) ( ( 屯一而) ( y 3 一) ，。) 一( 毛一工4 ) ( y 2 一_ ) ，l ”一( 3 - 2 ) a o ， l 并且0 s 1 b ( t = o 或t = 1 ) 且( s = o 或s = 1 ) c t = o 并且o s l ，或t = l 并且o s o 或s o ，s ls 2 位于s 3 s 4 的同一侧，如果s l s 2 o ，点s ls 2 位 于s 3s 4 所在直线的两侧，反之办然。由s 1 ，s 2 ，s 3 ，s 4 的符号可 辽宁r ：程技术大学硕十学位论文 1 6 判断出图示的各种情况： a s l s 2 o 且s 孙4 o 3 2 3 混合积算法 上述两种方法都是先求解方程组，再通过对解的合理性的判断 来确定线段是否相交。这种思路必然会因为求解方程组而带来大量 的计算，影响效率。在g i s 中经常需要判断一条线段与许多条链的 相交关系，而其中满足相交关系的链的数目是比较少的，即使用线 段的外接矩形进行过滤，也会有许多不可能相交的线段参与了计 算。因此，提高效率的关键在于提高判定方法的质量，排除干扰链 【t ”。 3 2 3 1 混合积的概念 设存在3 个向量a ，b ，c ，先作a 与b 的向量积，把所得到的 向量再与向量c 作数量积6 ) f ，这样得到的数量积叫做3 向量的 混合积。记作l 加c 】。它是一个数，它的绝对值表示以向量a ，b ，c 为棱的平行六面体的体积。如果向量a ，b ，c 组成右手系( 即c 的 方向按右手规则从a 转向b 来确定) ，那么，混合积为i f ；反之， 若成左手系( 即c 的方向按左手规则从a 转向b 来确定) ，那么，混 合积为负。 3 2 3 2 混合积判定准则 设有两条线段只最，q l q 2 ，如图3 3 所示 只z ，q 1 z ，垂直置b ，q l q 2 所在平面。 则线段只最，q lq 2 相交的判定条件，即充分必要条件是 彦耋嚣墓悠q 只笔最只乏象。复 们蚣qq l 最q 。z 】协q 2q 1 最q l z lj o2j 辽卜i ：程技术人学硕十学位论文1 7 证明： 充分性： 因为两线段相交等价于任意一条线段的两个端点在另外一条 线段的两侧 由混合积概念且。o 所以q i ，q 2 在线段只b 两侧 由混合积概念且：s o 所以只，最在线段q lq 2 两侧 所以线段只最，q 1q 2 相交 必要性： 由混合积定义计算必有 1 0 且2 o 综上，判断准则得证。 z l p l 图3 - 3 混合积相交算法原理示意图 注：，：为o 包含了顶点重合、线段重合、顶点在线段上3 种情况。 下面化简判定条件，由混合积计算公式 )5 - 3( 吒屯巳 乃以旬 以以巳 = d 6 ，p 辽0 r 程技术人学硕七学位论文 1 8 取只z ，q l z 。为单位向量( o ，0 ，1 ) ，其他向量的第3 维分量全 部为0 。 则有 。= g 1p 2 。p l q 。一p l p 2 。p 1 q 。) ( 只罡。只幺，一日最，量q ：，) o ：= ( 蜴q 2 。q 1 只，一q l q 2 ，q 1 只，地q 2 ，q l 最，一q q 2 ，q l 足。) o 算法流程图，如图3 - 4 所示： 图3 - 4 混合积算法流程圈 运用混合积判定准则，不用解方程组，通过简单而又准确的乘 法运算便可判定线段是否相交，可以大大的提高运算速度。 由于混合积法有上述的优点，所以本设计就是采用的混合积来 判断和处理线段相交。 3 2 4 特殊情况处理 除了正常的相交外还有两种特殊的情况即图3 2 中的d 、e 两 种情况。 对于上述两种情况进行单独的处理。 3 2 4 1 处理有4 个点共线并且有重叠的情况 4 个点共线并重叠有两种情况： a 两线段有一部分重叠。 b 一条线段在另一条线段内部。 堑! ：三；塑壁查盔堂堡主兰垡笙苎 ! ! 对于a 的情况，将待定线段的重叠部分的端点替换为基准线段 重叠部分的端点。如图3 5 所示。 p ip l ( 1 )( 2 ) 图3 5两条线段只有一部分重叠 对于b 的情况，以短线段的端点为分割点将长线段分割为三条 线段。如图3 6 所示。 ( 1 )( 2 ) 图3 6 一条线段在另一条线段内部 3 2 4 2 处理由于误差造成的悬空相交的情况 当两条线段p l p 2 ，p 3 p 4 不相交时，计算它们的虚交点q 。如 果此虚交点在其中一条线段p 1p 2 上，且q 距线段p 1p 2 的近端点 p 3 的距离小于容差，则将为线段p 3 p 4 延长至虚交点q ，并以此虚 交点q 为分割点，将线段p 1p 2 分割为两条线段p 1q 和q p 2 ，如图 3 7 所示。 图3 7 线段悬空相交处理示意图 辽1 ：程技术人学硕十学位论文 3 3 结点匹配 结点是指线目标( 或称弧段) 的端点。 结点匹配是指把一定限差内弧段的端点作为一个结点。 结点匹配可以有两种方法来完成，一种是全自动方式，给定一 个阈值，让所有的结点自动匹配；另一种是在编辑功能中加入智能 捕捉功能，移动结点时，该结点自动匹配到附近的结点上。该方法 适用于少量结点的匹配。 结点匹配算法设计： 在结点匹配中需重点考虑的问题是，经过结点匹配以后保证不 产生新的错误，这晕的主要错误是指产生新的相交，这样用户又必 须反过来处理相交情况，以至于对一幅图要生成正确的拓扑关系需 反复重复一些步骤，用户操作起来很不方便。 在找到容差范围内的若干个结点后，并不能简单地求出这些结 点的坐标平均值，然后将这些结点的坐标修币为它们的平均值，在 很多情况下会产生新的相交。如果采用求凸壳法，可以解决这个问 题。凸壳是包含若干个点的最小凸多边形。对于可以生成凸壳的情 况，判断各结点所在的弧段与凸壳的相交情况，凸壳内部包含的弧 段删除，新生成的弧段是凸壳的中心点和弧段与凸壳的交点的连 线。如图3 8 结点l 、2 ，3 的凸壳是由它们组成的三角形，c 中。是 三角形的重心，p 是弧段与三角形的交点，p o 是新生成的弧段，d 是结点匹配后的结果。 对于不能形成凸壳的情况( 有点重合或共线) ，可采用以下算 法：求出要匹配的点的平均坐标点，以此点为圆心，一定的阈值为 半径画圆，落在圆内的弧段删除，以圆心为结点，形成新的弧段。 如图3 9 所示弧段l 1 ，l 2 共一端点p l ，p 1 与p 2 点进行匹配，o 为p l 、p 2 的中心点，即圆心，c 是匹配的结果。这种方法最后生成 的结果合理，并且实践证明可以避免产生新的相交。 辽+ 卜i ：程技术人学硕十学位论文 2 l 图3 8 结点匹配( 存在凸壳) 3 4 悬弧处理 图3 9 结点匹配( 不存在凸壳) 悬弧是指没有与周围的弧段建立起关联关系的弧段。悬弧至少 有一个结点是悬挂结点。 形成悬弧的原因及处理方法： a 由于输入时误差较大，与附近的结点的距离超过结点匹配给 定的阈值。可增大阈值或人工编辑让其匹配。 b 由于周围弧段在交点处没有断开，需人工编辑断开。 c 错误的输入，直接删除。 如果悬弧数量很大，可重新作一次结点匹配，增大匹配阈值， l 辽j 。：l ：程技术人学硕+ 学位论文 很大一部分悬弧可自动处理，剩下的需交给用户编辑处理。 3 5 合并假弧段 在多边形层中，任一结点至少连接三条弧段。如果一个结点只 连接了两条弧段，那么这个结点为假结点，这两条弧段为假弧段。 当遇到假结点时，将假结点连接的两条假弧段合并为一条弧 段。 辽0 。i ：稃技术人学硕+ 学位论文 4 拓扑信息自动生成的原理及实现 4 1 多边形图简介 多边形图是g i s 中一种重要的图形类型，常常用来描述面状分 布的地图要素：如土壤图、地貌图、土地利用图等等。这类图型的 重要特点是每个图斑都是一个连通区域，有明确的界线。区域和界 线是多边形图的两个基本要素。对基本要素进行研究，找出内部联 系及其规律是g i s 的基本理论问题之一。而且g i s 中多边形图的处 理软件功能和性能的提高均直接依赖于两个基本要素的新知识。 如：左转算法的发现导致了单个多边形拓扑信息生成的自动化；点 与多边形包含关系的判断定理使得岛区判定实现了计算机处理。多 边形是多边形图的基本组成成份，对于多边形的性质及其在g i s 的 算法有不少文章作过论述。然而，多边形只是多边形图的个体，个 体的性质只是整体性质的一部分，根据个体性质得出的多边形拓扑 信息就单个多边形而言是正确的，而对于整幅多边形图而言则有可 能出现不一致甚至矛盾的拓扑信息1 4 】。 g i s 中的多边形图从其区域特性上看，每个多边形是一个连通 区域( 区内的任意两点之间都有一条位于区内的路径) 。对于连通 区域，引进一个重要概念： 连通区域：设平面上由一条封闭曲线围成的区域d ，如果d 中 的任意一条闭合曲线，可以不经过d 的边界而连续地收缩成一点， 则称d 为单连通区域，否则称为复连通区域。 图4 一l 中a 为单连通区域，b 为复连通区域，因为区域内有 的闭合曲线不可能在此区域内部收缩成一点，如要收缩成一点，必 需经过区域的内边界线。 沿连通区域d 的外( 内) 边界线走一周回到出发点，若区域d 位于前进方向的左侧，则前进方向定义为连通区域d 的外( 内) 边 界线的方向。 辽宁_ 1 ：程技术人学硕十学位论文 2 4 多边形图中不含岛区的多边形称为简单多边形，表示单连通区 域；含岛区的多边形称复合多边形，表示复连通区域。岛区多边形 看作是复连通区域的内部边界。 秽够 图4 l 单连通区域与复连通区域 多边形拓扑信息是指一个多边形由哪些弧段组成及其组成弧 段在多边形上的邻接关系。其目的在于表示平面上的连通区域。 多边形图的拓扑信息是指图上全部多边形的拓扑信息及这些 信息间的关系。 g i s 中的多边形图，输入的是弧段，所要描述的是连通区域， 拓扑信息是用弧段表示连通区域必不可少的数据。在g i s 的初级阶 段，这些数据靠手工采集，手工输入，随着对多边形图性质认识的 加深，逐步实现了计算机自动生成。 封闭多边形拓扑信息的形成可简单描述为：沿任意一条弧段i i 进，到达终点时向左转，顺次遍历所有与该终点相接的弧段，沿着 最后遇到的一条弧段继续前进，如此重复直至回到出发点，依次经 过的弧段即形成一个封闭的多边形。这一算法思想可形成单个封闭 多边形，对于整个一幅多边形图，含有的多边形常常不止一个，可 重复形成一些多边形，也可能遗漏一些多边形。要使每一个多边形 的拓扑信息形成一次且仅形成一次可根据下节的定理或公理设计 算法。 辽r i ：程技术大学硕十学位论文 4 2 多边形图的性质 定义l ：平面上一条不自相交的有向封闭曲线形成的图形叫多 边形。该曲线叫做多边形的边，从曲线上任意一点出发沿曲线静进 一周回到出发点，前进方向左侧所对应的部分平面叫做多边形的区 域。前进的方向叫多边形边的方向。在g i s 中常常将多边形的边分 割成弧段，分割点一般位于三个( 或三个以上) 多边形的邻接点。 沿一个多边形的边并按它的方向前进一周遍历它的所有弧段，弧段 编号依次为。e 1 ，e 2 e n 遍历的弧段数为n ，数据序列n ，e 1 ，f 1 ， e 2 ，f 2 e n ，f n ( 当前进方向与弧段方同相同时，f 为l ，否则f 为 ， o ) 叫做多边形拓扑信息。 公理l ：多边形将其所在平面分割成两个区域，有且仅有一个 区域含有平面上的无穷远点。 由定义l 及公理l 可知：一条封闭曲线由于有两个方向，因而 代表两个不同多边形的边。有且仅有一个多边形的区域含有平面上 的无穷远点。 定义2 ：平面上由一条不自相交的封闭曲线构成的图形叫最简 多边形图。 公理2 ：最简多边形图含有两个多边形。 定义3 ：从最简多边形图上引有限条互不相交且不与已有的任 何曲线相交的自封闭曲线所形成的图形叫多边形图；在多边形图上 起止于多边形的边引有限条互不相交曲线，且