GIS典型几何计算算法的并行化及优化研究

空间数据规模的快速增长对传统矢量数据分析方法提出了更高的计算效率和处理规模要求。随着计算机硬件和软件技术的进步,并行计算为提高GIS中典型几何计算算法的计算效率、扩大问题处理规模提供了有效手段。本文在Visual Studio 2010中,使用标准C++编程语言,基于GDAL(Geospatial Data Abstraction Library)库实现空间数据的读写操作,针对线简化算法的并行化问题,在高性能计算环境下对并行任务调度策略、并行计算粒度、数据分解方法等多个核心内容开展研究。在完成相关串行算法的基础上,实现了该算法的并行化和优化设计,为相关的矢量数据空间分析方法的多核并行优化提供了思路和参考。     

网络环境下矢量数据高效并行可视化方法

针对网络环境下传统的矢量地图可视化模型中矢量数据可视化效率低,地图服务器集群并行处理能力弱的难题,提出一种基于矢量数据要素空间分布的矢量数据高效并行可视化方法。研究了矢量数据空间分布信息的采集、检索和分析原理,重点阐述了矢量数据实时可视化任务的分解与并行处理流程,最终实现了矢量数据的高效并行可视化,达到了充分利用地图服务器集群中并行计算资源的目的。仿真实验结果证明,矢量数据高效并行可视化方法可以提升网络地图服务集群的并行处理能力,满足大用户量并发访问的需求。     

几何部件缓冲区域合并的Buffer算法及其并行优化方法

摘 要：本文在介绍一种基于几何部件缓冲区域合并的矢量数据缓冲区生成算法的基础上,采用数据并行思想和MPI编程模型对缓冲区算法的并行化实现和优化方法开展研究。实验结果显示,与ArcGIS Buffer工具相比,（1）当缓冲区结果多边形不合并时,虽然串行缓冲区算法的时间开销较高,但可轻易通过并行方式实现加速。（2）当缓冲区结果合并时,本文算法要明显优于ArcGIS Buffer工具,并且经过优化的并行缓冲区算法表现出了更高的计算效率和更大规模的数据处理能力。因此,基于几何部件缓冲区域合并的Buffer算法具备一定的实用价值,本文提出的按结点数量的任务分解方法和进程间结果“树状”归并策略是对缓冲区算法进行并行优化的有效途径,对GIS中其他矢量分析算法的并行化及相关优化工作也具有一定的借鉴意义。     

云环境下海量矢量数据叠置分析方法研究

针对当前单机环境下海量矢量数据叠置分析效率低的问题,提出了云环境下海量矢量数据并行叠置分析方法;设计了海量矢量数据在云环境下的存储模型GeoWKT;基于该模型研究了云环境下海量矢量数据并行划分方法,有效避免了云环境下并行叠置计算中负载不均引起的计算效率低的问题,为数据密集与计算密集型并行叠置计算提供了新的尝试。实验结果表明,相较于传统的单机GIS软件,该方法在保证计算结果正确性的同时,显著提高了叠置分析的计算效率,证明了本文提出的基于云环境下海量矢量数据并行叠置分析方法的正确性和有效性。     

3维数字地球快速缓冲区分析算法

提出一种应用在3维数字地球中的通过图形处理器(GPU)快速实现矢量数据缓冲区分析的算法。使用一张4通道的纹理图作为容器将地理实体的矢量数据传入GPU,利用GPU的高效并行特性,将目标缓冲区纹理中的每个像素所对应的矢量坐标与原实体进行距离量算,在一次渲染中得到缓冲区纹理,最后提取出缓冲区纹理的边界。选择中国的流域和湖泊矢量数据,将本文算法与两种传统的CPU算法进行了缓冲区分析计算、测试和对比。结果显示,本文算法相对于传统矢量算法效率提高了9—16倍,相对于传统栅格算法效率提高11—20倍。实验证明,该算法计算简单,效果明显,特别是随着数据量增大,缓冲区计算速度显著优于传统算法,并能有效解决传统矢量法缓冲区分析中的数据自相交问题。     

基于OpenMP的矢量空间数据并行拓扑算法设计与实现

高性能并行GIS逐渐成为GIS发展的新方向。矢量数据的复杂性使得一些并行GIS算法难以实现,从而无法满足并行GIS的发展要求。文中针对GIS算法中的拓扑算法,借助OpenMP编程模型,通过消除并行拓扑处理过程中的数据依赖,在单机多核的环境下设计并实现了矢量空间数据并行拓扑算法。通过实验对比串行拓扑算法和并行拓扑算法的处理时间和结果,验证了并行拓扑算法的正确性,同时证明并行拓扑算法能够在一定程度上提升拓扑处理的效率。     

基于OpenMP的海量DEM快速并行裁切算法

为了提高海量DEM的裁切效率,且充分利用现有的多核CPU计算资源,提出一种基于OpenMP框架的快速并行裁切算法,并对其性能进行实例验证.通过对规则和不规则DEM数据用不规则矢量范围线裁切的任务进行分解,设计了相应的并行程序,将遍历点与矢量范围线的空间关系及DEM内插的过程进行并行化计算,缩短了计算时间.算法在实际生产...     

多边形拓扑关系构建的栅格算法

矢量数据拓扑关系的自动建立是GIS软件的核心模块之一，也是技术难点之一。简要分析传统算法的优缺点，在此基础上，借鉴基栅格的种子点填充算法和矢量数据求交的栅格探测法的思想，提出建立图幅多边形与弧段所属关系的栅格算法，给出算法的各主要步骤和实现方法。分析与试验表明，新算法在特殊情况处理、多边形内点自动建立、处理效率、简化编程等方面有一定优势。     

基于GIS的海洋划界技术方法研究

通过分析国内外基于矢量方式海洋划界技术实现原理和技术特点,认为传统划界技术存在着概念不严密、算法复杂、数据结构不统一及缺乏误差讨论等诸多问题,已无法满足当前高精度海洋划界技术要求。而地图代数理论和技术的发展,充分发挥矢量数据和栅格数据的优势,为高精度的海洋划界模型建立提供了新的解决思路。     

基于OpenMP的并行化水文分析算法研究与实现

水文模拟计算具有数据量较大、过程连续性较强的特点。随着数据采集技术的不断发展,大范围、高分辨率的地形数据使得传统串行算法难以满足性能要求,而并行化水文分析算法研究受到越来越多的关注。本文在对GIS空间分析算法并行化进行分析的基础上,对主要并行计算框架进行了对比,并选用OpenMP框架对水文分析若干过程进行了并行化算法的研究和实践。实验结果表明,基于OpenMP框架的并行化水文分析算法是在多核平台下进行性能优化的有效手段。     

线要素化简算法的时间复杂度分析

线状要素是地图中数量最大、要素类型最多样的要素,其化简在地图自动综合中占据了重要的地位.目前对线状要素化简算法的改进、化简质量、化简精度等方面的研究较多,对线状要素化简算法的效率研究较少.此处是在兼顾化简质量的前提下研究算法效率,通过分析化简算法约束参数的特征,将线状要素化简算法分为6类,选取其中的几个典型算法,分析了其时间复杂度,并按照线状要素化简算法的时间复杂度将其分为线性算法和非线性算法两类,初步探讨了适合这两类算法的并行计算方法.     

球面线要素的多分辨率实时简化方法

在分析球面3维数据可视化特点的基础上,提出了视点相关的球面矢量数据LOD简化方法,基本原理是：以视点为基础在屏幕空间获取投影误差,反投影到模型空间得到动态简化阈值,并结合Douglas—Peucker算法,对矢量数据进行多分辨率实时简化表达。最后,开发实验系统并对相关方法进行了验证。结果表明：在不影响球面图形可视化效果下,数据量减少了约4-5倍,有效地提高了图形渲染速度和效率。     

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。     

一种顾及空间关系约束的线化简算法

线要素化简在制图表达与综合领域一直是研究的热点和难点之一。然而,经典化简算法多针对单独线要素进行处理,缺乏对该线要素与周边线要素之间整体空间关系的考虑,并且,存在计算结果生硬(D-P算法)、局部极值点缺失,特别是在曲度较大之处出现相交异常(L-O算法)等问题。为此,本文提出一种顾及空间关系约束的线化简算法,建立线要素全局化简方法(LGSM)和矢量位移、面积位移等5类评价指标。采用等高线、河流和道路3类线要素实际数据进行了试验,充分检验了本文算法的优越性,其处理结果符合开方根模型规律,降低了曲线复杂度,在保证全局空间关系不变条件下,不仅更好地保持了曲线整体形状特征,而且光滑美观、精度高。     

图形、图像融合利用的集成学习智能化简方法及其在岛屿岸线化简中的应用

为充分利用已有化简成果及其蕴含的化简知识,本文集成几种机器学习算法提出图形、图像融合利用的智能化简方法,实现顶点取舍决策的学习和优化。首先,分别利用全连接神经网络和卷积神经网络设计、构建基于图形的顶点取舍模型和基于图像的顶点取舍模型,通过样本训练各模型拟合从图形特征到顶点取舍和从栅格图像到顶点取舍的映射;然后,基于线性加权、朴素贝叶斯、支持向量机、人工神经网络构建多种融合决策模型,实现基于图形和基于图像的顶点取舍的融合利用;最后,通过试验用例对所有模型进行测试。试验结果表明：基于图形和基于图像的顶点取舍模型在一定程度上学习、掌握了化简算子,融合利用后还能进一步提高化简准确性、实现优势互补。     

A Parallel Framework for Processing Massive Spatial Data with a Split–and–Merge Paradigm

Due to high data volume, massive spatial data requires considerable computing power for real‐time processing. Currently, high performance clusters are the only economically viable solution given the development of multicore technology and computer component cost reduction in recent years. Massive spatial data processing demands heavy I/O operations, however, and should be characterized as a data‐intensive application. Data‐intensive application parallelization strategies, such as decomposition, scheduling and load‐balance, are much different from that of traditional compute‐intensive applications. In this article we introduce a Split‐and‐Merge paradigm for spatial data processing and also propose a robust parallel framework in a cluster environment to support this paradigm. The Split‐and‐Merge paradigm efficiently exploits data parallelism for massive data processing. The proposed framework is based on the open‐source TORQUE project and hosted on a multicore‐enabled Linux cluster. A specific data‐aware scheduling algorithm was designed to exploit data sharing between tasks and decrease the data communication time. Two LiDAR point cloud algorithms, IDW interpolation and Delaunay triangulation, were implemented on the proposed framework to evaluate its efficiency and scalability. Experimental results demonstrate that the system provides efficient performance speedup.     

CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架

本文提出了面向CPU+GPU异构环境的数据密集型矢量多边形地理大数据并行计算框架(PFGAP)。PFGAP将数据密集型矢量多边形地理大数据的并行计算分解为算子、数据、粒度、并行环境及任务调度5个模块,分别设计相应的负载均衡并行计算策略;通过封装并行计算实现细节及数据密集型多边形算子的快速并行化。试验采用多边形三角剖分、栅格化及投影变换作为测试算例,采用土地利用数据作为测试数据,在不同类型的并行环境中计算并行效率。结果表明,PFGAP能很好地适用于不同类型的数据集、算子及并行计算环境。利用PFGAP实现的并行算法显著地降低了串行执行时间,取得了40.03的最优并行加速比。试验还分别测试了各个模块涉及的并行策略,结果表明取得的并行效率优于现有并行策略。     

基于点删除的TIN简化算法改进

摘要： 三角网格模型的简化在三维建模过程中占有很重要的地位。本文通过系统研究目前常用的三角网简化算法，归纳总结出了各主要算法的优缺点与适用范围。文中重点选择了一种适用性比较广的基于点删除的TIN简化算法，并将它应用于实际的三维地形模型简化当中，在实际工作中检验它的实用性。根据三维地形数据量大、精度要求具层次感的特点，对原算法做了一些修改，在保证简化模型细节损失在误差控制范围内的情况下，使得算法简化效率更高。