原文链接：解读布尔运算库 VectorBoolean

VectorBoolean 是 Cocoa 上的一个贝塞尔曲线布尔运算库，布尔运算是矢量绘图软件最基本的功能之一，连占据 UI 设计半壁江山的 Sketch 也是使用这个库做布尔运算的。

类说明

FBBezierGraph

这个类作为 NSBezierPath 的替代类，这个类与 NSBezierPath 可以方便的互相转换。

布尔运算时会将 NSBezierPath 转成这个类，做完布尔操作后再转回来。

在- (id) initWithBezierPath:(NSBezierPath *)path方法中可以看到从 NSBezierPath 转换成 FBBezierGraph 的过程。

内部成员 _contours 为一个 NSMutableArray ，存储的是 FBBezierContour

FBBezierContour

FBBezierContour 相当于 NSBezierPath 的一个 subpath，一个 NSBezierPath 就是一条完整的线段。可以参考我写的NSBezierPath小记

内部成员 _edges 为一个 NSMutableArray ，存储的是 FBBezierCurve

FBBezierCurve

FBBezierCurve 与 NSBezierPath 的 Element 有点类似，但是不一样，Element 可以是一个点，但是 FBBezierCurve 代表的是曲线的一个线段。

内部成员 data 为一个 FBBezierCurveData，是一个结构体，存储的为贝塞尔曲线的信息（开始点、两个控制点、结束点）。就算是直线，FBBezierCurveData 也把他当成控制点在同一直线上的曲线处理。

上3个类总结

• FBBezierGraph 包含若干个 FBBezierContour，FBBezierGraph 就相当于多个闭合图形的集合
• FBBezierContour 包含若干个 FBBezierCurve，相当于一个闭合图（连续的线段构成的）
• FBBezierCurve 相当于一个线段 (曲线)

FBBezierIntersection

FBBezierIntersection 记录两个 Curve 相交的信息。

location 是相交的点

_parameter1 成员的意思是相交点在线段1上的位置，比如中点，则 parameter1 为0.5；如果为开始点则 parameter1 为 0

_parameter1 成员的意思是相交点线段2上的位置

对应还存有 _curve1 和 _curve2

FBBezierIntersectRange

FBBezierIntersectRange 是记录两个 Curve 覆盖相交的信息。

_parameterRange1 记录的是第一个 Curve 相交部分的范围，比如0-0.5，就是第一个 Curve 开头到一半的位置都有相交

_parameterRange2 记录的是第二个

两个线段有一段是重叠，相交的不是点而是线段重叠，用FBBezierIntersectRange表示

FBEdgeCrossing

FBEdgeCrossing 代表相交点，在判断得到相交点后，存储记录到 FBBezierCurve 中

主要由 FBBezierIntersection 构成，但是还持有另一个线段的 FBEdgeCrossing 的引用。存在 counterpart 成员中

FBEdgeOverlap

FBEdgeOverlap 代表 Curve 的覆盖相交，即最小单位线段的覆盖相交，主要由 FBBezierIntersectRange 构成。

成员：

FBBezierCurve *_edge1;
FBBezierCurve *_edge2;
FBBezierIntersectRange *_range;

FBEdgeOverlapRun

FBEdgeOverlapRun 的唯一一个成员为 NSMutableArray *_overlaps;，存储的是 FBEdgeOverlap

每次往 FBEdgeOverlapRun 加 FBEdgeOverlap 时，FBEdgeOverlapRun 都检查新加入的是否与 _overlaps 的第一个或者最后一个为连续的，不连续的话则不添加并返回添加失败。

所以 FBEdgeOverlapRun 存储的是连续覆盖相交的 FBEdge 线段

- (BOOL) isComplete指的是是否形成闭合，即 _overlaps 中最后一个与第一个 fits

FBContourOverlap

FBContourOverlap 代表 Contour 的覆盖相交，在判断得到覆盖相交的线段的范围后，存储记录到 FBBezierContour 的 _overlaps 中

FBContourOverlap 的唯一一个成员为 NSMutableArray *_runs;，存储的是 FBEdgeOverlapRun

关于 Overlap 总结

FBEdgeOverlap、FBEdgeOverlapRun、FBContourOverlap的概念容易混淆，这里说明一下。

如果图3个正方形，红色、黑色、蓝色，以黑色为主

上面的1、2、3、4、5都分别代表一个 overlap 线段，是 FBEdgeOverlap 类型

红色与黑色 overlap 的线段为1、2

蓝色与黑色 overlap 的线段为3、4、5

• FBEdgeOverlap 代表 overlap 的线段，这里的1、2、3、4、5都是 overlap 线段
• FBEdgeOverlapRun 代表连续的 FBEdgeOverlap ，这里有3个，分别是：[1]、[2]、[3、4、5]
• FBContourOverlap 代表某一 Contour 的所有 overlaprun，这里有两个，分别是 [ [1]、[2] ] 和 [ [3、4、5] ]

FBContourOverlap 存储在 FBBezierContour 中

关键流程

布尔运算算法的基本流程为：

1. 拆解曲线，判断两个图形的相交点。
2. 标记相交点，根据布尔运算的类型进行线段筛选。
3. 遍历所有线段，组合需要的线段，组成新的图形

判断相交

在 FBBezierGraph 中的 - (void) insertCrossingsWithBezierGraph:(FBBezierGraph *)other

遍历两个 FBBezierGraph 的所有的 FBBezierCurve，判断 FBBezierCurve 之间的相交，并把相交的信息写入 FBBezierCurve

FBBezierCurve 中的 - (void) intersectionsWithBezierCurve:(FBBezierCurve *)curve overlapRange:(FBBezierIntersectRange **)intersectRange withBlock:(FBCurveIntersectionBlock)block

判断链两个 FBBezierCurve 的相交

最关键的方法在 FBBezierCurve 的

static void FBBezierCurveDataIntersectionsWithBezierCurve(FBBezierCurveData me, FBBezierCurveData curve, FBRange *usRange, FBRange *themRange, FBBezierCurve *originalUs, FBBezierCurve *originalThem, FBBezierIntersectRange **intersectRange, NSUInteger depth, FBCurveIntersectionBlock outputBlock, BOOL *stop)

代码非常多，就没看了

判断相交的结果可以通过 FBCurveIntersectionBlock 得到

判断相交例子

蓝色矩形大小为300x50，红色为100x50

以蓝色矩形左下角为原点，执行蓝色矩形 different 红色矩形

相交点判断，log 打印出来的点，的顺序为1，2，3，4

• FBBezierIntersection1: location = (150, 0), param1 = 0.5, param2 = 0.0,

  param1为 点2 -> 点1 方向，蓝色箭头线段的位置

  param2位 点1 -> 点2 方向，红色箭头线段的位置

• FBBezierIntersection2:location = (50, 0), param1 = 0.166667, param2 = 1

  param1为 点2 -> 点1 方向，蓝色箭头线段的位置，0.166667x300 = 50，0.166667为相交点在这个线段上的位置

  param2位 点1 -> 点2 方向，红色箭头线段的位置

• FBBezierIntersection4:location = (50, 50), param1 = 0.833333, param2 = 0

  param1为 点3 -> 点4 方向，蓝色箭头线段的位置，0.833333为相交点在这个线段上的位置

  param2位 点1 -> 点2 方向，红色箭头线段的位置

标记线段

拿作者博客的例子来看，找到3个相交的线段，1、2、3，这三个线段标记为 inside

以矩形为主图形

如果做 union 的操作，那么就是【蓝色矩形 outside 的线段】+【红色圆形 outside 的线段】

如果做 difference 的操作，那么就是 【蓝色矩形 outside 的线段】+【红色圆形 inside 的线段】

只要能正确将线段进行标记、分割，就可以很容易进行布尔操作。

以 difference 操作为例，代码位置为：

- (FBBezierGraph *) differenceWithBezierGraph:(FBBezierGraph *)graph中调用：

[self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:NO];//标记矩形 outside 的线段
[graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:YES];//标记圆形 inside 的线段

实际上，代码进行标记的不是线段，而是交点，Bezier 的线段是有方向的，我们假设正方形和圆形都是顺时针方向的

[self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:NO];的意思是标记矩形，标记不在相交区域的线段，出相交区域的交点为 entry，进相交区域的交点为 exit。

对于矩形来说，交点1为 exit，交点2为 entry

[graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:YES]的意思是标记圆形，标记在相交区域内的线段，进相交区域的交点为 entry，出相交区域的交点为 exit

对于圆形来说，交点1为 entry，交点2为 exit

遍历线段

接下来遍历线段，完成布尔运算

方法为- (FBBezierGraph *) bezierGraphFromIntersections

这里做的操作简化来说就是：

从第一个 entry 的相交点开始，按照 next 的顺序遍历线段，每一段都加到新建的 FBBezierContour 中，直到遇到下一个相交点，切换到 counterpart 相交点上，如果为 entry 则继续添加每一个线段直到下一个相交点，然后又切到 counterpart 相交点，再继续。

上面逻辑，如果遇到的不是 entry 点，则反向操作，按照 previous 的顺序遍历线段，加到新建的 FBBezierContour 中，，，略

处理无相交的情况

略

参考

VectorBoolean作者的博客：

How to implement boolean operations on bezier paths