Title简单多边形裁剪算法
Other TitlesAlgorithm for simple polygon clipping
Authors宋树华
濮国梁
罗旭
陈东
陈润强
Affiliation北京大学遥感与地理信息系统研究所,北京100871
中国资源卫星应用中心,北京100094
北京大学遥感与地理信息系统研究所,北京,100871
中煤科技集团公司,北京,100013
北京应用气象研究所,北京,100029
Keywords多边形裁剪 交点 前驱 后继 矢量数组 polygon clipping intersection points predecessor successor vector
Issue Date2014
Publisher计算机工程与设计
Citation计算机工程与设计.2014,35,(1),192-197.
Abstract为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法.该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形.其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数.该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点.
URIhttp://hdl.handle.net/20.500.11897/207322
ISSN1000-7024
DOI10.3969/j.issn.1000-7024.2014.01.036
Indexed中文核心期刊要目总览(PKU)
中国科技核心期刊(ISTIC)
中国科学引文数据库(CSCD)
Appears in Collections:地球与空间科学学院

Files in This Work
Adobe PDF

Web of Science®



Checked on Last Week

Scopus®



Checked on Current Time

百度学术™



Checked on Current Time

Google Scholar™





License: See PKU IR operational policies.