无重迭边的可重入多边形裁剪算法

摘要

本文提出一种在标准 Sutherland—Hodgman 多边形裁剪算法基础上扩充的重迭边消去算法。本算法在沿着窗口边沿直线对多边形的各边进行裁剪的时候,建立了一个中间结果顶点队列和一个交点队列,然后通过顶点追溯方法产生出作为裁剪结果的一列子多边形.这些子多边形的定义方式与输入多边形相同,不存在重迭的边,而且仍然保持可重入性.