论文摘要
空间数据的复杂性会导致空间数据处理的延迟,这对实时性要求比较高的应用问题如军事作战等问题产生了巨大的挑战。设计支持空间分析的并行算法是解决此类问题的有效方法,然而,目前国内外对并行空间分析的算法研究却很少。本文的工作主要包括以下几个方面:1、采用平面扫描树技术将平面扫描算法并行化。平面扫描树技术可应用于梯形分解,点定位等空间分析中,本文利用平面扫描树技术进行空间分析前先对一般的平面扫描树进行预处理,在树的各结点中增加一些指针和结构,使得点定位的时间复杂度从O(log2n)降低到O(logn)。2、采用分解归并技术将平面扫描算法并行化。空间拓扑分析是许多复杂空间分析算法的基础,本文利用分解归并的方法设计并实现了并行空间拓扑分析算法。3、许多空间分析算法都可归结为凸包问题的求解,本文改进并实现了求取平面散乱点集凸包的并行算法,和已有并行算法相比,该算法设计更加简单,计算量更小。4、本文的空间拓扑分析算法是以Realms为基础来设计和组织数据的,和基于欧氏空间的空间分析相比,基于Realms的空间分析能够使得空间分析局部化,这使得并行空间分析算法的实现更加简单。
论文目录
摘要ABSTRACT第一章 绪论1.1 GIS 和空间分析1.2 并行空间分析的必要性1.3 支持空间分析的并行算法1.4 本文结构1.5 本章小节第二章 并行计算概述2.1 并行计算简介2.2 集群系统概述2.3 并行算法概述2.3.1 并行编程模型2.3.2 并行算法2.3.3 并行程序设计2.4 MPI 简介2.5 本章小节第三章 并行平面扫描算法的设计与实现3.1 平面扫描算法概述3.2 平面扫描算法的并行化方法3.2.1 平面扫描树（Plane-Sweep Tree ）技术3.2.2 分解归并技术3.3 本章小节第四章 并行空间拓扑分析算法的设计与实现4.1 基于Realms 的空间对象的建模4.1.1 空间数据的建模过程4.1.2 Realms 的约束条件4.1.3 空间对象的构成4.1.4 区域类型空间对象的实现4.2 基于Realms 的平面扫描算法4.3 串行的空间拓扑分析算法4.3.1 静态事件点列表的构建4.3.2 扫描线状态的数据结构和更新4.3.3 串行空间拓扑分析算法的实现4.4 空间拓扑分析算法的并行化4.4.1 算法的主要步骤4.4.2 算法的实现4.4.3 算法分析4.5 本章小节第五章 求取平面点集凸包的并行算法及在空间分析中的应用5.1 凸包算法的概述5.1.1 现有求取凸包的串行算法5.1.2 改进的快速求取凸包的算法5.1.3 求取简单有序多边形凸包算法5.1.4 求取凸包的并行算法5.2 求取平面点集凸包串行算法5.2.1 基于12 个极值点的凸包求取算法5.2.2 格网技术的算法思想5.2.3 串行算法的步骤5.3 求取平面点集凸包并行算法5.3.1 算法思想5.3.2 基于MPI 的平面点集凸包的并行算法5.3.3 算法分析5.3.4 算法验证5.4 并行凸包算法在空间分析中的应用5.5 本章小节第六章 全文总结与展望6.1 全文总结6.2 改进和发展参考文献致谢在学期间的研究成果及发表的学术论文
相关论文文献
标签：并行空间分析论文; 平面扫描算法论文; 平面扫描树论文; 空间拓扑分析论文; 凸包论文;
