Abstract
Polygon intersection is important for data processing in geographic information systems. For large datasets, spatial indexing methods such as R-tree allow the identification of polygon intersections, but often retrieve inaccurate results. An improved boundary algebra filling (iBAF) method was preliminarily proposed as an alternative to R-tree. However, its applicability, performance, and accuracy require optimization, and its application conditions remain to be unveiled. This study develops version iBAF 2.0 for a more efficient identification and evaluates performance for different computational intensities and applications. Both intersecting polygons and raster zones within intersections can be rapidly grouped in the rasterized cells of input polygons. The resulting polygons can then be generated by configuring the polygon groups or converting the zones into vectors. We use complexity ratio CR, which is defined as the sum of the number of polygons in each actually intersecting group divided by the total number of polygons, to represent the computational intensity. Two land-use datasets containing 4295 and 741,562 polygons are considered, and we establish test cases containing the same polygons with varying CR. Experimental results show that iBAF 2.0 outperforms R-tree when applied to topology verification; however, its performance is conditional for polygon overlay and area calculation between two layers. Specifically, iBAF 2.0 exhibits higher-efficiency grouping of polygons and raster zones when CR exceeds specific thresholds. In addition, better scalability is achieved compared to R-tree when polygons with complex shapes and additional layers are considered.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beckmann N, Kriegel HP, Schneider R, Seeger B (1990) The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, pp 322–331. https://doi.org/10.1145/93597.98741
Belciu AV, Olaru S (2010) Optimizing Spatial Databases. Inform Econ J 14(2):61–71
Chang KT (2008) Introduction to geographic information systems. McGraw-Hill, New York
De Berg M, Van Kreveld M, Overmars M, Schwarzkopf OC (2000) Computational geometry. Springer, Berlin
Dong H, Cheng ZL, Fang JY (2009) One rasterization approach algorithm for high performance map overlay. In: proceedings of 17th international conference on Geoinformatics. https://doi.org/10.1109/GEOINFORMATICS.2009.5293561
Fan JF, Kong WH, Ma T, Zhou CH, Ji M, Zhou YK (2015) RaPC: a rasterization-based polygon clipping algorithm and its error analysis. Acta Geod Carto Sinica 44(3):338–345. https://doi.org/10.11947/j.AGCS.2015.20140017
Fan JF, He HX, Hu TY, Li GH, Liu Q, Zhou YK (2018) Rasterization computing-based parallel vector polygon overlay analysis algorithms using OpenMP and MPI. IEEE Access 6(99):21427–21441. https://doi.org/10.1109/ACCESS.2018.2825452
Finkel RA, Bentley JL (1974) Quad trees a data structure for retrieval on composite keys. Acta Informatica 4(1):1–9. https://doi.org/10.1007/bf00288933
Gao Y, Wu B, Luo JX, Qiu HP (2017) GPU-based arbitrary polygon intersection area algorithm. In: Proceedings of 3rd international symposium on mechatronics and industrial informatics (ISMII 2017), pp 99–105. https://doi.org/10.12783/dtetr/ismii2017/16652
Gomboš IM, Žalik B (2006) Point-in-polygon tests for geometric buffers. Comput Geosci 31(10):1201–1212. https://doi.org/10.1016/j.cageo.2005.03.009
Greiner G, Hormann K (1998) Efficient clipping of arbitrary polygons. ACM T Graphic 17(2):71–83. https://doi.org/10.1145/274363.274364
Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data
Hormann K, Agathos A (2001) The point in polygon problem for arbitrary polygons. Comput Geom 20:131–144. https://doi.org/10.1016/S0925-7721(01)00012-8
Kim DH, Kim MJ (2006) An extension of polygon clipping to resolve degenerate cases. Comput Aided Design Appl 3(1–4):447–456. https://doi.org/10.1080/16864360.2006.10738483
Liu YK, Wang XQ, Bao SZ, Gomboši M, Žalik B (2007) An algorithm for polygon clipping, and for determining polygon intersections and unions. Comput Geosci 33(5):589–598. https://doi.org/10.1016/j.cageo.2006.08.008
Longley PA, Goodchild MF, Maguire DJ, Rhind DW (2015) Geographic information science and systems. John Wiley & Sons, New York
Martínez F, Rueda AJ, Feito FR (2009) A new algorithm for computing Boolean operations on polygons. Comput Geosci 35(6):1177–1185. https://doi.org/10.1016/j.cageo.2008.08.009
Puri S, Prasad SK (2014) Output-sensitive parallel algorithm for polygon clipping. In: Proceedings of IEEE International Conference on Parallel Processing, pp 241–250. https://doi.org/10.1109/ICPP.2014.33
Puri S, Prasad SK (2015) A parallel algorithm for clipping polygons with improved bounds and a distributed overlay processing system using MPI. In: Proceedings of IEEE/ ACM International Symposium on Cluster, Cloud and Grid Computing, pp 576–585. https://doi.org/10.1109/CCGrid.2015.43
Puri S, Agarwal D, He X, Prasad SK (2013) MapReduce algorithms for GIS polygonal overlay processing. In: Proceedings of IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), pp 1009–1016. https://doi.org/10.1109/IPDPSW.2013.254
Ren FH (1989) Theory, method and application of geographical information system. Peking University, Dissertation
Sellis T, Roussopoulos N, Faloutsos C (1987) The R+-tree: a dynamic index for multi-dimensional objects. In: proceedings of the 13th international conference on very large data. Bases:507–518
Shi X (2012) System and Methods for Parallelizing Polygon Overlay Computation in Multiprocessing Environment. US 20120320087 A1
Vatti BR (1992) A generic solution to polygon clipping. Commun ACM 35(7):56–63. https://doi.org/10.1145/129902.129906
Wang F (1993) A parallel intersection algorithm for vector polygon overlay. IEEE Comput Graph 13(2):74–81. https://doi.org/10.1109/38.204970
Wang JC, Cui C, Pu YX, Ma JS, Chen G (2010) A novel algorithm of buffer construction based on run-length encoding. Cartogr J 47(3):198–210. https://doi.org/10.1179/000870410X12786821061413
Wang JC, Cui C, Chen G, Pu YX, Ma JS (2012a) A new trapezoidal-mesh based data model for spatial operations. Int J Digit Earth 5(2):165–183. https://doi.org/10.1080/17538947.2011.580860
Wang KB, Huai Y, Lee RB, Wang FS, Zhang XD, Saltz JH (2012b) Accelerating pathology image data cross-comparison on CPU-GPU hybrid systems. PVLDB 5:1543–1554. https://doi.org/10.14778/2350229.2350268
Wang Y, Liu ZL, Liao HY (2015) Improving the performance of GIS polygon overlay computation with MapReduce for spatial big data processing. Cluster Comput 18(2):507–516. https://doi.org/10.1007/s10586-015-0428-x
Weiler K, Atherton P (1977) Hidden surface removal using polygon area sorting. In: Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques, pp 214–222. https://doi.org/10.1145/563858.563896
Zhou XF, Abel DJ, Truffet D (1998) Data partitioning for parallel spatial join processing. GeoInformatica 2(2):175–204. https://doi.org/10.1023/A:1009755931056
Zhou CH, Ou Y, Yang L, Qin B (2007) An equal area conversion model for rasterization of vector polygons. Sci China Ser D 50(S1):169–175. https://doi.org/10.1007/s11430-007-5013-6
Zhou C, Chen ZJ, Li MC (2018) A parallel method to accelerate geospatial operations involving polygon intersections. Int J Geogr Inf Sci 32(12):2402–2426. https://doi.org/10.1080/13658816.2018.1508689
Funding
This work was supported by the National Key R&D Program of China (Grant number 2017YFB0504205).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
No potential conflict of interest was reported by the authors.
Additional information
Communicated by: H. Babaie
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Zhou, C., Li, M. Improving and evaluating boundary algebra filling for identifying polygon intersections. Earth Sci Inform 12, 581–597 (2019). https://doi.org/10.1007/s12145-019-00405-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12145-019-00405-z