RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

doi:10.11947/j.AGCS.2015.20140017

测绘学报 ›› 2015, Vol. 44 ›› Issue (3): 338-345.doi: 10.11947/j.AGCS.2015.20140017

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

范俊甫^1,2, 孔维华¹, 马廷², 周成虎², 季民³, 周玉科²

1. 山东理工大学建筑工程学院, 山东淄博 255049;
2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101;
3. 山东科技大学测绘科学与工程学院, 山东青岛 266590

收稿日期:2014-01-10 修回日期:2014-10-11 出版日期:2015-03-20 发布日期:2015-04-01
作者简介:范俊甫(1985—),男,博士,研究方向为并行空间分析算法. E-mail:fanjf@sdut.edu.cn
基金资助:
国家自然科学基金(41471330);国家科技支撑计划(2012BAH27B04);中国科学院重点部署项目(KZZD-EW-07);山东省自然科学基金(ZR2012DL06);山东理工大学博士科研基金(4041-414039)

RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysis

FAN Junfu^1,2, KONG Weihua¹, MA Ting², ZHOU Chenghu², JI Min³, ZHOU Yuke²

1. School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255049, China;
2. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences, Beijing 100101, China;
3. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China

Received:2014-01-10 Revised:2014-10-11 Online:2015-03-20 Published:2015-04-01
Supported by:
The National Natural Science Foundation of China (No.41471330);The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (No.2012BAH27B04);Key Research Program of the Chinese Academy of Sciences (No.KZZD-EW-07);Shandong Provincial Natural Science Foundation, China (No.ZR2012DL06);Doctoral Research Foundation of Shandong University of Technology (No.4041-414039)

摘要/Abstract

摘要： 传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(NlogN)~O(N²)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化.在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪.本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论.试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为ON;在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差.RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效.

关键词: 栅格化, 多边形裁剪, 点面包含, 环绕追踪, 面积误差

Abstract: Computational efficiencies of traditional vector computing-based polygon clipping algorithms will decrease rapidly when handling polygons contain large amount of vertices. The computing flows of traditional polygon clipping algorithms are tightly coupled with special data structures, which difficult to be optimized in the underlying of them. Under the premise of meeting a certain degree of area errors, the polygon clipping problem can be solved by introducing the idea of rasterization processing. In this research, we proposed a new rasterization processing-based polygon clipping algorithm: the RaPC algorithm, on the basis of analyzing the characteristics of existing algorithms. The area errors of results of the new algorithm are also analyzed and discussed. Experimental results show that the efficiencies of the RaPC algorithm can be enhanced significantly when using large grid cells, and it shows a linear trend growth with the increase of amount of polygon vertices. Compared with the Vatti algorithm, the RaPC algorithm represents more efficiencies on dealing clipping issues between polygons with large amount of vertices, the former shows lower time costs when handling polygons with less vertices. The area error of computing results of the RaPC algorithm is closely related with the grid size, and errors can be reduced using smaller grid sizes. Therefore the RaPC algorithm showed higher efficiencies on processing polygons with large amount of vertices than the Vatti algorithm and presented practical values to some degree.

Key words: rasterization, polygon clipping, point in polygon, winding and tracing, area error

中图分类号:

P208

范俊甫, 孔维华, 马廷, 周成虎, 季民, 周玉科. RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析[J]. 测绘学报, 2015, 44(3): 338-345.

FAN Junfu, KONG Weihua, MA Ting, ZHOU Chenghu, JI Min, ZHOU Yuke. RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysis[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(3): 338-345.

参考文献

[1] DOWERS S, GITTINGS B M, MINETER M J. Towards a Framework for High-performance Geocomputation: Handling Vector-topology within a Distributed Service Environment[J]. Computers, Environment and Urban Systems,2000, 24(5): 471-486.
[2] GOODCHILD M F. Statistical Aspects of the Polygon Overlay Problem[M]//DUTTON G. Harvard Papers on Geographic Information Systems. Reading, MA:Addison-Wesley Publishing Company, 1977.
[3] AGARWAL D, PURI S, HE Xi, et al. A System for GIS Polygonal Overlay Computation on Linux Cluster: An Experience and Performance Report[C]//Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum.Shanghai: IEEE, 2012: 1433-1439.
[4] SHAMOS M I, HOEY D.Geometric Intersection Problems[C]//Proceedings of the 17th Annual Symposium on Foundations of Computer Science.Washington DC: IEEE, 1976:208-215.
[5] BENTLEY J L, OTTMANN T A. Algorithms for Reporting and Counting Geometric Intersections[J].IEEE Transactions on Computers,1979, C-28(9): 643-647.
[6] PREPARATA F P, SHAMOS M I. Computational Geometry: An Introduction[M]. Translated by Zhuang Xingu.Beijing: Science Press, 1990. (PREPARATA F P, SHAMOS M I. 计算几何导论[M]. 庄心谷, 译. 北京: 科学出版社, 1990.)
[7] WEILER K, ATHERTON P. Hidden Surface Removal Using Polygon Area Sorting[C]//Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1977:214-222.
[8] VATTI BR. A Generic Solution to Polygon Clipping[J]. Communications of the ACM, 1992, 35(7): 56-63.
[9] GREINER G, HORMANN K. Efficient Clipping of Arbitrary Polygons[J]. ACM Transactions on Graphics, 1998, 17(2): 71-83.
[10] CHEN Zhanlong, WU Xincai, WU Liang. 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-108. (陈占龙, 吴信才, 吴亮. 基于单调链和STR树的简单要素模型多边形叠置分析算法[J]. 测绘学报, 2010, 39(1): 102-108.)
[11] LIU Yongkui, GAO Yun, HUANG Youqun. An Efficient Algorithm for Polygon Clipping[J]. Journal of Software, 2003, 14(4): 845-856. (刘勇奎, 高云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4): 845-856.)
[12] KUI Liuyong, QIANG Wangxiao, ZHE Baoshu, et al. An Algorithm for Polygon Clipping, and for Determining Polygon Intersections and Unions[J]. Computers & Geosciences, 2007, 33(5): 589-598.
[13] MARTNEZ F, RUEDA A J, FEITO F R. A New Algorithm for Computing Boolean Operations on Polygons[J]. Computers & Geosciences, 2009, 35(6): 1177-1185.
[14] MURTA A.A General Polygon Clipping Library[EB/OL].[2013-11-01].http://www.cs.man.ac.uk/~toby/alan/software/gpc.html.
[15] XIE Zhong, WEI Dongqi, WU Liang, et al. Graph Model of Polygon Clipping Using Simple Vector Data[J]. Acta Geodaetica et CartographicaSinica, 2009, 38(4): 369-374. (谢忠, 魏东琦, 吴亮, 等. 简单矢量数据多边形裁剪问题的图模型[J]. 测绘学报, 2009, 38(4): 369-374.)
[16] LEONOV M. Comparison of the Different Algorithms for Polygon Boolean Operations[EB/OL]. [2013-11-02]. http://www.complex-a5.ru/polyboolean/comp.html.
[17] FAN Junfu, MA Ting, JI Min, et al. Implementation and Optimization of Eight Parallel Polygon Overlapping Tools with OpenMP at the Feature Layer Level in GIS[J]. Progressin Geography, 2013, 32(12): 1835-1844. (范俊甫, 马廷, 季民, 等. GIS中8种图层级多核并行多边形叠置分析工具的实现及优化方法[J]. 地理科学进展, 2013, 32(12): 1835-1844.)
[18] BATES P D, DEROO A P J. A Simple Raster-based Model for Flood Inundation Simulation[J]. Journal of Hydrology, 2000, 236(1-2): 54-77.
[19] YANG Cunjian, ZHANG Zengxiang. Models of Accuracy Loss During Rasterizing LanduseVector Data with Multi-scale Grid Size[J]. Geographical Research, 2001, 20(4): 416-422. (杨存建, 张增祥. 矢量数据在多尺度栅格化中的精度损失模型探讨[J]. 地理研究, 2001, 20(4): 416-422.)
[20] CHEN Shupeng, LU Xuejun, ZHOU Chenghu. Introduction to Geographic Information Systems[M]. Beijing: Science Press, 1999. (陈述彭, 鲁学军, 周成虎. 地理信息系统导论[M]. 北京: 科学出版社, 1999.)
[21] BAI Yan, LIAO Shunbao, SUN Jiulin. Scale Effect and Methods for Accuracy Evaluation of Attribute Information Loss in Rasterization[J]. Journal of Geographical Sciences, 2011, 21(6): 1089-1100.
[22] LI Yuguang, LI Lianying, LI Qingquan, et al. Vector Map Geometric Data Change Detection Based on Grid Method[J]. Geospatial Information, 2010, 8(1): 142-146. (李宇光, 李莲营, 李清泉, 等. 基于栅格化思想的矢量电子地图几何变化检测[J]. 地理空间信息, 2010, 8(1): 142-146.)
[23] CHEN Jianjun, ZHOU Chenghu, CHENG Weiming. Area Error Analysis of Vector to Raster Conversion of Areal Feature in GIS[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 344-350. (陈建军, 周成虎, 程维明. GIS中面状要素矢量栅格化的面积误差分析[J]. 测绘学报, 2007, 36(3): 344-350.)
[24] ZHOU Chenghu, OU Yang, YANG Liao, et al. An Equal Area Conversion Model for Rasterization of Vector Polygons[J]. Science in China: Series D: Earth Sciences, 2007, 50(S1): 169-175. (周成虎, 欧阳, 杨辽, 等. 矢量多边形栅格化的保积优化模型[J]. 中国科学D辑: 地球科学, 2006, 36(增刊Ⅱ): 157-163.)
[25] SHORTRIDGE A M. Geometric Variability of Raster Cell Class Assignment[J]. International Journal of Geographical Information Science, 2004, 18(6): 539-558.
[26] ZHOU Peide. Computational Geometry Algorithm Design and Analysis(Fourth Edition)[M]. Beijing: Tsinghua University Press, 2011. (周培德. 计算几何:算法设计与分析(第4版)[M]. 北京: 清华大学出版社, 2011.)

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysis

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价