多边形间空间关系查询的异构多核架构并行算法

doi:10.11947/j.AGCS.2016.20140463

测绘学报 ›› 2016, Vol. 45 ›› Issue (1): 119-126.doi: 10.11947/j.AGCS.2016.20140463

• 地图学与地理信息 • 上一篇

多边形间空间关系查询的异构多核架构并行算法

谢传节¹, 龙舟^1,2, 马益杭^1,2, 由志杰^1,2

1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101;
2. 中国科学院大学, 北京 100049

收稿日期:2014-09-04 修回日期:2015-05-04 出版日期:2016-01-20 发布日期:2016-01-28
作者简介:谢传节(1971—),男,博士,副研究员,研究方向为并行地理计算。
基金资助:
国家863计划(2011AA120302;2011AA120306;2012AA12A401);海洋公益性项目(201105033-6)

Parallel Algorithm of Spatial Relationship Query between Polygons Based on Heterogeneous Multi-core Architecture

XIE Chuanjie¹, LONG Zhou^1,2, MA Yihang^1,2, YOU Zhijie^1,2

1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China

Received:2014-09-04 Revised:2015-05-04 Online:2016-01-20 Published:2016-01-28
Supported by:
The National High-tech Research and Development Program of China (863 Program) (Nos.2011AA120302;2011AA120306;2012AA12A401);The Marine Public Welfare Project (No.201105033-6)

摘要/Abstract

摘要： 目前在空间关系查询中常用的Plane Sweep算法是一种串行算法,在处理海量空间数据时效率较低,而已有的并行计算方法对于普通的计算机并不适用。本文针对这个问题,提出了一种多边形间空间关系查询的异构多核架构并行算法,该算法先利用STR树索引过滤掉不相交的多边形,然后将过滤后的多边形数据集合分解为点集合和边集合,并对其构建四叉树索引;在保证数据浮点运算精度符合要求的情况下,利用GPU强大的批量运算能力快速处理边与边的相交情况并据此逐步计算得到环间的拓扑关系,再根据环间拓扑关系计算得到多边形间的维度扩展九交模型(DE-9IM)参数值;根据DE-9IM参数值与空间关系查询条件相比对,输出查询结果。最后通过试验验证了算法的准确性与高效性。

关键词: 异构多核, 并行计算, 拓扑关系, 空间关系查询

Abstract: The commonly used Plane Sweep algorithm in the spatial relationship query is a serial algorithm, when dealing with huge amounts of spatial data, the efficiency is very low,and the existing parallel computing method is not applicable to normal computer. Aiming at this problem, this paper proposes a parallel algorithm of spatial relationship query between polygons based on heterogeneous multi-core architecture. The algorithm uses STR-tree index to filter out non-intersection polygons first, then decomposes the filtered polygons data into points set and edges set, and constructs a quadtree index for them; under the premise of data accuracy meets the requirement of floating point calculation, uses GPU's powerful batch computing power quickly processing the intersection between edges and calculates the topology relationship between rings, then uses the topology relationship between rings to calculate the DE-9IM model between polygons; compares the DE-9IM model with spatial relationship query condition and outputs the query results. At last, the efficiency and accuracy of the algorithm is verified by experiment.

Key words: heterogeneous multi-core, parallel computing, topological relations, querying spatial relationship

中图分类号:

P208

谢传节, 龙舟, 马益杭, 由志杰. 多边形间空间关系查询的异构多核架构并行算法[J]. 测绘学报, 2016, 45(1): 119-126.

XIE Chuanjie, LONG Zhou, MA Yihang, YOU Zhijie. Parallel Algorithm of Spatial Relationship Query between Polygons Based on Heterogeneous Multi-core Architecture[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(1): 119-126.

参考文献

[1] 王结臣, 王豹, 胡玮, 等. 并行空间分析算法研究进展及评述[J]. 地理与地理信息科学, 2011, 27(6): 1-5. WANG Jiechen, WANG Bao, HU wei, et al. Review on Parallel Spatial Analysis Algorithms[J]. Geography and Geo-Information Science, 2011, 27(6): 1-5.
[2] 陈军, 赵仁亮. GIS空间关系的基本问题与研究进展[J]. 测绘学报, 1999, 28(2): 95-102. CHEN Jun, ZHAO Renliang. Spatial Relations in GIS: A Survey on Its Key Issues and Research Progress[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(2): 95-102.
[3] SHAMOS M I, HOEY D. Geometric Intersection Problems[C]//17th Annual Symposium on Foundations of Computer Science, 1976. Houston, TX: IEEE, 1976: 208-215.
[4] BENTLEY J L, OTTMANN T A. Algorithms for Reporting and Counting Geometric Intersections[J]. IEEE Transactions on Computers, 1979, C-28(9): 643-647.
[5] BARTUSCHKA U, MEHLHORN K, NÄHER S. A Robust and Efficient Implementation of a Sweep Line Algorithm for the Straight Line Segment Intersection Problem[C]//Proceedings of Workshop on Algorithm Engineering. 1997.
[6] CHAZELLE B, EDELSBRUNNER H. An Optimal Algorithm for Intersecting Line Segments in the Plane[J]. Journal of the ACM, 1992, 39(1): 1-54.
[7] BALABAN I J. An Optimal Algorithm for Finding Segments Intersections[C]//Proceedings of the 11th Symposium on Computational Geometry. New York: ACM, 1995: 211-219.
[8] 陈军, 刘万增, 李志林, 等. 线目标间拓扑关系的细化计算方法[J]. 测绘学报, 2006, 35(3): 255-260. CHEN Jun, LIU Wanzeng, LI Zhilin, et al. The Refined Calculation Method of Topological Relationships between Line Objects[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(3): 255-260.
[9] 陈斐, 周晓光. 基于平面分割的线/线相接、交叉类型判断[J]. 测绘学报, 2014, 43(2): 186-192. CHEN Fei, ZHOU Xiaoguang. An Algorithm for Determining the Touching and Crossing Relations between a Pair of Lines Based on One Line Splitting Plane to Two Parts[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(2): 186-192.
[10] GOODRICH M T, GHOUSE M R, BRIGHT J. Sweep Methods for Parallel Computational Geometry[J]. Algorithmica, 1996, 15(2): 126-153.
[11] ATALLAH M J, GOODRICH M T. Efficient Plane Sweeping in Parallel[C]//Proceedings of the Second Annual Symposium on Computational Geometry. New York: ACM, 1986: 216-225.
[12] AGGARWAL A, CHAZELLE B, GUIBAS L, et al. Parallel Computational Geometry[J]. Algorithmica, 1988, 3(1-4): 293-327.
[13] OWENS J D, LUEBKE D, GOVINDARAJU N, et al. A Survey of General-Purpose Computation on Graphics Hardware[J]. Computer Graphics Forum, 2007, 26(1): 80-113.
[14] 张舒, 褚艳利. GPU高性能运算之CUDA[M]. 北京: 中国水利水电出版社, 2009. ZHANG Shu, CHU Yanli. CUDA GPU High-performance Computing[M]. Beijing: China Water Power Press, 2009.
[15] LEUTENEGGER S T, LOPEZ M A, EDGINGTON J. STR: A Simple and Efficient Algorithm for R-Tree Packing[C]//Proceedings of the 13th International Conference on Data Engineering. Birmingham: IEEE, 1997: 497-506.
[16] 周伟明. 多核计算与程序设计[M]. 武汉: 华中科技大学出版社, 2009. ZHOU Weiming. Multi-core Computing and Programming[M]. Wuhan: Huazhong University of Science and Technology Press, 2009.
[17] SAMET H, WEBBER R E. Storing a Collection of Polygons Using Quadtrees[J]. ACM Transactions on Graphics (TOG), 1985, 4(3): 182-222.
[18] SAMET H, WEBBER R E. On Encoding Boundaries with Quadtrees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(3): 365-369.
[19] SHEWCHUK J R. Adaptive Precision Floating-point Arithmetic and Fast Robust Geometric Predicates[J]. Discrete & Computational Geometry, 1997, 18(3): 305-363.
[20] MULLER J M, BRISEBARRE N, DE Dinechin F, et al. Handbook of Floating-point Arithmetic[M]. Boston: Birkhäuser, 2009.
[21] 王舒鹏, 方莉. 混合积判断线段相交的方法分析[J]. 电脑开发与应用, 2006, 19(10): 34-35. WANG Shupeng,FANG Li.An Analysis of Two Segments Intersection Judgment with Mixed Product[J]. Computer Development & Applications, 2006, 19(10): 34-35.
[22] EGENHOFER M J, HERRING J R. Categorizing Binary Topological Relations Between Regions, Lines and Points in Geographic Databases[R]. Orono: University of Maine 1991.
[23] 虞强源, 刘大有, 谢琦. 空间区域拓扑关系分析方法综述[J]. 软件学报, 2003, 14(4): 777-782. YU Qiangyuan, LIU Dayou, XIE Qi. A Survey of Analysis Methods of Topological Relations between Spatial Regions [J]. Journal of Software, 2003, 14(4): 777-782.
[24] HERRING J R. OpenGIS^® Implementation Standard for Geographic Information——Simple Feature Access-Part 1: Common architecture[S]. [S.l.]: OGC Document, 2011.
[25] MCKENNEY M, PAULY A, PRAING R, et al. Local Topological Relationships for Complex Regions[M]//Advances in Spatial and Temporal Databases. Heidelberg: Springer, 2007: 203-220.

多边形间空间关系查询的异构多核架构并行算法

Parallel Algorithm of Spatial Relationship Query between Polygons Based on Heterogeneous Multi-core Architecture

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王勇, 罗安, 王慧慧, 曹元晖, 刘纪平. 复杂建筑物最短邻近线多边形聚合法[J]. 测绘学报, 2021, 50(12): 1671-1682.
[2]	邓非, 颜青松, 肖腾. 多视密集匹配并行传播GPU-PatchMatch算法[J]. 测绘学报, 2020, 49(2): 181-190.
[3]	康顺, 陈军, 彭舒. 顾及栅格空间拓扑关系的地表覆盖时空目标不一致性探测方法[J]. 测绘学报, 2019, 48(6): 767-779.
[4]	陈占龙, 叶文. 复杂面实体拓扑关系的精细化模型[J]. 测绘学报, 2019, 48(5): 630-642.
[5]	王占刚, 屈红刚, 王想红. 基于25交模型实现带洞面域拓扑关系描述模型间的转换[J]. 测绘学报, 2018, 47(9): 1270-1279.
[6]	郑顺义, 何源, 徐刚, 王辰, 朱锋博. 三维点云数据实时管理的Hash map方法[J]. 测绘学报, 2018, 47(6): 825-832.
[7]	梁伟, 徐新禹, 李建成, 朱广彬. 联合EGM2008模型重力异常和GOCE观测数据构建超高阶地球重力场模型SGG-UGM-1[J]. 测绘学报, 2018, 47(4): 425-434.
[8]	郑茂腾, 周顺平, 熊小东, 朱俊峰. GPU并行区域网平差[J]. 测绘学报, 2017, 46(9): 1193-1201.
[9]	王占刚, 杜群乐, 王想红. 复杂区域对象拓扑关系分解与计算[J]. 测绘学报, 2017, 46(8): 1047-1057.
[10]	崔阳, 吕志平, 李林阳, 陈正生, 孙大双, 邝英才. GNSS大网双差模型并行快速解算方法[J]. 测绘学报, 2017, 46(7): 848-856.
[11]	王竞雪, 朱庆, 王伟玺. 顾及拓扑关系的立体影像直线特征可靠匹配算法[J]. 测绘学报, 2017, 46(11): 1850-1858.
[12]	周晓光, 汪红松, 吴志强. 引入二维交细分类型的地表覆盖矢量数据增量更新[J]. 测绘学报, 2017, 46(1): 114-122.
[13]	沈敬伟, 周廷刚, 朱晓波. 面向带洞面状对象间的拓扑关系描述模型[J]. 测绘学报, 2016, 45(6): 722-730.
[14]	刘民士, 龙毅, 费立凡. 顾及拓扑一致性的水系三维曲线化简[J]. 测绘学报, 2016, 45(4): 494-501.
[15]	刘闯, 钱海忠, 王骁, 何海威, 谢丽敏, 王成舜. 利用城市骨架线网的道路和居民地联动匹配方法[J]. 测绘学报, 2016, 45(12): 1485-1494.