论文部分内容阅读
针对计算机图形学中应用广泛的多边形布尔计算,提出了一种新的、适用于一般多边形的并集、交集和差集算法。算法主要分为计算交点、将交点插入多边形顶点序列、遍历三个步骤。通过采用循环单链表的数据结构、避开复杂的出入点计算、及预先的一些碰撞检测以避开复杂的求交运算与链表遍历等技巧,提高了算法的执行速度、减少了存储单元。算法能够很好地处理一些奇异情形(边界情形),比如重叠边、交点为边的顶点等情形,具有很好的鲁棒性。与经典的Weiler算法、Vatti算法和Greiner-Hormann算法相比,该算法具有较低的