Boost 矩形布尔运算

阅读原文时间：2023年07月08日阅读：3

本文主要介绍boost库中矩形布尔运算的思路和代码解析。在此感谢Intel对开源事业的贡献。

图形的插入

所有的操作的第一步都是进行图形的插入，我们需要声明定义好我们要使用的图形类型，以矩形为例，方式为：

rectangle_data(T xl, T yl, T xh, T yh)

实例如下：

ps1.insert(rectangle_data<int>(3,5,7,9));
ps2.insert(rectangle_data<int>(2,4,6,8));

xl, yl, xh, yh分别为x最小值，y最小值，x最大值，y最大值。分别为矩形的右下角左边和左上角坐标。

顶点与多边形的转化——微分

在Boost算法中，一个基本的实现逻辑是通过计算多边形的导数来代表多边形的x和y坐标点变化

在对矩形的端点进行导数计算后，从左到右扫描所有矩形的点y坐标形成的竖直区间，对于矩形，竖直区间导数值等于下端点的导数值。在代码实现上，boost并不真的求导，而只是按顺序分配，给四个顶点以1和-1的值，以加快运行速度。

从左到右扫描所有矩形的点形成的区间，累加导数值，记录为count,来判断是否应该将该区间加入结果中。

假设有n个矩形进行布尔运算，那么设立一个长度为n的数组count，count[i]代表第i个矩形。布尔运算完成之后的图形设为 Result。扫描的方式是从左到右进行扫描。

计算加入区间ivl前总体状态值before和加入ivl之后after。对于不同的布尔运算，总体状态值的计算方式也不一致。

1.对于或运算，从count[0]和count[1]任一值为1，就能计算出当前总体状态值为true。

2.对于与运算，就需要从count[0]和count[1]所有值全为1，才能计算出当前总体状态值为true。

总体状态值before或after等于true，那么代表位于Result内部。

等于false自然代表位于Result外部。

显然对于一个区间，加入他前后如果都在Result内部，或者都在Result外部，这个区间就不是Result的边。反之，如果由内到外或者由外到内，这个区间就是Result的边，应该加入结果中。

首先声明矩形，方式为

rectangle_data(T xl, T yl, T xh, T yh)

xl, yl, xh, yh分别为x最小值，y最小值，x最大值，y最大值。

定义三个矩形集合ps1, ps2和ps_tmp。

ps1内包含一个值为(3,5,7,9)的矩形, ps2包含一个值为(2,4,6,8)的矩形，ps_tmp保存结果。

做布尔与运算

ps_tmp=ps1*ps2

通过重载操作符*的形式，进入布尔运算流程。

polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd>
(
    lvalue,
    rvalue,
    polygon_90_set_traits<geometry_type_1>::orient(lvalue),
    boolean_op::BinaryAnd()
);

lvalue即ps1， rvalue即ps2。

初始化

数据类型介绍：

interval_data：区间数据，用于扫描线。
polygon中端点数据结构形如：

(first,(second.first,second.second))

first存储端点的x值，second.first存储端点的y值，second.second存储端点的导数值。

有几个变量需要得到初始化：

orient:方向。每个 polygon_90_set_data 都有，默认为1.
data_:保存着端点的数据。

data_的初始化在insert时就已经完成，首先默认如下图所示。标记各个顶点,标记名为corner_，值为0,1,2,3（矩形条件下）。按照0，1，2，3的顺序依次标记各个点的导数值为1,-1,-1,1。需要注意的是在有hole的情况下，导数值会发生变化。具体执行函数位于iterator_geometry_to_set.hpp 52行 inline reference operator*()处。

compute_90_set_value

计算首先在名为 compute_90_set_value 的结构体中进行。将ps1,ps2分别作为lvalue_和rvalue_传入。

假如ps1和ps2的orient（方向）相同，那么：

对ps1和ps2均进行端点sort。先按x坐标升序排序，若x坐标相同，再按y坐标升序排序。如下图所示,ps1排序后顶点顺序为(3,5),(3,9),(7,5),(7,9)。

调用

output_.applyBooleanBinaryOp
(
    lvalue_.begin(), lvalue_.end(),
    rvalue_.begin(), rvalue_.end(),
    boolean_op::BinaryCount<op_type>()
);

进入applyBooleanBinaryOp函数。

applyBooleanBinaryOp

变量介绍：

itr1：迭代器。用于ps1遍历。
itr2：迭代器。用于ps2遍历。
output：布尔运算得到的结果。
container: vector类型。保存着每次计算得到的结果。其中元素类型为

pair<interval_data<Unit>, int>
curCoord：记录当前x值。
curPosition：记录当前y值。
curCount：curCount[0]记录当前区间的属于ps1的端点导数值，curCount[1]记录当前区间的属于ps2的端点导数值。
prevCoord：前一个被处理的点的x值。
prevPosition：前一个被处理的点的y值。
count：累加所有已处理的区间的下端点的导数值。

遍历ps1和ps2中的所有点,当他们都未被遍历完时：

选择itr1和itr2之中x值更小的点。使curCoord为其x值，curPosition为对应的y值。curCoount=defaultCount。如果选择itr1，curCount[0]加上itr1的导数值。否则，curCount[1]加上itr2的count值。
如果prevCoord!=curCoord。即两个端点的x值不一致，不能形成一条竖直方向的扫描线区间。不再进行后续处理，直接进行下次循环。调用advanceScan函数使scanData迭代器回到scanData.begin()，并直接更新prevCoord,prevPosition,count。如下图所示，当前一点为(2,8)，现端点为(3,5)时，二者不在同一竖直线上，不再进行后续处理。
否则，继续处理。声明并定义变量ivl。ivl的下界为prevPosition,上界为curPosition。
清理container为空。
调用boolean.processInterval(container, ivl, count)进行区间的处理和计算,将结果加入container中。
遍历container中所有interval元素，将prevCoord和元素的上界high联合成为新端点P1并加入output中。另外，当将prevCoord和元素的下界low联合成新端点P2,但若P2与output中最后一个端点A重合（如下图所示，点A与low重合），则将点A移除(为了合并区间),否则加入P2到output。

遍历结束，返回output，计算完毕。如下图所示，(3,5),(3,8),(6,5),(6,8)四个点就是布尔运算后的结果中所保存的点。

processInterval

processInterval函数用于计算结果。

变量介绍：

ivl：即输入变量interval，下界和上界分别为low和high。
outputContainer：一个vector向量，用于保存结果interval。即输出。
deltaCount：也就是count。累加所有已处理的区间的下端点的导数值。

具体来说：

对比当前interval与scacnData。如果当前interval覆盖到了scanData没有覆盖到的区域，根据当前interval扩展scanData。例如第一次进入processInterval时，将区间[4,8]传入。此时scanData 中没有数据，扩展scanData 。
在scanData中，由输入的ivl的下界low开始，到ivl的high结束。生成新interval，将新生成的interval输入到evaluateInterval进行判断，判断是否加入outputContainer中。
在evaluateInterval函数中，通过

以 ps1和ps2为例，流程如下

将区间[4,8]传入processInterval 。此时scanData 中没有数据，扩展scanData 。

判断[4,8]是否需要加入outputContainer中，判断结果为不需要。
将区间[5,9]传入。传入之前scanData为[4,8]。扩展，扩展后为[4,5,8,9]。

判断[5,8],[8,9]是否需要加入outputContainer中。[5,8]加入。
将区间[4,8]传入。判断[4,5],[5,8]。[5,8]加入。
将区间[5,9]传入。判断[5,9]。不加入。

判断区间

判断区间在evaluateInterval中进行。

变量介绍：

1.ivl：区间interval。

2.beforeCount:代表scanData尚未加入ivl时的count值。保存了所有图形扫到的导数值之和。

3.afterCount:代表scanData加入ivl后的count值。保存了所有图形扫到的导数值之和。

假设有n个矩形进行布尔运算，那么设立一个长度为n的数组count，count[i]代表第i个矩形。布尔运算完成之后的图形设为 Result.

从左到右进行扫描，count值的变化情况如下:

0(尚未扫到该矩形) -----1(当前正在该矩形内部)-----0(离开该矩形)。

判断代码：

bool before = (int)beforeCount > 0;
bool after = (int)afterCount > 0;
int value = (!before & after) - (before & !after);

通过重载的方式，对于布尔运算进行不同的操作。

before和after即总体状态值，为true则代表在结果图形Result之内，否则代表在Result之外。

对于或运算的总体状态值，从count[0]和count[1]任一值为1，考虑到或运算需要将所有图形加入结果中，就代表当前总体状态值为true。

而对于与运算，就需要从count[0]和count[1]所有值全为1，才能判定位于结果图形之内，总体状态值为true。

当进行与运算时，代码如下:

bool before = (int)beforeCount > 0;

调用

inline operator int() const { return T()(counts_[0], counts_[1]); }

再调用

  class BinaryAnd
  {
  public:
    inline BinaryAnd() {}
    inline bool operator()(int a, int b) { return (a > 0) & (b > 0); }
  };

推广到其他布尔运算，则是:

  class BinaryOr
  {
   ... (int a, int b) { return (a > 0) | (b > 0); }
  };
  class BinaryNot
  {
    ...(int a, int b) { return (a > 0) & !(b > 0); }
  };
  class BinaryXor
  {
    ...(int a, int b) { return (a > 0) ^ (b > 0); }
  };

通过模板和重载的方式实现对于不同的布尔运算类型实现不同的before和after取值方法。

计算完before和after的值后，计算value值。value值为1即为入边，为-1即为出边，这两种情况都需要加入outputContainer中。其他情况则不需要。

例如当第一次扫到(2,4),(2,8)边时，判断interavl[4,8]：