空间索引引导的点—弧拓扑关系构建方法研究

发布时间：2017-09-17 06:05

  本文关键词：空间索引引导的点—弧拓扑关系构建方法研究

  更多相关文章： 点-弧拓扑关系 空间索引 空间数据模型 PSO CPSO-TREE

【摘要】：空间实体间的拓扑关系是空间关系中最基本的关系,是空间推理、查询、分析的基础。当前的拓扑关系计算大多从空间实体的几何形态特性出发,从几何角度考虑拓扑关系的计算问题,并没有将拓扑关系的计算与地理学中的空间相似性和异质性联系在一起,使得GIS空间拓扑关系的计算方法存在一些可改进的方面。现阶段的GIS数据模型决定了当前的拓扑关系计算过程是一种“静态”模式,无法满足数据动态变化的需求,例如Geodatabase数据模型利用规则的形式按需构建拓扑关系,无法在数据更新时只计算变更数据。因此,本文在分析现有拓扑关系计算流程的基础上,针对拓扑关系构建需要满足数据动态更新的需求,提出空间索引引导的点-弧拓扑关系构建方法,改进现有的拓扑关系构建方法。空间索引引导的点-弧拓扑关系构建一方面从空间分布特性角度出发,提高了静态数据的拓扑关系构建效率,另一方面在数据更新时实现拓扑关系的动态更新。 本文的主要研究成果如下： (1)基于空间分布特性和粒子群优化的索引方法 空间索引的关键是空间划分。在划分的同时兼顾空间分布特性使之达到最优解是空间索引最理想的状态。粒子群优化算法(PSO)已经在聚类问题中的得到应用,本文利用其聚类特性,将PSO优化和空间分布特性结合起来,提出一种基于聚类的多路划分索引方式CPSO-TREE。该索引既权衡了数据量均衡、空间重叠度最小等几何参数,又考虑了数据的空间分布特性。 (2)空间索引引导的点-弧拓扑关系计算方法 从拓扑关系描述和拓扑关系计算两方面着手,研究现阶段拓扑关系的构建方法,分析现阶段拓扑关系构建的不足,将空间分布特性融入目前单纯考虑几何形态的拓扑关系计算方法。基于CPSO-TREE索引提出CPSO-TREE引导的点-弧拓扑关系计算方法,该方法使得静态数据拓扑构建高效,数据更新时只考虑变更数据,无需重新计算,实现拓扑关系按需更新。 (3)原型系统设计与实验 根据CPSO-TREE引导的点-弧拓扑关系计算方法,本文构建点-弧拓扑关系计算的原型系统,实验结果表明,本文算法计算结果正确,计算效率优于ArcGIS、 SuperMap和GEOS等现有国内外著名GIS软件。
【关键词】：点-弧拓扑关系 空间索引 空间数据模型 PSO CPSO-TREE
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：P208
【目录】：

• 资助项目4-5
• 摘要5-6
• Abstract6-12
• 第1章 绪论12-27
• 1.1 选题背景与研究意义12-14
• 1.1.1 选题背景12-13
• 1.1.2 研究意义13-14
• 1.2 拓扑关系计算的研究现状14-23
• 1.2.1 拓扑构建的研究现状14-22
• 1.2.2 存在问题分析22-23
• 1.3 研究目标与研究内容23-24
• 1.3.1 研究目标23
• 1.3.2 研究内容23-24
• 1.4 研究方法与技术路线24-26
• 1.4.1 研究方法24
• 1.4.2 技术路线24-26
• 1.5 论文结构26-27
• 第2章 基于空间分布特性和粒子群优化的索引方法27-44
• 2.1 空间索引对比研究27-33
• 2.1.1 结点分裂算法27-31
• 2.1.2 空间索引的范围查询31-33
• 2.2 基于空间聚类的多路划分索引算法33-43
• 2.2.1 Hilbert编码聚类34
• 2.2.2 粒子群优化算法(Particle Swarm Optimization,PSO)34-36
• 2.2.3 组合粒子群优化算法(Combinatorial Particle Swarm Optimization,CPSO)36-37
• 2.2.4 基于空间聚类的多路划分索引算法CPSO-TREE37-43
• 2.3 本章小结43-44
• 第3章 空间索引引导的点-弧拓扑关系计算方法44-53
• 3.1 基于CPSO-TREE的扫描线算法的数据结构44-46
• 3.1.1 拓扑关系索引数据结构45
• 3.1.2 扫描线状态的数据结构45-46
• 3.2 基于CPSO-TREE的扫描线算法原理46-49
• 3.2.1 空间索引初次过滤46-47
• 3.2.2 单调链二次过滤47-48
• 3.2.3 算法主体流程48-49
• 3.3 数据的插入和删除引起的拓扑关系变化49-51
• 3.3.1 数据插入49-50
• 3.3.2 数据删除50-51
• 3.4 算法总体流程51-52
• 3.5 本章小结52-53
• 第4章 点-弧拓扑关系构建实验53-68
• 4.1 实验技术路线53
• 4.2 结果正确性验证53-57
• 4.2.1 最小生成树实验53-55
• 4.2.2 最短路径实验验证55-57
• 4.3 算法效率验证57-67
• 4.3.1 实验介绍及实验数据57-58
• 4.3.2 CPSO-TREE效率验证58-61
• 4.3.3 基于CPSO-TREE的线段打断效率验证61-67
• 4.4 本章小结67-68
• 第5章 结论与展望68-70
• 5.1 研究结论68
• 5.2 主要创新点68-69
• 5.3 展望69-70
• 在校期间发表的学术论文和研究成果70-71
• 参考文献71-77
• 致谢77

【参考文献】

中国期刊全文数据库 前10条

1 廖楚江,杜清运;GIS空间关系描述模型研究综述[J];测绘科学;2004年04期

2 陈占龙;吴信才;吴亮;;基于单调链和STR树的简单要素模型多边形叠置分析算法[J];测绘学报;2010年01期

3 陈军,赵仁亮;GIS空间关系的基本问题与研究进展[J];测绘学报;1999年02期

4 ;IMPROVING 9-INTERSECTION MODEL BY REPLACING THE COMPLEMENT WITH VORONOI REGION[J];Geo-Spatial Information Science;2000年01期

5 陈军;GIS空间数据模型的基本问题和学术前沿[J];地理学报;1995年S1期

6 程昌秀,周成虎,陆锋;ArcInfo 8中面向对象空间数据模型的应用[J];地球信息科学;2002年01期

7 朱雅音,万丰,王化文;确定两个任意简单多边形空间关系的算法[J];计算机工程与应用;2003年01期

8 夏德麟，熊鑫;线段相交性问题求解的新算法与原理[J];计算机辅助设计与图形学学报;1996年02期

9 王文成,吴恩华;判断检测点是否在多边形或多面体内的新方法[J];软件学报;2000年12期

10 严霄凤;;在智慧城市建设中推广电子认证服务[J];软件;2012年03期

，

本文编号：867677