并行化矢量多边形叠加算法研究
2016-03-27范俊甫
并行化矢量多边形叠加算法研究
范俊甫1,2
1. 山东理工大学建筑工程学院，山东 淄博 255049； 2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室，北京 100101
Parallel Algorithms for Polygon Overlapping
FAN Junfu1, 2
1. School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255049, China; 2. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences, Beijing 100101, China
空间数据规模的快速增长对传统地学分析方法提出了更高的计算效率和处理规模要求。作为核心的空间分析算法之一，矢量多边形叠加分析具有典型的高算法复杂性和计算密集性特征。随着计算机硬件和软件技术的进步，并行计算为提高多边形叠加分析的计算效率，扩大问题处理规模提供了有效手段。研究面向新型计算架构的多边形并行叠加分析算法对完善高性能GIS理论研究和实现方法，提升传统地学分析算法的计算效率具有重要的理论价值和实践意义。本论文针对多边形非拓扑叠加算法的并行化问题，在多种高性能计算环境下解决了数据分解方法、并行任务映射方法、高效的多边形裁剪算法等多个关键问题，主要研究内容包括以下几点：
(1) 矢量多边形叠加及其并行化的关键问题理论总结。在对矢量多边形拓扑叠加与非拓扑叠加所需处理的关键问题、算法流程进行系统总结的基础上，明确了研究开展的前提，确定了数据分解算法、任务映射方法、多边形裁剪算法等多个研究重点。
(2) 多边形“多对多”映射条件下的数据分解方法研究。对多边形叠加过程中的“多对多”映射条件下的多边形相交蔓延性问题进行了研究，分析了不同的多边形叠加分析算法所适用的数据分解方法及之间的差异，提出了一种双向种子索引数据划分方法——DWSI算法；采用标记分割要素和设置期望分组大小的方法对DWSI算法进行了有效改进，解决了空间分布不均匀的要素叠加时易产生的并行失效问题；在多核并行环境下基于DWSI算法实现了多边形并行叠加联合算法，并实现了多种有效优化方法。
(3) 多边形叠加分析中的并行任务映射和算法应用研究。基于Vatti算法的多边形合并过程中的顶点累积效应是造成“滚雪球”合并模式效率低下的主要原因；采用分治法设计了多边形集合合并的“树状”合并方法，规避了顶点累积效应，有效地提高了多边形合并的计算效率；针对“多对多”映射下的集群并行任务映射问题，设计并实现了6种并行任务映射方法，其中采用R树预筛选的直接合并方法是在集群环境下实现并行多边形合并的有效方法；应用多边形合并算法提出并实现了一种高效的并行缓冲区生成算法。
(4) 基于栅格化思想的任意多边形裁剪算法的设计实现和并行应用研究。提出并实现了一种基于栅格化思想的任意多边形裁剪算法——RaPC算法；分析了RaPC算法计算结果的面积误差、形状误差和拓扑误差的影响因素和变化规律；通过实验比较了RaPC算法与Vatti算法的串行、并行计算效率差异，Vatti算法适用于小数据量叠加分析，RaPC算法在处理大数据量叠加时更有优势；RaPC算法的矩阵式处理模式比Vatti算法更适用于GPU并行计算，GPU加速的多边形叠加求交算法验证了RaPC算法对GPU并行的适用性和高效率。
(5) 开发实现了面向多种并行计算环境的、功能完备的开放式多边形叠加分析工具集，并完成了在多平台并行计算环境下的部署。
Author： FAN Junfu(1985—),male, received his doctoral degree from Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences on July 2014, majors in parallel spatial analysis algorithms.
E-mail： fanjf@lreis.ac.cn
作者简介：范俊甫(1985—)，男，讲师，2014年7月毕业于中国科学院地理科学与资源研究所，获理学博士学位(指导教师：周成虎院士、马廷副研究员)，研究方向为并行空间分析算法。
收稿日期：2015-09-24
基金项目：国家自然科学基金(41501425)；山东理工大学博士科研基金(4041-414039)；资源与环境信息系统国家重点实验室开放基金。
文章编号：1001-1595(2016)04-0502-01
中图分类号：P208
文献标识码：D
引文格式：范俊甫. 并行化矢量多边形叠加算法研究[J].测绘学报，2016,45(4)：502. DOI:10.11947/j.AGCS.2016.20150495.
FAN Junfu.Parallel Algorithms for Polygon Overlapping[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):502. DOI:10.11947/j.AGCS.2016.20150495.
