摘要: 多边形的布尔运算是计算机图形学中最常用的功能之一。二次曲线作为一种最为简单的曲线，因为其良好的几何属性和灵活的控制参数，从而在计算几何中具有重要作用，但是目前对二次曲线多边形的布尔算法研究较少。二次曲线多边形是由二次曲线段或者有界二次曲线(如圆或者椭圆)组成的多边形。现有的二次曲线多边形布尔算法大多是在Bentley-Ottmann算法基础上进行扩展，为了满足Bentley-Ottmann算法的前提条件，需要将二次曲线(段)分解为多个x单值的曲线段，并添加辅助线才能实现。
本文提出一般多边形布尔运算的框架，并基于二次曲线的拓扑空间关系，提出了一种二次曲线多边形三种布尔运算(包括交运算、并运算和减运算)算法。算法考虑了各种蜕化情况，如两个边界相同，互补，边界落在另外一个多边形内部和边界落在另外一个多边形的外部等情况。本文工作采用C#实现了该算法，并对算法时间复杂度进行分析，认为对于两个分别包含m和n个二次曲线段的二次曲线多边形来说，其时间复杂度为O(m*n)，其中求取二次曲线多边形之间交点的时间在整个二次曲线多边形布尔运算中所占的时间比例最大。
本文首先给出二次曲线多边形的定义和一些基本运算，以及一般多边形布尔运算的原理和基本流程，然后给出了二次曲线多边形布尔运算的详细算法。具体的算法如下：(1) 求解两个二次曲线多边形的交点；(2) 依次计算每个交点附近两个多边形之间的局部拓扑关系；(3) 基于局部拓扑关系，依据路径跟踪规则表进行路径跟踪，得到一个二次曲线边界的集合，这个集合是结果二次曲线多边形中边界的一部分；(4) 计算二次曲线多边形的全局拓扑关系，包括两个边界之间的同型(homology)/互补(complement)关系，以及一个边界与另外一个二次曲线多边形之间的内(interior)/外(exterior)关系；(5) 那些与别的多边形同型或者互补，或者与别的多边形存在内/外关系的边界称为没有被穿越的边界，在路径跟踪中无法得到处理，因此需要依据边界选择规则，确定哪些没有被穿越的边界会成为布尔运算结果的边界； (6) 合并来自路径跟踪和边界选择的边界，得到布尔运算的结果。
实验表明，该算法能够稳定工作，获得正确的布尔运算结果。对于大计算量的应用来说，运算效率至关重要。考虑到二次曲线多边形布尔运算的时间复杂度决定于两个二次曲线多边形之间交点数量，并且交点计算的时间在布尔运算中所占的比重最大，因此研究高速二次曲线的交点求解方法是将来的工作之一。同时，多核计算机已经普及，将二次曲线多边形运算分解为若干个独立的任务，实现并行运算，也是将来的工作之一。
二次曲线是最为简单的曲线，本文所提出的二次曲线的布尔算法在计算机动画、计算机图形、计算机辅助设计、机器人以及虚拟现实等领域都有较为广泛的应用前景。