Acta Geodaetica et Cartographica Sinica ›› 2015, Vol. 44 ›› Issue (3): 338-345.doi: 10.11947/j.AGCS.2015.20140017
Previous Articles Next Articles
FAN Junfu1,2, KONG Weihua1, MA Ting2, ZHOU Chenghu2, JI Min3, ZHOU Yuke2
Received:
2014-01-10
Revised:
2014-10-11
Online:
2015-03-20
Published:
2015-04-01
Supported by:
CLC Number:
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] MARTNEZ 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.) |
[1] | LIU Jingnan, LUO Yarong, GUO Chi, GAO Kefu. PNT intelligence and intelligent PNT [J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(6): 811-828. |
[2] | HAN Litao, ZHOU Lijuan, GONG Cheng, ZHANG Aiguo. An indoor navigation network considering walking habits and its generation algorithm [J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(5): 729-738. |
[3] | FANG Jinfeng, MENG Xiangfu. POI recommendation based on LBSN and multi-graph fusion [J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(5): 739-749. |
[4] | ZHANG Ruizhuo. Risk assessment of power transmission corridors in forestry area based on multi-source data [J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(5): 784-784. |
[5] | XIA Jizhe, ZHOU Ying, LI Zhen, LI Fan, YUE Yang, CHENG Tao, LI Qingquan. COVID-19 risk assessment driven by urban spatiotemporal big data: a case study of Guangdong-Hong Kong-Macao Greater Bay Area [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6): 671-680. |
[6] | ZHU Qing, FENG Bin, LI Maosu, CHEN Meite, XU Zhaowen, XIE Xiao, ZHANG Yeting, LIU Mingwei, HUANG Zhiqin, FENG Yicong. An efficient sparse graph index method for dynamic and associated data [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6): 681-691. |
[7] | LU Chuanwei, SUN Qun, CHEN Bing, WEN Bowei, ZHAO Yunpeng, XU Li. Road learning extraction method based on vehicle trajectory data [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6): 692-702. |
[8] | YIN Shuo, YAN Xiaoming, YAN Xiongfeng. Simplification method of building polygon based on feature edges reconstruction [J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(6): 703-710. |
[9] | WU Huayi, HUANG Rui, YOU Lan, XIANG Longgang. Recent progress in taxi trajectory data mining [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1341-1356. |
[10] | GUO Qingsheng, LIU Yang, LI Meng, CHENG Xiaoxi, HE Jie, WANG Huihui, WEI Zhiwei. A progressive simplification method of navigation road map based on mesh model [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1357-1368. |
[11] | WU Zheng, WU Pengda, LI Chengming. Adaptive hierarchical spatio-temporal index construction method for vector data under peer-to-peer networks [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1369-1379. |
[12] | WANG Peixiao, ZHANG Hengcai, WANG Haibo, WU Sheng. Spatial-temporal clustering by fast search and find of density peaks [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1380-1390. |
[13] | WAN Zijian, LI Lianying, YANG Min, ZHOU Xiaodong. Decision tree model for extracting road intersection feature from vehicle trajectory data [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1391-1403. |
[14] | HU Guanghui, XIONG Liyang, TANG Guoan. Vector geometry based method for the extraction of slope of aspect by using DEMs [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1404-1414. |
[15] | ZHANG Xu, HAO Xiangyang, LI Jiansheng, LI Pengyue. Fusion and visualization method of dynamic targets in surveillance video with geospatial information [J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1415-1423. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||