简单要素模型多边形拓扑检查并行算法

摘 要:

将并行计算应用到大数据量简单要素模型多边形拓扑检查中，设计实现了简单要素模型多边形拓扑检查并行算法。算法针对拓扑检查的计算特点，改进了主从式并行策略，在主进程中进一步划分线程以实现任务并行，从而隐藏拓扑错误提取和结果写入时间。采用MPI和PThread实现进程与线程的结合。利用苏南五市土地现状调查地类图斑数据对算法进行测试。经测试，该算法能够对大数据量简单要素模型多边形进行准确、快速的拓扑检查。算法提出的进程与线程结合的任务并行策略相对于传统主从式策略加速比提高约20%。

关键词:并行计算；简单要素模型；拓扑检查；消息传递接口；PThread

中图分类号: TP751

文献标志码:A

英文标题

Parallel algorithm of polygon topology validation for simple feature model

英文作者名

REN Yibin1,2, CHEN Zhenjie1,2*, LI Feixue1,2, ZHOU Chen1,2, YANG Yunli1,2

英文地址(

1.School of Geographic and Oceanographic Sciences, Nanjing University, Nanjing Jiangsu 210023,China;

2.Jiangsu Provincial Key Laboratory of Geographic Information Sciences and Technology (Nanjing University), Nanjing Jiangsu 210023,China

英文摘要)

Abstract:

Methods of parallel computation are used in validating topology of polygons stored in simple feature model. This paper designed and implemented a parallel algorithm of validating topology of polygons stored in simple feature model. The algorithm changed the masterslave strategy based on characteristics of topology validation and generated threads in master processor to implement task parallelism. Running time of computing and writing topology errors was hidden in this way. MPI and PThread were used to achieve the combination of processes and threads. The land use data of 5 cities in Jiangsu, China, was used to check the performance of this algorithm. After testing, this parallel algorithm is able to validate topology of massive polygons stored in simple feature model correctly and efficiently. Compared with masterslave strategy, the speedup of this algorithm increases by 20%.

英文关键词Key words:

parallel computation; simple feature model; topology validation; Message Passing Interface (MPI); PThread

0 引言

简单要素模型是一种常用的矢量数据存储形式，被广泛应用于商用、开源地理信息系统(Geographic Information System，GIS)软件中,但由于不含拓扑关系数据，在创建和编辑过程中易产生数据冗余和不一致性等拓扑错误［1-3］。因此，在此类数据使用过程中会频繁地进行拓扑检查［4］。目前，商业GIS软件对此类数据进行拓扑检查前，一般需要先将其导入空间数据库建立起全局拓扑关系［5］。对大数据量多边形数据，数据导入导出和全局拓扑关系建立比较耗时［6］，严重影响拓扑检查的效率。因此，如何直接对大数据量简单要素模型多边形进行准确、快速的拓扑检查，显得尤为重要。并行计算允许多个处理单元同时执行一个操作，从而起到加速处理的作用［7-8］。将并行计算引入地理学领域以解决大数据量地理数据的计算问题已成为发展趋势［9］。当前，地理计算方面的并行算法主要集中于栅格数据处理、空间分析、数据转换等方面［10-12］，

拓扑方面的并行算法研究较少。文献［13］从空间数据划分的角度，提出了一种实现拓扑关系高效并行计算的矢量数据划分方法，但没有针对拓扑检查提出完整的并行算法流程。针对上述问题，本文以实现对大数据量简单要素多边形的快速拓扑检查为目的，综合考虑数据划分、任务调度等方面，提出了适用于简单要素模型多边形拓扑检查的并行策略。以检查多边形要素类的“多边形之间不存在重叠”拓扑规则为例，实现了多核环境下的多边形拓扑检查并行算法。

1 简单要素模型拓扑检查方法

对简单要素模型拓扑检查的目标是判断所有要素之间的拓扑关系是否满足拓扑规则，并提取出不满足拓扑规则的拓扑错误区域。如：“多边形之间不存在重叠”规则要求同一多边形要素类中多边形之间不能存在重叠［14］，对此规则检查就是查找要素间重叠区域。本文采用基于点集理论维度扩展的9交模型(Dimensionally Extented NineIntersection Model，DE9IM)作为描述要素间拓扑关系的模型［13］。拓扑关系计算需先判断要素间是否相交，如果相交则在相交关系的基础上进行其他拓扑关系计算［13］。为了提高拓扑检查的效率，本文分三步进行拓扑检查：一维空间索引构建,相交关系判断,拓扑错误区域提取和写入。其中，第三步是在一维空间索引构建、相交关系判断的基础上，针对存在相交关系的多边形提取拓扑错误区域，并将这些错误区域写入结果文件。

1.1 一维空间索引构建

为提高相交关系判断效率，需要对所有多边形建立一维空间索引。基本思路为：根据多边形最小外包矩形(Minimum Bounding Rectangle，MBR)最小X坐标对多边形进行排序，形成按X值由小到大的多边形序列(图1)。建好索引后，每个多边形只需与排在其后面的多边形进行拓扑关系计算。

推荐访问:多边形 拓扑 并行 算法 要素