论文部分内容阅读
本文提出一种多边形布尔运算的快速算法。首先采用平面扫描方法计算两个多边形之间的交叉点,然后计算出属于布尔运算结果的线段链,最后将这些线段链拼接成对应布尔运算的多边形。该算法可以对任意多边形,包括有洞和自交叉的凹多边形,进行布尔运算。该算法的时间复杂度为O(nlog(n),其中n是多边形的总边数。实验表明当n较大的时候,本文提出算法性能仍然很稳定。