几何图形布尔运算简介

布尔运算在计算机领域是一个多含义的概念，包括逻辑上布尔类型的与并否操作，而在计算机几何上，它代表的是多边形或多面体之间的集合与并或非等操作。我们也可以粗暴地将图形布尔运算理解为多面体或多边形的加剪法运算，下图展示了多边形间的布尔运算。

布尔运算在BIM领域的应用

几何图形的布尔运算在BIM中很经常会用到，常见的有（1）梁柱之间的连接部位剪切、（2）现浇结构体与预制结构之间的扣减倒模、（3）绿化区域不同植被的面积计算等。

上述的1、2种情况属于**多面体（polyhedra）**的布尔运算，对于这种情况，达索的Spatial建模内核有很好的支持，我们常用的BIM开发平台Revit对Spatial布尔运算有一定的封装，除了极端的精度问题外，可以满足大部分场景的需要。

第3种情况属于多边形（polygon）的布尔运算，对于这种情况，目前我们用的是一个开源的多边形运算库clipperlib。然而ClipperLib只支持由线段构成的多边形间的布尔运算，且由于浮点数存在精度问题，ClipperLib只支持整形数据，这就会导致我们在实际应用时无法很好地保持曲线描述以及精度。对于这个问题，我们稍后会提出使用CGAL如何进行解决。

除了以上的两种情况，其实还有一种很常用的情况，就是设计师需要通过构造一些不规则的直线和曲线（包括圆锥曲线和样条线），并通过这些线找到闭合的区域。对于这种应用场景，Spatial和clipperLib都没法很好地解决，而通过CGAL，我们存在解决这种问题的方法。

CGAL中的布尔运算

查阅CGAL帮助文档，我们发现CGAL支持以下操作：

二维平面多边形的布尔运算：该多边形的布尔运算突破了ClipperLib对整形以及直线段的依赖，CGAL中的多边形可以支持直线段、圆弧、圆锥曲线弧、样条线以及任意可以用多项式方程表达的平面曲线。三维多面体的布尔运算：与Spatial功能类似，这里不过度关注。2D-Arrangement（二维平面划分）：在查看帮助文档的过程中，我们惊喜地发现这个2D Arrangement模块，它能很好地贴合我们上面描述的通过线获取闭合区域的应用场景。2D Arrangement可以理解为一个二维平面的划分，通过给这个Arrangement添加不同的直线段和曲线段，CGAL内核会把平面分割成一个个闭合或不闭合的模块，而添加的线段也会被相互进行分割，变成多条首尾相连、互不相交的线段。下图是一个2D Arrangement的示例图：

2D Arrangement的构建

参考以下代码

// Constructing an arrangement of various conic arcs. #include <CGAL/config.h> #ifndef CGAL_USE_CORE #include <iostream> int main () { std::cout << "Sorry, this example needs CORE ..." << std::endl; return 0; } #else #include <CGAL/Cartesian.h> #include <CGAL/CORE_algebraic_number_traits.h> #include <CGAL/Arr_conic_traits_2.h> #include <CGAL/Arrangement_2.h> typedef CGAL::CORE_algebraic_number_traits Nt_traits; typedef Nt_traits::Rational Rational; typedef Nt_traits::Algebraic Algebraic; typedef CGAL::Cartesian<Rational> Rat_kernel; typedef Rat_kernel::Point_2 Rat_point_2; typedef Rat_kernel::Segment_2 Rat_segment_2; typedef Rat_kernel::Circle_2 Rat_circle_2; typedef CGAL::Cartesian<Algebraic> Alg_kernel; typedef CGAL::Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits> Traits_2; typedef Traits_2::Point_2 Point_2; typedef Traits_2::Curve_2 Conic_arc_2; typedef CGAL::Arrangement_2<Traits_2> Arrangement_2; int main () { Arrangement_2 arr; // Insert a hyperbolic arc, supported by the hyperbola y = 1/x // (or: xy - 1 = 0) with the endpoints (1/5, 4) and (2, 1/2). // Note that the arc is counterclockwise oriented. Point_2 ps1 (Rational(1,4), 4); Point_2 pt1 (2, Rational(1,2)); Conic_arc_2 c1 (0, 0, 1, 0, 0, -1, CGAL::COUNTERCLOCKWISE, ps1, pt1); insert (arr, c1); // Insert a full ellipse, which is (x/4)^2 + (y/2)^2 = 0 rotated by // phi=36.87 degree (such that sin(phi) = 0.6, cos(phi) = 0.8), // yielding: 58x^2 + 72y^2 - 48xy - 360 = 0. Conic_arc_2 c2 (58, 72, -48, 0, 0, -360); insert (arr, c2); // Insert the segment (1, 1) -- (0, -3). Rat_point_2 ps3 (1, 1); Rat_point_2 pt3 (0, -3); Conic_arc_2 c3 (Rat_segment_2 (ps3, pt3)); insert (arr, c3); // Insert a circular arc supported by the circle x^2 + y^2 = 5^2, // with (-3, 4) and (4, 3) as its endpoints. We want the arc to be // clockwise oriented, so it passes through (0, 5) as well. Rat_point_2 ps4 (-3, 4); Rat_point_2 pm4 (0, 5); Rat_point_2 pt4 (4, 3); Conic_arc_2 c4 (ps4, pm4, pt4); CGAL_assertion (c4.is_valid()); insert (arr, c4); // Insert a full unit circle that is centered at (0, 4). Rat_circle_2 circ5 (Rat_point_2(0,4), 1); Conic_arc_2 c5 (circ5); insert (arr, c5); // Insert a parabolic arc that is supported by a parabola y = -x^2 // (or: x^2 + y = 0) and whose endpoints are (-sqrt(3), -3) ~ (-1.73, -3) // and (sqrt(2), -2) ~ (1.41, -2). Notice that since the x-coordinates // of the endpoints cannot be accurately represented, we specify them // as the intersections of the parabola with the lines y = -3 and y = -2. // Note that the arc is clockwise oriented. Conic_arc_2 c6 = Conic_arc_2 (1, 0, 0, 0, 1, 0, // The parabola. CGAL::CLOCKWISE, Point_2 (-1.73, -3), // Approximation of the source. 0, 0, 0, 0, 1, 3, // The line: y = -3. Point_2 (1.41, -2), // Approximation of the target. 0, 0, 0, 0, 1, 2); // The line: y = -2. CGAL_assertion (c6.is_valid()); insert (arr, c6); // Insert the right half of the circle centered at (4, 2.5) whose radius // is 1/2 (therefore its squared radius is 1/4). Rat_circle_2 circ7 (Rat_point_2(4, Rational(5,2)), Rational(1,4)); Point_2 ps7 (4, 3); Point_2 pt7 (4, 2); Conic_arc_2 c7 (circ7, CGAL::CLOCKWISE, ps7, pt7); insert (arr, c7); // Print out the size of the resulting arrangement. std::cout << "The arrangement size:" << std::endl << " V = " << arr.number_of_vertices() << ", E = " << arr.number_of_edges() << ", F = " << arr.number_of_faces() << std::endl; return 0; } #endif

这段代码构建了一个形如下图的平面划分 利用CGAL的2D Arrangement，我们可以快速求解多边形的围合区域。

CGAL布尔运算的局限性

看到CGAL的特性后，我们来分析一下它的局限性。 CGAL对于直线段和圆弧的构建及表达，和我们上层应用的表达方式其实很类似，通过输入一些特征点便能构建出我们想要的线。但是对于圆锥曲线，CGAL提供的构建方式是输入圆锥曲线的一般方程参数进行构建。圆锥曲线的一般方程式为

r·x²+s·y²+t·xy+u·x+v·y+w=0

而上层应用在构建圆锥曲线时，一般会使用它的特征表达，以椭圆弧为例，我们一般只需要输入中心点、长短半轴向量、起始角度、终止角度即可，因此在构建CGAL椭圆弧时还需要求解其一般方程参数。 另外要注意的是，CGAL中的方程参数需要使用分式表达（分子分母都需要为整形），当我们求解出椭圆参数时，还需要将其转换为分式，多次的转换也增加了开发的工作量以及出错概率。