地图线要素自动综合并行计算方法研究 ——以等高线为例

论文摘要

地图综合作为地图数据生产、更新、地图特征信息提取和可视化表达的重要手段,一直以来都是地图学与地理信息科学领域具有挑战性的难点问题。随着GIS在各领域应用的不断深入,现有的GIS数据处理技术已不能满足数字空间信息时代与信息社会的需求,其中一个重要方面就是无法解决空间数据随比例尺变化而产生的信息量增减问题,而解决此问题的根本出路就在于实现地图综合的自动化。而随着各种网络技术的发展,对实时在线多尺度地理信息服务的要求不断提高,为了解决实时动态的海量地理数据的处理,地图综合的效率需要进一步提高,除了对地图综合算法进行改进这种方法外,并行计算技术的发展也为地图综合效率的提高提供了新方法。线要素综合作为地图综合领域中最重要的研究领域,经历了几十年的发展,依然是专家学者们研究的热点,这是由线状要素在地图要素的图形表达和GIS分析中的重要性而决定的。然而线要素有很多,它们有着不同的数据特点,它们的综合方法也不尽相同,因此对线要素综合并行计算的方法的研究必不可缺。本文在调研地图线要素自动综合研究以及并行计算在地图综合中应用研究的基础上,选择了地图线要素自动综合中常用的一些简化算法进行时间复杂度分析,探讨了现有数据分解方法在线要素综合并行计算中应用的适宜性,并提出了基于层次结构特征的线要素数据分解策略,然后在分析等高线综合方法及等高线数据特点的基础上提出了基于高程带的等高线数据分解方法,最后基于这种分解方法分别在OpenMP和MPI并行计算环境下利用上述常用算法进行等高线数据的并行处理实验,通过该实验验证了基于高程带的等高线数据分解方法的有效性,也验证了上述简化算法的时间复杂度分析结果的准确性,该实验中基于OpenMP的线简化并行算法的效率得到了提升,而基于MPI环境的线简化并行算法在效率上有些不同,对于时间复杂度为O(n)的线简化算法没有起到加速效果,对时间复杂度为O(n2)的线简化算法加速效果明显,这也说明了算法本身的效率与并行计算环境选择之间有密切联系,该研究为实现地图线要素自动综合的并行计算提供了依据。

论文目录

• 摘要
• Abstract
• 目录
• 图表目录
• 第1章 绪论
• 1.1 选题背景及研究意义
• 1.1.1 选题背景
• 1.1.2 研究意义
• 1.2 国内外研究现状
• 1.2.1 地图线要素自动综合研究现状
• 1.2.2 并行计算在地图综合中的应用现状
• 1.3 地图线要素自动综合并行计算研究存在问题及趋势
• 1.4 本文研究内容、技术路线及章节安排
• 1.4.1 研究内容
• 1.4.2 技术路线
• 1.4.3 章节安排
• 第2章 地图线要素自动综合理论基础
• 2.1 地图中的线要素
• 2.2 地图自动综合过程
• 2.2.1 传统手工地图综合过程
• 2.2.2 数字条件下地图自动综合过程
• 2.3 地图线要素自动综合算子及算法
• 2.3.1 线要素简化算子及算法
• 2.3.2 线要素选取算子及算法
• 2.4 线要素地图综合约束
• 2.4.1 地图综合约束的概念及来源
• 2.4.2 地图综合约束条件的分类
• 2.4.3 地图综合约束对地图综合的控制
• 2.5 小结
• 第3章 常用线要素简化算法时间复杂度分析
• 3.1 算法时间复杂度
• 3.1.1 算法的定义及特征
• 3.1.2 算法时间复杂度的定义及表示方法
• 3.1.3 时间复杂度分析的方法
• 3.2 线要素简化算法的时间复杂度分析
• 3.2.1 间隔取点法
• 3.2.2 垂距限差法
• 3.2.3 角度限差法
• 3.2.4 "圆"算法
• 3.2.5 Li-Openshaw算法
• 3.2.6 光栏法
• 3.2.7 Douglas-Peucker算法
• 3.2.8 Lang算法
• 3.2.9 渐进式化简算法
• 3.3 小结
• 第4章 地图线要素自动综合并行计算的数据分解方法
• 4.1 面向并行计算的空间数据分解方法
• 4.1.1 基于条带和矩形块的空间数据数据分解方法
• 4.1.2 基于Hilbert曲线的空间数据数据分解方法
• 4.2 基于层次结构的线要素数据分解策略
• 4.3 等高线地图自动综合基本理论
• 4.3.1 等高线地图综合相关知识
• 4.3.2 等高线自动综合的基本方法
• 4.4 面向等高线地图综合并行计算的数据分解方法
• 4.4.1 等高线综合并行计算对数据分解的要求
• 4.4.2 基于高程带的等高线数据分解方法
• 4.5 小结
• 第5章 地图线要素自动综合并行计算实验
• 5.1 并行计算介绍
• 5.1.1 并行计算概念、发展趋势及分类
• 5.1.2 并行计算编程环境
• 5.1.3 并行计算的性能度量
• 5.2 基于OpenMP的线简化算法的并行计算实验
• 5.2.1 实验环境及数据
• 5.2.2 实验平台
• 5.2.3 实验结果及分析
• 5.3 基于MPI的等高线简化算法的并行计算实验
• 5.3.1 实验环境及数据
• 5.3.2 实验平台
• 5.3.3 实验结果及分析
• 5.4 本章小结
• 第6章 结论与展望
• 6.1 结论
• 6.2 展望
• 参考文献
• 攻读硕士期间科研成果
• 致谢