二维轮廓布尔运算干涉标志算法研究

曹文杰， 胡德计

（1. 河北工业大学材料学院，天津 300130；2. 天津工程师范学院机械系，天津 300222）

1 二维布尔运算与干涉标志法

二维轮廓的布尔运算是计算机图形学的基本算法之一，它被广泛的应用于二维图形的几何造型中。由于一些复杂空间几何造型问题可以转化为二维轮廓的布尔运算来解决，因此二维布尔运算算法研究是计算图形学的一个重要问题[1]。

二维布尔运算就是两个或多个平面图形作交、并、差、覆盖和剪取等运算操作。目前人们在这方面已进行了大量有益的探索，并且有多种算法[2-4]。这些算法虽然各有特点，但是存在诸如线段的属性规定较复杂、运算过程较繁复、对于不同的布尔运算集需要进行不同的运算过程、算法效率不高、算法实现的一致性不好等问题。

干涉标志法[5]最早用于型腔轮廓的等距轮廓生成算法，是型腔加工刀具轨迹生成的基本算法之一，干涉标志法的详细算法实现参见文献[6]的介绍。干涉标志法的基本思想是将轮廓以轮廓边界分为材质区域（如图1 中阴影区域）和非材质区域（如图1 中空白区域），当某段外部轮廓进入材质区域中，则该轮廓段发生干涉，这时将其干涉标志赋值为1；如某段外部轮廓离开材质区域中，则该段轮廓段没有发生干涉，这时将其干涉标志赋值为0。如图1 所示。

图1 干涉标志示意图

虽然干涉标志法最初是应用于型腔轮廓的等距轮廓生成的算法，通过研究发现其算法原理和思路也可以运用于二维布尔运算中。从而衍生出一个实现二维布尔运算的新算法。算法的基本思路是：先计算所有参与布尔运算的轮廓段的干涉标志，注意计算干涉标志时在相交点要把轮廓段打断。然后在计算后的轮廓段中根据具体的布尔运算操作的要求按规则挑选具有不同干涉标志的轮廓段，从而可以得到相应的布尔运算结果集。

2 二维图形轮廓表达

零件表面的轮廓段一般由直线、圆弧和自由曲线等构成。为简化处理过程，可以认为零件的整体轮廓均是由直线和圆弧构成的。其中，对于自由曲线可以将其离散为一系列直线段，根据自由曲线轮廓段的表面粗糙度要求，采用有理B 样条插值算法确定该轮廓段内的插值点。这样便可以建立整体轮廓的统一描述。经过这样处理后，可以避免轮廓偏移过程中对自由曲线进行单独处理时，求自由曲线的偏移过程中其起始点法矢难以确定以及自由曲线的偏移轮廓与邻近轮廓段的偏移轮廓间的连接问题。在整个偏移算法中只需要处理直线和圆弧的偏移，便可以得到整段轮廓的偏移轮廓。简化了算法的实现难度，提高了可靠性。

轮廓的边界可由一系列有向的轮廓边界组 成[5]（见图2）。如果把构成轮廓表面的各轮廓段统一称为节点(knot)，那么整条轮廓便是由多个首尾相连接的节点所组成。每一节点内含有一个描述边界性质的几何点点集。直线是一个包含起点和终点两个几何点的节点；圆弧是一个包含起点、终点和圆心3 个几何点的节点；而自由曲线则是一个包含多个几何点（型值点）点集的节点。

图2 型腔轮廓的表达

对于轮廓边界可以用集合表示如下：

KnotList = { Knot1, Knot2, …, Knotn}

其中：Knoti(1) = Knoti+1(0) i = 1, 2, …, n-1.

在程序实现上，整个型腔轮廓可以用单向链表来表达。

采用节点的描述方法，可以建立各轮廓段对外的统一接口。将各节点的指针压入单向链表结构中，便可以得到用于描述整条轮廓的边界链，边界链经离散处理后便可形成一条只由直线和圆弧构成的偏移边界链来进行操作。

3 布尔运算算法

基于以上的轮廓表达方式，二维布尔运算可以通过对各段相交轮廓设立干涉标志来实现。结合一个具体的实例介绍其算法实现，在此主要介绍二维图形的并运算。规定沿着几何轮廓逆时针走向定义节点并且材质在左手边。如图3 所示，左边为A 轮廓(A1-A7)，右边为B 轮廓(B1-B4)。

（1） 分别求出两条链中每一条边的交点P1, P2, …, P6。

（2） 在交点处，将两条链的边打断，并将打断后形成的新边插入轮廓链中。如图中P6A3， A3P5, P5A4 等均为形成的新边。

（3） 分别遍历两条轮廓链，为每一条边设立干涉标志：对于A 链，从A1A2 开始设其干涉标志为0，如果链中的某一条边进入到另一条链的材质区内（例如A2A3），则该条边进入材质区内的部分干涉标志加1（例如P6A3 为1）；对于离开另一条链的材质区内的部分，其干涉标志减1（例如P5A4 被设为0）；每一条边的起点的干涉标志等于上一条边的干涉标志，例如A2P6 为0, A3P5 为1，A4P4 为1 等等。

图3 平面图形的布尔运算

（4） 在两条链中分别删除干涉标志为1 的轮廓段，即干涉段。重新链接两条链中干涉标志为0 的轮廓段，即未干涉段。这样可以得到c、 d、 e 三条新链，如图3 所示。所形成的新链即为两条链A 和B 作布尔并运算所得到的新链。

通过以上并运算的算法过程可以看出，在分别计算完轮廓A、B 的干涉标志后，在形成新环时，采用不同规则挑选具有不同干涉标志的边即可得到不同的布尔运算结果集。其挑选规则如下：

1） 并运算：分别提取初始轮廓A、B 的干涉标志为0 的轮廓段，形成新的并运算轮廓，如图4(a)所示；

2） 交运算：分别提取初始轮廓A、B 的干涉标志为1 的轮廓段，形成新的交运算轮廓，如图4(b)所示；

3） 差运算(A–B)：分别提取初始轮廓A 中干涉标志为0 的轮廓段和B 中干涉标志为1 的轮廓段，形成新的差运算轮廓，如图4(c)所示；

4） 差运算(B–A)：分别提取初始轮廓A 中干涉标志为1 的轮廓段和B 中干涉标志为0 的轮廓段，形成新的差运算轮廓。如图4(d)所示。

图4 干涉标志与布尔运算

4 结 论

基于干涉标志法的二维布尔运算首先计算二维轮廓段的干涉标志，然后根据具体布尔运算操作，在计算后的轮廓中根据挑选规则挑选具有不同干涉标志的轮廓段构成新链，从而得到布尔运算结果集。采用干涉标志法可以简化二维布尔运算的计算过程。根据干涉标志值采用不同的轮廓段拾取规则，经过一次计算就可以得到所有的二维布尔运算集。该算法具有轮廓表达清晰，算法实现简单，一致性好的特点。目前该算法已在计算机上实现，并运用于数控车削和型腔铣削加工的等距轮廓生成算法中，取得了良好效果。

[1] 梅树立, 张彦娥, 等. 计算机图形学中二维布尔运 算的稳定性分析[J]. 中国农业大学学报, 2001, 6(4)： 81-84.

[2] 谢步瀛, 张 岩. 用分段法与链表法的二维布尔运算算法[J]. 工程图学学报, 2003, 24(2)： 78-84.

[3] 郑家骧, 方 向, 等. 刀位轨迹的干涉标志量的改进算法[J]. 机械制造, 1999, (1)： 17-19.

[4] 武运兴. 基于边界识别的多边形的布尔运算[J]. 计算机辅助设计与图形学学报, 1994, 6(4)： 260-265.

[5] Held M, Lukacs G, Andor L. Pocket machining based on contour —— parallel tool generated by means of proximity maps [J]. Computer-Aided Design, 1994, 26(3)： 189-203.

[6] ALLAN HANSEN, FARHD ARBAB. An algorithm for generating Nc tool paths for arbitrarily shaped pockets with islands [J]. ACM Transaction on Graphics, 1992, 11(2)： 152-182.