舒沈睿 张其林 满延磊

(1.同济大学 土木工程学院，上海 200092; 2.上海同磊土木工程技术有限公司，上海 200433)

引言

钢结构加工图(图1)的自动生成是计算机建筑辅助设计(CAAD)的重要内容[1]，图纸自动生成包括投影、绘制、标注等步骤。其中，图纸标注的布局技术是指生成标注后对标注进行空间位置的重新布局，使标注间没有重叠干涉，图纸整洁、美观。标注包括尺寸标注及引出标注等，引出标注指的是零件序号、焊缝标注等带有引线的标注。由于引出标注数量大、要素多、位置灵活，其布局问题是标注布局研究的重点与难点。

图1 某钢结构柱构件组三维模型及其加工图

商业应用层面，如图2所示，各类钢结构设计软件如Tekla、AdvanceSteel等均具备了自动图纸生成功能。然而这些软件生成的图纸无法避免标注干涉冲突，不够美观，需要用户大量手动修改甚至全部重新布局。

图2 部分商用软件引出标注布局干涉重叠现象

标注布局等平面布局问题属于NP完全问题，难以找到可接受的多项式时间复杂度解[2]，对此国内外已有学者开展各种研究，提出贪心法、梯度下降法等局部搜索算法与模拟退火法等全局搜索算法[3-4]。Bekos[5]提出了边界标注布局形式，约束了标注出现的位置。近年来，关于图纸标注算法的创新层出不穷，如Lhuillier[6]提出的基于密度的梯度下降算法，Kakoulis提出的“一对多”标注算法[7]、王福胜提出的基于边界标注的均匀排列法[8]等。这些算法均在一定程度上解决了干涉重叠的问题。然而，经测试验证，上述算法依然存在以下问题亟待解决：

1)部分随机搜索算法计算时间过长；

2)部分局部最优算法在钢结构加工图中依然常见大量重叠冲突;

3)边界标注均匀布局引线过长，不够美观；

4)基于密度的梯度下降法等算法适用曲线或多折线引线，不符合加工图绘制规范。

针对以上问题，本文提出一种基于边界标注形式，采用结合聚类与二分图带权最优匹配的钢结构加工图引出标注布局算法，力求在避免标注干涉的同时兼顾运算性能与布局整洁美观，具备较高的实用性。

1 问题模型与求解思路

1.1 问题模型

钢结构加工图引出标注的空间占位情况可采用如下基本要素确定(图3)：

图3 引出标注空间占位基本要素

1)引出点，即引线指于被标注体上的点；

2)引线终点，即放置标注内容位置的点；

3)标注内容，其空间范围可用该标注内容所覆盖的AABB包围盒表示；

引出点可设置在被标记体的重心或边缘点。在布局问题中，引出点是已知的，需要考虑如何布置引线终点和标注内容以避免如下三类常见干涉情况：

1)框—框干涉(图4-a)，其数量记为X；

2)线—框干涉(图4-b)，其数量记为Y；

3)线—线干涉(图4-c)，其数量记为Z；

图4 三种引出标注干涉情况

在一定的空间范围A内对所有引出标注Labels进行布局，就要使范围内标注重叠数量最小，则布局目标F可表示为：

F=min{X+Y+Z|Labels∈A}

(1)

1.2 求解思路分析

贪心法、梯度下降法等算法遵循就近原则依次进行搜索。当标注密集时，如图5(a)所示，就近布置一定数量标注(黑色)后，后续的标注(灰色)难以找到合适位置。模拟退火等改进方法计算时间长，实用性不佳。

边界标注是引出标注布局的另一形式。如图5(b)所示，在边界标注中，所有标注布置于某矩形边界上，引出点位于边界内，引线终点位于边界线上，标注内容均位于边界外。边界标注降低了布局的灵活性，但可较好避免先前布局占位不合理导致的干涉冲突，适合用于标注较密集的加工图。

图5 局部最优缺陷与边界标注

与地形、机械零件图不同，加工图在柱的层交界处或梁跨交界处存在大量信息，而层间或跨中却较为空旷，使得标注呈现出时而聚集、时而松散的分布特点，采用传统的边界标注不能满足美观要求。本文算法考虑这一问题，选择参考并改进边界标注布局，首先以空间聚集特征为依据，将被标注体划分为若干聚集在一起的子集(子范围)，随后对每个子范围i依次求解上述三目标。将目标F分解为三个子目标：

F1={B1，B2， …|Bi∈A}

(2)

F2=∑F2i= ∑min{Xi+Yi|F1，Labels∈Bi}

(3)

F3=∑F3i=∑min{Zi|F1，F2，Labels∈Bi}

(4)

求解目标F1i，可得子范围的边界Bi。

求解目标F2i，在边界Bi上布置引线终点，使X=0。由于标注内容与引线分别位于边界外部和内部，不可能产生线—框干涉，故Y=0，满足目标F2i。

求解目标F3i，对引出点和引线终点进行匹配，匹配后各条引线互不交叉。

2 标注边界获取

2.1 子范围划分

首先求解F1i得到子范围边界。本算法采用引出点代表各个被标注体的空间位置，以点集重心的空间距离为依据，使用合成聚类法对各引出点根据空间聚集特性进行归类以划分子范围。

子范围划分可按照如下步骤进行：

1)初始阶段：每个引出点均为单独的类；

2)重复如下操作，直到类的数量不再改变：二重遍历各类，计算类m、n的欧氏距离Dmn，若Dmn<阈值d，则合并m、n；

经测试，该算法可有效提取标注之间的空间聚集特性。以图6所示的柱构件图为例，67个引出点可被准确划分为分别包含3、25、25、14个引出点的子范围。

图6 某柱构件图子范围划分结果

2.2 标注边界计算

2.2.1 初始边界

对于某一子范围i，采用一个刚好包围范围i内引出点的AABB包围盒Bi表示标注子范围的初始边界。但此时的边界往往过小，不能容纳所有标注，需要检验与调整。

2.2.2 边界检验与调整

初始边界需要检验是否满足标注的最小容量要求。对于宽度为L，高度为H的边界，先采用有效长度法考虑标注与原图纸干涉的情况，即计算各零件图块多段线与边界的交点，判断交点两端边界是否与图块产生干涉。若有，则折减掉产生干涉的边界长度，并不在此范围布置引线终点。再通过引出点个数、标注内容最大尺寸、标注最小容许间隙算出每条边可容纳的标注数量numH和numL。则当以下表达式为真时当前边界满足容量要求，停止调整； 反之则向外扩大边界直至满足要求：

2×(numH+numL)≥LabelNum

(5)

注：LabelNum指通过有效边界算出的最多可布置标注个数。

对于图7所示的构件，对柱顶、层间及柱脚四个子范围分别计算其标注边界，边界计算结果如图所示。

图7 某柱构件图标注子范围及边界

3 标注空间位置布局

3.1 引线终点布置

引线终点需要根据对应引出点的位置就近布置于边线。布置时暂忽略引线交叉，只需预留出足够放置最大标注内容的空间。先按左—下—右—上逆时针顺序将引出点就近归属于相应的边。从某一条边开始，按照以下原则布置引线终点：

1)按照与引出点的x(上下边)或y(左右边)坐标值的逆时针顺序布置引线终点；

2)过引出点作45°方向直线，若在此直线与边线的交点上布置引线终点不产生重叠，则将引线终点布置于此(图8-a)；

图8 引出终点边界布置原则

3)若(c)无法满足空间容纳要求，则尝试反向挪动已布置标注以提供空间(图8-b)； 若本边已满，则转入下一边布置(图8-c)；

4)在下一条边递归重复上述操作，直到引线终点全部布置完成。

3.2 处理引线交叉

布置引线终点时未考虑引线交叉，需要进行调整，即求解F3。

调整标注布置从调整引出点与引线终点的对应关系入手。首先考虑2个标注引线交叉这一最简情况。如图9所示，存在AC与BD(交叉)、AD与BC(不交叉)两种匹配。由于三角形两边之和大于第三边。因此有：

图9 引线交叉的避免

AC+BD>AD+BC

可知引线不交叉时，引线长度之和最小。可推论n个引出点与n个引线终点对应，所得引线长度和最小时，引线互不交叉。

用图的相关理论求解F3。对于n个引出点(S1， …，Sn)与n个引线终点(E1， ……En)，构造如图10所示的带权二分图G(V，E)，该图中引出点两两之间或引线终点两两之间互不相连，而任一引出点与引线终点均相连，边ij的权取为点Si和点Ej的距离dij；

图10 引出点与引线终点的二分图

引出点与引线终点的对应关系称为匹配。对于上述的图G，寻找引线互不交叉的节点对应关系，相当于寻找权和Σdij最小的匹配。寻找该匹配可采用Kuhn-Munkres算法(K-M算法)。该算法参考匈牙利算法，求解带权二分图权和最大匹配[9-10]。由于本算法所求为和最小匹配，故将各边权取负求解。

综上所述，引出点与引线终点的配对可按以下步骤进行：

1)对引出点与引线终点构造上述二分图；

2)使用K-M算法对二分图进行匹配；

3)根据匹配后的对应关系，在各引线终点Ei处布置引出点Sj对应的标注内容；

4 算法应用

采用C++编程，将上述图纸布局算法应用于同济大学3D3S Solid钢结构深化软件，对某钢结构框架柱构件组(引出标注67个)进行构件加工图引出标注布局，并选取部分已有算法对比，结果如表1和图11所示。

表1 不同算法布局效果及执行时间对比

图11 各布局算法布局结果

4.1 效果评价

根据布局效果可看出，贪心法由于局部最优缺陷，标注的干涉现象严重，基本不具备实用性。模拟退火算法为随机搜索，执行速度慢，且由于标注密集，数万次迭代依然无法收敛而中止执行，因此也难以实用。边界排列法以整幅图为边界，没有划分子标注范围，容易产生引线过长、布局散乱等问题，效果很不美观，也需要大量修改。前文图1所示的Tekla等商用软件采用自动或半主动标注，也存在部分标注干涉冲突现象。

相比其他算法或商用软件的布局效果，本算法布局后各引出标注在子范围内布局，互相无干涉重叠，而且图纸美观、整洁。

4.2 效率评价

本算法时间复杂度取决于聚类及K-M算法，为o(n3)，低于均匀排列法的o(n4)，高于贪心算法的o(n)。但由于本算法无需如贪心法那样对搜索范围内每个可能布置进行小步长的计算迭代，故时间常数项远小于贪心法。在钢结构加工图常见的问题规模下(n<100)总耗时更低。

综上所述，与已有算法相比，本文提出的布局算法效果更好，效率更高。

5 结论

1)本文提出的图纸引出标注布局算法采用边界标注的形式，针对钢结构加工图引出标注的分布特点进行优化，图纸整洁美观，标注无冲突干涉。与已有算法相比，本算法布局效果更好，图纸更加美观，执行效率更高，具有更好的实用性；

2)采用合成聚类法划分子范围，在子范围内分别布局，比均匀排列布局更美观；

3)通过构造引出点与引出终点的距离权二分图，采用Kuhn-Munkres算法解决引线交叉问题，具有更好的布局效果及效率；

4)本文布局算法的时间复杂度为o(n3)，由于避免迭代，在钢结构加工图常见的问题规模下执行时间更短。