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

摘要

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