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

doi:10.11772/j.issn.1001-9081.2014.07.1852

计算机应用 ›› 2014, Vol. 34 ›› Issue (7): 1852-1856.DOI: 10.11772/j.issn.1001-9081.2014.07.1852

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

任沂斌¹,²,陈振杰¹,²,李飞雪¹,²,周琛¹,²,杨云丽¹,²

1. 江苏省地理信息技术重点实验室(南京大学)，南京 210023
2. 南京大学地理与海洋科学学院, 南京 210023;

收稿日期:2013-12-26 修回日期:2014-02-18 出版日期:2014-07-01 发布日期:2014-08-01
通讯作者: 陈振杰
作者简介:任沂斌(1990-)，男，山东青岛人，硕士研究生，主要研究方向：地理信息系统、高性能地理计算;陈振杰(1974-)，男，陕西宝鸡人，副教授，博士，主要研究方向：GIS算法、高性能地理计算;李飞雪(1983-)，女，黑龙江齐齐哈尔人，副教授，博士，主要研究方向：城市增长建模;周琛(1990-)，男，江苏宿迁人，硕士研究生，主要研究方向：高性能地理计算;杨云丽(1989-)，女，江苏淮安人，硕士研究生，主要研究方向：高性能地理计算。
基金资助:
国家863计划项目

Parallel algorithm of polygon topology validation for simple feature model

REN Yibin¹,²,CHEN Zhenjie¹,²,LI Feixue¹,²,ZHOU Chen¹,²,YANG Liyun¹,²

1. Jiangsu Provincial Key Laboratory of Geographic Information Sciences and Technology (Nanjing University), Nanjing Jiangsu 210023,China
2. School of Geographic and Oceanographic Sciences, Nanjing University, Nanjing Jiangsu 210023,China;

Received:2013-12-26 Revised:2014-02-18 Online:2014-07-01 Published:2014-08-01
Contact: CHEN Zhenjie

摘要/Abstract

摘要：

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

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%.

中图分类号:

TP751

任沂斌陈振杰李飞雪周琛杨云丽. 简单要素模型多边形拓扑检查并行算法[J]. 计算机应用, 2014, 34(7): 1852-1856.

REN Yibin CHEN Zhenjie LI Feixue ZHOU Chen YANG Liyun. Parallel algorithm of polygon topology validation for simple feature model[J]. Journal of Computer Applications, 2014, 34(7): 1852-1856.

参考文献

［1］CHEN Z, WU X, WU L. Polygon overlay analysis algorithm based on monotone chain and STR tree in the simple feature mode［J］. Acta Geodaetica et Cartographica Sinica, 2010, 39(1): 102-107. (陈占龙, 吴信才, 吴亮. 基于单调链和 STR 树的简单要素模型多边形叠置分析算法［J］. 测绘学报, 2010, 39(1): 102-107.)
［2］WANG X. Research on optimisation application of data structure processing of geographic information［D］. Zhengzhou: Information Engineering University, 2010. (王晓理. 地理信息数据结构处理优化应用研究［D］. 郑州: 信息工程大学, 2010.)
［3］HUANG X, MA J. Geographical information system［M］. Beijing: Higher Education Press, 2008. (黄杏元, 马劲松. 地理信息系统概论［M］. 北京:高等教育出版社, 2008.)
［4］PAN C, ZHOU S, YANG L, et al. The research of spatial topology rules managing mechanism based on MapGIS7.0［J］. Science of Surveying and Mapping, 2009,34(1): 222-224. (潘婵玲, 周顺平, 杨林, 等. 基于MapGIS7.0的空间拓扑规则管理机制研究［J］. 测绘科学, 2009,34(1): 222-224.)
［5］FENG H, MA T, LIU W, et al. Topology relationship analysis of cadastral spatial database and validity method based on rule［J］. Journal of Computer Applications, 2006, 26(17): 2522-2524. (冯杭建, 麻土华, 刘伟宏, 等. 地籍空间数据库拓扑关系分析及基于规则的验证方法［J］. 计算机应用, 2006, 26(17): 2522-2524.)
［6］XIE Z, YE Z, WU L. Polygon overlay analysis algorithm using the simple data model［J］. Geography and Geo-Information Science, 2007, 23(3): 19-23. (谢忠, 叶梓, 吴亮. 简单要素模型下多边形叠置分析算法［J］. 地理与地理信息科学, 2007,23(3): 19-23.)
［7］MINETER M J. A software framework to create vector-topology in parallel GIS operations［J］. International Journal of Geographical Information Science, 2003, 17(3): 203-222.
［8］SUI J, LIU H, WANG J, et al. Overview of multicore multithread technologies［J］. Journal of Computer Applications, 2013,33(S1): 239-242. (眭俊华, 刘慧娜, 王建鑫, 等. 多核多线程技术综述［J］. 计算机应用, 2013,33(S1): 239-242.)
［9］ZHANG S. Study on execution time prediction for parallel geocomputation in multi-core cluster environment［D］. Changsha: National University of Defense Technology, 2011. (张思乾. 多核集群环境下并行地理计算执行时间预测技术研究［D］. 长沙：国防科学技术大学, 2011.)
［10］GUAN Q, CLARKE K C. A general-purpose parallel raster processing programming library test application using a geographic cellular automata model［J］. International Journal of Geographical Information Science, 2010, 24(5): 695-722.
［11］PURI S, AGARWAL D, HE X, et al. MapReduce algorithms for GIS polygonal overlay processing［C］// Proceedings of the 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum. Piscataway: IEEE, 2013: 1009-1016.
［12］WANG Y, CHEN Z, CHENG L, et al. Parallel scanline algorithm for rapid rasterization of vector geographic data［J］. Computers and Geosciences, 2013, 59: 31-40.
［13］YANG Y, WU L, GUO J, et al. A method of spatial data partition for efficient parallel computing of topological relations［J］. Geography and Geo-Information Science, 2013,29(4): 25-29. (杨宜舟, 吴立新, 郭甲腾, 等. 一种实现拓扑关系高效并行计算的矢量数据划分方法［J］. 地理与地理信息科学,2013,29(4): 25-29.)
［14］WANG B. Rules-based topological relationships in Geodatabase［J］. Geomatics and Spatial Information Technology, 2004(3): 17-19. (王宝利. Geodatabase中基于规则的拓扑关系［J］. 测绘与空间地理信息, 2004(3): 17-19.)
［15］RABENSEIFNER R, HAGER G, JOST G. Hybrid MPI/OpenMP parallel programming on clusters of multi-core SMP nodes［C］// Proceedings of the 17th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Piscataway: IEEE, 2009: 427-436.
［16］SACHDEV G S, SUDAN K, HALL M W, et al. Understanding the behavior of PThread applications on non-uniform cache architectures［C］// Proceedings of the 2011 International Conference on Parallel Architectures and Compilation Techniques. Piscataway: IEEE, 2011: 175-176.

[1]	赖星锦郑致远杜晓颜徐莎杨晓君. 基于超像素锚图二重降维的高光谱聚类算法[J]. 计算机应用, 0, (): 0-0.
[2]	宋中山, 梁家锐, 郑禄, 刘振宇, 帖军. 基于双向门控尺度特征融合的遥感场景分类[J]. 计算机应用, 2021, 41(9): 2726-2735.
[3]	任秋如, 杨文忠, 汪传建, 魏文钰, 钱芸芸. 遥感影像变化检测综述[J]. 计算机应用, 2021, 41(8): 2294-2305.
[4]	孙潇, 徐金东. 基于级联生成对抗网络的遥感图像去雾方法[J]. 计算机应用, 2021, 41(8): 2440-2444.
[5]	李学明吴国豪周尚波林晓然. 基于分数阶网络和强化学习的图像实例分割模型[J]. 计算机应用, 0, (): 0-0.
[6]	侯笑晗, 金国栋, 谭力宁, 薛远亮. 基于自适应和最优特征的合成孔径雷达舰船检测方法[J]. 计算机应用, 2021, 41(7): 2150-2155.
[7]	陶冶许文海徐鲁强郭富城蒲海波陈广同. 基于人工欠曝光融合和白平衡技术的水下图像增强[J]. 计算机应用, 0, (): 0-0.
[8]	邓爽何小海卿粼波陈洪刚滕奇志. 基于改进VGG的弱监督细粒度阿尔兹海默症分类方法[J]. 计算机应用, 0, (): 0-0.
[9]	吴蕾, 杨晓敏. 改进的基于通道注意力反馈网络的遥感图像融合算法[J]. 计算机应用, 2021, 41(4): 1172-1178.
[10]	贺杰安, 吴晓红, 何小海, 胡建蓉, 卿粼波. 结合图像增强和卷积神经网络的小麦不完善粒识别[J]. 计算机应用, 2021, 41(3): 911-916.
[11]	王新生孙润德姚统. 基于相位一致性的遥感图像匹配方法[J]. 计算机应用, 0, (): 0-0.
[12]	成亚玲, 柏智, 谭爱平. 基于引导滤波和差分图像的多聚焦图像融合方法[J]. 计算机应用, 2021, 41(1): 220-224.
[13]	史文旭, 鲍佳慧, 姚宇. 基于深度学习的遥感图像目标检测与识别[J]. 计算机应用, 2020, 40(12): 3558-3562.
[14]	张永宏, 刘昊, 田伟, 王剑庚. 基于DeepLab v3的西藏地区降雨云团分割方法[J]. 计算机应用, 2020, 40(9): 2781-2788.
[15]	王睿, 黄微, 胡南强. 基于全变分模型的多时相遥感影像厚云去除算法[J]. 计算机应用, 2020, 40(7): 2126-2130.

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

Parallel algorithm of polygon topology validation for simple feature model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics