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

Efficient algorithm for Boolean operations on polygons

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

In this paper, a new algorithm was proposed for Boolean operations on general polygons, including union,intersection and difference calculations of two polygons, which are of wide application in computer graphics. Our algorithm includes three main steps： computing the intersection points, inserting the intersection points into the polygon vertex lists, and vertex traversal. The adoption of single-linked list data structure enables less storage space. And through uniform processing on intersection points and beforehand collision detection to avoid complicated intersection calculation, this algorithm can accelerate the execution speed and reduce further the storage space. The algorithm possesses good robustness since it can tackle with many singular cases very well. Compared with the classical Weiler algorithm, Vatti algorithm and Greiner-Hormann algorithm, our algorithm has lower time complexity（ O（（ m ＋ n ＋ k） log d）） and space complexity. The experiments illustrate the efficiency of this algorithm. For a case with 2 222 × 2 222 vertices and 42 intersection points, this algorithm is 296 faster than Weiler algorithm. The main idea of this algorithm is also applicable to the union, intersection and difference calculation of polyhedra.