Journal of Geo-information Science >
A Quick Method for Query Spatial Relationships between Polygon Layers Based on Heterogeneous Multi-core Architecture
Received date: 2014-12-15
Revised date: 2015-01-19
Online published: 2015-05-10
The commonly used Plane Sweep algorithm in spatial relationship query is a serial algorithm. Some scholars had studied some parallel query algorithms that based on multi-core CPU. However, due to the limitations induced by the number of CPU's core and thread, when dealing with massive data query, these methods are incapable to meet the requirements for query efficiency. To solve this problem, this paper proposes a new parallel algorithm of spatial relationship query between polygon layers based on heterogeneous multi-core architecture. The algorithm used STR-tree index to filter the disjointed polygons first. After the filtration, we built a quadtree index to manage the line segments of the polygons, so that we could quickly get the line segment combination to prepare for computing the intersection situations. Then, the CPU+GPU architecture was adopted to parallel compute the line segments'intersection situation. In details, we firstly put each line segment combination into each thread of GPU to calculate the relevant intersection situation, and the intersection type was counted using CPU. Next, the topological relations between the polygon rings were judged according to the type of line segment intersection, thus the values of DE-9IM parameters between these polygons were calculated based on the topological relations, and accordingly, the spatial relationship between the polygons were determined. At last, the efficiency and accuracy of the algorithm was verified by an experiment. In the experiment, we gradually increased the polygon number of the source layer and the target layer. When both of the two layers had 50000 polygons, here took the Contains relation as an example, we found that the computation time of the parallel algorithm is 15.143s faster than ArcGIS, and the speedup ratio can reach up to 2. In general, the parallel algorithm has more obvious advantages in dealing with higher volumes of data.
YOU Zhijie, XIE Chuanjie, MA Yihang, LONG Zhou . A Quick Method for Query Spatial Relationships between Polygon Layers Based on Heterogeneous Multi-core Architecture[J]. Journal of Geo-information Science, 2015 , 17(5) : 547 -555 . DOI: 10.3724/SP.J.1047.2015.00547
[1] 王结臣,王豹,胡玮,等.并行空间分析算法研究进展及评 述[J].地理与地理信息科学,2011,27(6):1-5.
[2] 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.
[3] 张舒,褚艳利.GPU 高性能运算之CUDA[M].北京:中国 水利水电出版社,2009.
[4] Shamos M I, Hoey D. Geometric intersection problems
[C]. 17th Annual Symposium on Foundations of Computer Science, IEEE, 1976:208-215.
[5] Bentley J L, Ottmann T A. Algorithms for reporting and counting geometric intersection[J]. IEEE Transactions on Computers, 1979,100(9):643-647.
[6] 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 ofWorkshop on Algorithm Engineering, 1997.
[7] Chazelle B, Edelsbrunner H. An optimal algorithm for intersecting line segments in the plane[J]. JACM, 1992,39:1-54.
[8] Balaban I J. An optimal algorithm for finding segments intersections[C]. Proceedings of the eleventh annual symposium on Computational geometry, ACM, 1995:211-219.
[9] Andrews D S, Snoeyink J, Boritz J, et al. Further comparison of algorithms for geometric intersection problems[C]. 6th International Symposium on Spatial Data Handling, 1994.
[10] Aggarwal A, Chazelle B, Guibas L, et al. Parallel computational geometry[J]. Algorithmica, 1988,3(1-4):293-327.
[11] Atallah M J, Goodrich M T. Efficient plane sweeping in parallel[C]. Proceedings of the second annual symposium on Computational geometry, ACM, 1986:216-225.
[12] Goodrich M T, Ghouse M R, Bright J. Sweep methods for parallel computational geometry[J]. Algorithmica, 1996, 15(2):126-153.
[13] Herring J. OpenGIS implementation standard for geographic information-simple feature access-part 1: Common architecture[R]. Wayland: Open Geospatial Consortium Inc, 2011.
[14] Leutenegger S T, Lopez M A, Edgington J. STR: A simple and efficient algorithm for R-tree packing[C]. 13th International Conference on Data Engineering, IEEE, 1997: 497-506.
[15] 周伟明.多核计算与程序设计[M].武汉:华中科技大学出 版社,2009.
[16] Samet H, Webber R E. Storing a collection of polygons using quadtrees[J]. ACM Transactions on Graphics (TOG), 1985,4(3):182-222.
[17] Samet H, Webber R E. On encoding boundaries with quadtrees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984(3):365-369.
[18] Shneier M. Calculations of geometric properties using quadtrees[J]. Computer Graphics and Image Processing, 1981,16(3):296-302.
[19] Shewchuk J R. Adaptive precision floating-point arithmetic and fast robust geometric predicates[J]. Discrete & Computational Geometry, 1997,18(3):305-363.
[20] Brisebarre N, De Dinechin F, Jeannerod C P, et al. Handbook of floating-point arithmetic[M]. Boston: Birkhäuser Boston Publisher, 2010.
[21] 王舒鹏,方莉.混合积判断线段相交的方法分析[J].电脑 开发与应用,2006,19(10):34-35.
[22] Egenhofer M J, Herring J. Categorizing binary topological relations between regions, lines and points in geographic databases[R]. Orono: Department of Surveying Engineering, University of Maine, 1991.
[23] 虞强源,刘大有,谢琦.空间区域拓扑关系分析方法综述[J].软件学报,2003,14(4):777-782.
/
| 〈 |
|
〉 |