# [1]王慧青,崇素文.一种处理交点退化现象的高效多边形裁剪算法[J].东南大学学报(自然科学版),2016,46(4):702-707.[doi:10.3969/j.issn.1001-0505.2016.04.005] 　Wang Huiqing,Chong Suwen.A high efficient polygon clipping algorithm for dealing with intersection degradation[J].Journal of Southeast University (Natural Science Edition),2016,46(4):702-707.[doi:10.3969/j.issn.1001-0505.2016.04.005] 点击复制 一种处理交点退化现象的高效多边形裁剪算法() 分享到： var jiathis_config = { data_track_clickback: true };

46

2016年第4期

702-707

2016-07-20

## 文章信息/Info

Title:
A high efficient polygon clipping algorithm for dealing with intersection degradation

1东南大学仪器科学与工程学院, 南京210096; 2展讯通信(上海)有限公司, 上海 201203
Author(s):
1School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China
2Spreadtrum Communications(Shanghai)Co., Ltd., Shanghai 201203, China

Keywords:

TP391
DOI:
10.3969/j.issn.1001-0505.2016.04.005

Abstract:
Aiming at complex polygon clipping with coincidence points and coincidence edges, a high efficient algorithm for polygon clipping is proposed for dealing with intersection degradation. The algorithm uses singly linked lists to store polygons, and acquires intersection points between polygons based on the planar scanning method with a monotone chain, thus reducing the times of traversing polygon vertices and calculating intersections. Then, it marks the entry and exit points to the clipping polygon’s interior based on the direction relationship between line segments with intersections. Finally, it updates the polygon vertex sequence and obtains cutting results. The experimental results show that the algorithm can clip a polygon with several inner rings, and obtain right clipping results even under the condition of intersection degradation. The cutting efficiency of the algorithm is significantly higher than that of the Greiner-Hormann algorithm. Therefore, it has high efficiency and practicability.

## 参考文献/References:

[1] 宋树华, 濮国梁, 罗旭, 等. 简单多边形裁剪算法[J]. 计算机工程与设计, 2014, 35(1):192-197.DOI:10.3969/j.issn.1000-7024.2014.01.036.
Song Shuhua, Pu Guoliang, Luo Xu, et al. Algorithm for simple polygon clipping[J]. Computer Engineering and Design, 2014, 35(1):192-197. DOI:10.3969/j.issn.1000-7024.2014.01.036.(in Chinese)
[2] Weiler K, Atherton P. Hidden surface removal using polygon area sorting[J]. ACM SIGGRAPH Computer Graphics, 1977, 11(2):214-222. DOI:10.1145/965141.563896.
[3] Vatti B R. A generic solution to polygon clipping[J]. Communications of the ACM, 1992, 35(7):56-63.DOI:10.1145/129902.129906.
[4] Greiner G, Hormann K. Efficient clipping of arbitrary polygons[J]. ACM Transactions on Graphics, 1998, 17(2):71-83. DOI:10.1145/274363.274364.
[5] 刘勇奎, 高云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4):845-856.
Liu Yongkui, Gao Yun, Huang Youqun. An efficient algorithm for polygon clipping[J]. Journal of Software, 2003, 14(4):845-856.(in Chinese)
[6] 张钧, 王鹏. 一种新的矢量数据多边形的快速裁剪算法[J]. 中国图象图形学报, 2008, 13(12):2409-2413.
Zhang Jun, Wang Peng. A new fast polygon clipping algorithm for vector data[J]. Journal of Image and Graphics, 2008, 13(12):2409-2413.(in Chinese)
[7] 王结臣, 沈定涛, 陈焱明,等. 一种有效的复杂多边形裁剪算法[J]. 武汉大学学报(信息科学版), 2010,35(3): 369-372,377.
Wang Jiechen,Shen Dingtao,Chen Yanming,et al. An efficient algorithm for complex polygon clipping [J]. Geomatics and Information Science of Wuhan University, 2010, 35(3): 369-372,377.(in Chinese)
[8] 彭杰, 刘南, 唐远彬, 等. 一种基于交点排序的高效多边形裁剪算法[J]. 浙江大学学报(理学版), 2012, 39(1):107-111,122. DOI:10.3785/j.issn.1008-9497.2012.01.022.
Peng Jie, Liu Nan, Tang Yuanbin, et al. An efficient algorithm for polygon clipping based on intersection points sorting[J]. Journal of Zhejiang University(Science Edition), 2012, 39(1):107-111,122. DOI:10.3785/j.issn.1008-9497.2012.01.022.(in Chinese)
[9] 邓敏, 李志林, 吴静. 空间关系理论与方法[M]. 北京:科学出版社, 2013:88-110.
[10] 闫浩文, 张黎明, 李茜茜, 等. 复合多边形求差的高效矢量算法[J]. 计算机应用研究, 2013, 30(10):3192-3194. DOI:10.3969/j.issn.1001-3695.2013.10.079.
Yan Haowen, Zhang Liming, Li Qianqian, et al. Vector-based efficient algorithm for computing differences between two complex polygons[J]. Application Research of Computers, 2013, 30(10):3192-3194. DOI:10.3969/j.issn.1001-3695.2013.10.079.(in Chinese)
[11] Chen Z L, Ma L N, Wu L. Polygon overlay analysis algorithm based on monotone chain and STR tree in the simple feature model[C]//2010 International Conference on Electrical and Control Engineering. Harbin, China, 2010: 2905-2909. DOI:10.1109/icece.2010.1420.