高效的多边形布尔计算方法

针对计算机图形学中应用广泛的多边形布尔计算，提出了一种新的、适用于一般多边形的并集、交集和差集算法。算法主要分为计算交点、将交点插入多边形顶点序列、遍历三个步骤。通过采用循环单链表的数据结构、避开复杂的出入点计算、及预先的一些碰撞检测以避开复杂的求交运算与链表遍历等技巧，提高了算法的执行速度、减少了存储单元。算法能够很好地处理一些奇异情形（边界情形），比如重叠边、交点为边的顶点等情形，具有很好的鲁棒性。与经典的Weiler算法、Vatti算法和Greiner-Hormann算法相比，该算法具有较低的时间复杂度O（（ m+n+k） log d））和空间复杂度。实验结果显示该算法在处理2222×2222个顶点、42个交点时比经典的Weiler算法速度提高了296倍。算法的主要思想对确定两个多面体的交、并、差问题亦有参考价值。

Efficient algorithm for Boolean operations on polygons