VegaGIS中矢量空间分析的关键算法研究

来源 :中国科学院计算技术研究所 | 被引量 : 0次 | 上传用户:zhongli2511
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
空间分析是GIS的核心和灵魂,是GIS区别于一般的信息系统、CAD或者电子地图系统的主要标志之一,也是GIS的主要技术门槛。二维矢量数据的空间分析能提供各类要素信息提取和辅助决策。因此,空间分析在GIS基础平台研发中的重要性不言而喻。叠加分析和缓冲区分析是矢量数据的空间分析中最为重要的两种类型。也是本文的主要研究内容。 本文在分析当前GIS业界和学术界研发现状基础上,总结了矢量空间分析的基本功能特征,将叠加分析分解为点与线的关系、线与线的交点、面与面的叠加等基本问题并结合计算几何、空间数据索引等领域的最新研究成果,对平面中线段求交点的B0算法着重阐明了该算法的核心流程改进的关键是维护BO中的不变式,并对于求“点和线段的方向”函数给出了鲁棒实现,这些内容为后续研究奠定基础。 要素叠加分析是GIS矢量空间分析中最核心的计算之一。面面叠加,由于其在GIS的空间分析和查询中非常基础和关键,并且实现难度大,受到了较多的关注。基于Han算法,本文提出了改进算法Han-E并给出了面面叠加分析的实现。相比于Han算法,Han-E算法在不改变算法的时间复杂度的前提下,充分考虑了GIS数据集中会导致.Han算法失效的特殊情形并且提出了改进方法。Han-E算法可以在一次扫描过程中输出交、并、差、对称差、几何并的结果,并求得每个结果多边形的父多边形。对于多边形的洞,以较低的时间和空间复杂度求得其归属多边形。 基于经过裁剪的Han-E算法并结合空间数据索引实现了点面叠加分析和线面叠加分析。算法时间复杂度是点面为n log n(n为坐标点数),线面为(n+k)log n(n为点数,k为交点数)。而计算几何中的经典算法和可获得的开源软件中的算法的复杂度皆为0(n<2>)。 本文提出了基于改进的平面扫描算法的缓冲区分析方法,相对于传统的矢量算法,总体效率高,并且减少了需要处理的特殊情况。本文中给出的算法支持线的端点平头、圆头的缓冲边界。在不增加空间复杂度的前提下,本文中的算法相对于文献中给出的算法运行时间上能减少5﹪。 本文提出了一种基于空间数据索引和平面扫描算法的分条带叠加分析的方法,该方法可用来处理大数据量的叠加分析。实际测试表明该方法性能优于ArcGIS 9。 对于GIS需要支持的矢量空间分析算法(以ArcGIS为参考系统),本文系统地给出了实现方法并通过实际数据集验证了其正确性和效率。依据本文的算法,可以实现当前ArcGIS 9矢量空间分析的所有功能。而且,算法流程清晰、一致,可以有效减少未来代码维护的工作量。同时,算法的时间复杂度低,算法设计对于较大规模的数据量具有很好的扩展性。 本文的工作已经在VegaGIS中得到了应用。经过测试,运行稳定、高效,取得了良好的效果。
其他文献
随着信息和计算机技术的飞速发展,人脸表情识别技术越来越受到研究者的关注。人脸表情识别是指利用计算机分析特定人的脸部表情及变化,进而确定其内心情绪或思想活动,实现人机更
Job Shop 调度问题(简称JSP)是具有特殊工件特性和加工环境的最典型和最重要的调度问题,是许多实际生产调度问题的简化。JSP属于NP-Hard问题,它的搜索空间随着工件和机器的增加
ZigBee是一种短距离无线通信技术。ZigBee本身的技术特点就决定了ZigBee技术在家庭自动化、工业、医学、现代化农业等领域具有广阔的应用前景,它的目标定位于现存系统所不能满
软件重用是目前解决软件危机比较现实可行的方法之一。构件及构件库的开发是软件重用的前提,构件库能有效地对可重用构件进行管理,已成为当前基于构件的软件开发的核心。如何
在分布式处理环境中,作业分配和调度的一个主要目的是平衡各处理机间的负载,并以此提高并行处理的效率。静态作业分配是指在计算前就被指派给确定的计算机。这种分配方式虽然简
随着Internet的快速发展,WEB已经成为有史以来最大的信息库,并且其内容仍在以指数级增长,传统的依靠浏览器以及关键字检索查询的搜索引擎已经越来越难满足人们对互联网信息服务
网络和多媒体技术在教学中的广泛应用,使得基于网络的现代远程教育得到了充分的普及和发展。作为信息时代中一种新型教育模式,网络远程教育己经成为现代教育体系的一个重要组
广播与数据聚集在无线传感器网络中有着广泛的应用。广播是将信息从网络中的某个节点分发到网络中所有节点的过程,数据聚集是每个节点将采集的信息集中到网络中的某个中心节
在系统开发的周期中,会有很多本质上相互关联的模型产生。特别是在模型驱动开发被工业界所接受的今天,这种情况更为常见。比如在建模或者书写文档的时候,人们经常喜欢把各种模型
本文旨在介绍一种新的交互式的软件需求获取方法。 软件工程学的研究历史将近四十年,在软发开生命周期中,需求分析被公认为最关键的一步。所以,本文试图寻找一种有效的获取软