[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]
点击复制

一种处理交点退化现象的高效多边形裁剪算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
46
期数:
2016年第4期
页码:
702-707
栏目:
计算机科学与工程
出版日期:
2016-07-20

文章信息/Info

Title:
A high efficient polygon clipping algorithm for dealing with intersection degradation
作者:
王慧青1崇素文2
1东南大学仪器科学与工程学院, 南京210096; 2展讯通信(上海)有限公司, 上海 201203
Author(s):
Wang Huiqing1 Chong Suwen2
1School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China
2Spreadtrum Communications(Shanghai)Co., Ltd., Shanghai 201203, China
关键词:
多边形裁剪 交点退化 单向链表 方向关系
Keywords:
polygon clipping intersection degradation singly linked list direction relationship
分类号:
TP391
DOI:
10.3969/j.issn.1001-0505.2016.04.005
摘要:
针对复杂多边形裁剪中出现的多边形彼此间重点和重边现象,提出了一种能够处理交点退化现象的高效多边形裁剪算法.该算法利用单向链表实现多边形的存储,同时基于单调链的平面扫描法求解多边形间的交点,减少了多边形顶点的遍历次数和求交次数;对于重点和重边现象,通过交点关联的线段间的方向关系判别交点的进出性;最后更新多边形顶点序列,获取裁剪结果.实验结果表明,该算法能够完成对含内环多边形的裁剪,在交点退化情况下也能获得准确的裁剪结果.且该算法裁剪效率较Greiner-Hormann算法大幅提高,具有很高的执行效率和实用性.
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.

备注/Memo

备注/Memo:
收稿日期: 2015-12-21.
作者简介: 王慧青(1976—),女,博士,副研究员,921394420@qq.com.
基金项目: “十二五”国家科技支撑计划资助项目(2013BAJ13B01).
引用本文: 王慧青,崇素文.一种处理交点退化现象的高效多边形裁剪算法[J].东南大学学报(自然科学版),2016,46(4):702-707. DOI:10.3969/j.issn.1001-0505.2016.04.005.
更新日期/Last Update: 2016-07-20