简单多边形裁剪算法

doi:10.3969/j.issn.1000-7024.2014.01.036

CORC > 北京大学 > 地球与空间科学学院

	简单多边形裁剪算法; Algorithm for simple polygon clipping
	宋树华 ; 濮国梁 ; 罗旭 ; 陈东 ; 陈润强
刊名	计算机工程与设计
	2014
关键词	多边形裁剪交点前驱后继矢量数组 polygon clipping intersection points predecessor successor vector
DOI	10.3969/j.issn.1000-7024.2014.01.036
英文摘要	为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法.该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形.其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数.该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点.; 中文核心期刊要目总览(PKU); 中国科技核心期刊(ISTIC); 中国科学引文数据库(CSCD); 0; 1; 192-197; 35
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/207322]
专题	地球与空间科学学院
推荐引用方式 GB/T 7714	宋树华,濮国梁,罗旭,等. 简单多边形裁剪算法, Algorithm for simple polygon clipping[J]. 计算机工程与设计,2014.
APA	宋树华,濮国梁,罗旭,陈东,&陈润强.(2014).简单多边形裁剪算法.计算机工程与设计.
MLA	宋树华,et al."简单多边形裁剪算法".计算机工程与设计 (2014).