格网划分的双策略跟踪多边形裁剪算法

摘要：

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单多边形,同时也支持多边形的“并”和“差”等布尔运算.首先,设计了算法所需的数据结构；其次,基于直线扫描转换Bresenham算法原理提出了边网格划分的有效算法,并应用一个简单的方法避免不同网格内边的重复求交；最后,将交点分类为普通交点和顶交点,并针对这两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处理特殊情况时的稳定性.与其它同类算法的比较表明,新算法具有更高的效率.

关键词：凹多边形、多边形裁剪、跟踪策略、网格划分、单线性链表

所属期刊栏目：33

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

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

页数：共5页

页码：45-49