简单多边形裁剪算法

摘要：

为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法.该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形.其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数.该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点.

关键词：多边形裁剪、交点、前驱、后继、矢量数组

所属期刊栏目：35

分类号：TP391(计算技术、计算机技术)

在线出版日期：2014-03-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：192-197