舒沈睿 張其林 滿延磊

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

引言

鋼結構加工圖(圖1)的自動生成是計算機建筑輔助設計(CAAD)的重要內(nèi)容[1]，圖紙自動生成包括投影、繪制、標注等步驟。其中，圖紙標注的布局技術是指生成標注后對標注進行空間位置的重新布局，使標注間沒有重疊干涉，圖紙整潔、美觀。標注包括尺寸標注及引出標注等，引出標注指的是零件序號、焊縫標注等帶有引線的標注。由于引出標注數(shù)量大、要素多、位置靈活，其布局問題是標注布局研究的重點與難點。

圖1 某鋼結構柱構件組三維模型及其加工圖

商業(yè)應用層面，如圖2所示，各類鋼結構設計軟件如Tekla、AdvanceSteel等均具備了自動圖紙生成功能。然而這些軟件生成的圖紙無法避免標注干涉沖突，不夠美觀，需要用戶大量手動修改甚至全部重新布局。

圖2 部分商用軟件引出標注布局干涉重疊現(xiàn)象

標注布局等平面布局問題屬于NP完全問題，難以找到可接受的多項式時間復雜度解[2]，對此國內(nèi)外已有學者開展各種研究，提出貪心法、梯度下降法等局部搜索算法與模擬退火法等全局搜索算法[3-4]。Bekos[5]提出了邊界標注布局形式，約束了標注出現(xiàn)的位置。近年來，關于圖紙標注算法的創(chuàng)新層出不窮，如Lhuillier[6]提出的基于密度的梯度下降算法，Kakoulis提出的“一對多”標注算法[7]、王福勝提出的基于邊界標注的均勻排列法[8]等。這些算法均在一定程度上解決了干涉重疊的問題。然而，經(jīng)測試驗證，上述算法依然存在以下問題亟待解決：

1)部分隨機搜索算法計算時間過長；

2)部分局部最優(yōu)算法在鋼結構加工圖中依然常見大量重疊沖突;

3)邊界標注均勻布局引線過長，不夠美觀；

4)基于密度的梯度下降法等算法適用曲線或多折線引線，不符合加工圖繪制規(guī)范。

針對以上問題，本文提出一種基于邊界標注形式，采用結合聚類與二分圖帶權最優(yōu)匹配的鋼結構加工圖引出標注布局算法，力求在避免標注干涉的同時兼顧運算性能與布局整潔美觀，具備較高的實用性。

1 問題模型與求解思路

1.1 問題模型

鋼結構加工圖引出標注的空間占位情況可采用如下基本要素確定(圖3)：

圖3 引出標注空間占位基本要素

1)引出點，即引線指于被標注體上的點；

2)引線終點，即放置標注內(nèi)容位置的點；

3)標注內(nèi)容，其空間范圍可用該標注內(nèi)容所覆蓋的AABB包圍盒表示；

引出點可設置在被標記體的重心或邊緣點。在布局問題中，引出點是已知的，需要考慮如何布置引線終點和標注內(nèi)容以避免如下三類常見干涉情況：

1)框—框干涉(圖4-a)，其數(shù)量記為X；

2)線—框干涉(圖4-b)，其數(shù)量記為Y；

3)線—線干涉(圖4-c)，其數(shù)量記為Z；

圖4 三種引出標注干涉情況

在一定的空間范圍A內(nèi)對所有引出標注Labels進行布局，就要使范圍內(nèi)標注重疊數(shù)量最小，則布局目標F可表示為：

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

(1)

1.2 求解思路分析

貪心法、梯度下降法等算法遵循就近原則依次進行搜索。當標注密集時，如圖5(a)所示，就近布置一定數(shù)量標注(黑色)后，后續(xù)的標注(灰色)難以找到合適位置。模擬退火等改進方法計算時間長，實用性不佳。

邊界標注是引出標注布局的另一形式。如圖5(b)所示，在邊界標注中，所有標注布置于某矩形邊界上，引出點位于邊界內(nèi)，引線終點位于邊界線上，標注內(nèi)容均位于邊界外。邊界標注降低了布局的靈活性，但可較好避免先前布局占位不合理導致的干涉沖突，適合用于標注較密集的加工圖。

圖5 局部最優(yōu)缺陷與邊界標注

與地形、機械零件圖不同，加工圖在柱的層交界處或梁跨交界處存在大量信息，而層間或跨中卻較為空曠，使得標注呈現(xiàn)出時而聚集、時而松散的分布特點，采用傳統(tǒng)的邊界標注不能滿足美觀要求。本文算法考慮這一問題，選擇參考并改進邊界標注布局，首先以空間聚集特征為依據(jù)，將被標注體劃分為若干聚集在一起的子集(子范圍)，隨后對每個子范圍i依次求解上述三目標。將目標F分解為三個子目標：

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

(2)

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

(3)

F3=∑F3i=∑min{Zi|F1，F(xiàn)2，Labels∈Bi}

(4)

求解目標F1i，可得子范圍的邊界Bi。

求解目標F2i，在邊界Bi上布置引線終點，使X=0。由于標注內(nèi)容與引線分別位于邊界外部和內(nèi)部，不可能產(chǎn)生線—框干涉，故Y=0，滿足目標F2i。

求解目標F3i，對引出點和引線終點進行匹配，匹配后各條引線互不交叉。

2 標注邊界獲取

2.1 子范圍劃分

首先求解F1i得到子范圍邊界。本算法采用引出點代表各個被標注體的空間位置，以點集重心的空間距離為依據(jù)，使用合成聚類法對各引出點根據(jù)空間聚集特性進行歸類以劃分子范圍。

子范圍劃分可按照如下步驟進行：

1)初始階段：每個引出點均為單獨的類；

2)重復如下操作，直到類的數(shù)量不再改變：二重遍歷各類，計算類m、n的歐氏距離Dmn，若Dmn<閾值d，則合并m、n；

經(jīng)測試，該算法可有效提取標注之間的空間聚集特性。以圖6所示的柱構件圖為例，67個引出點可被準確劃分為分別包含3、25、25、14個引出點的子范圍。

圖6 某柱構件圖子范圍劃分結果

2.2 標注邊界計算

2.2.1 初始邊界

對于某一子范圍i，采用一個剛好包圍范圍i內(nèi)引出點的AABB包圍盒Bi表示標注子范圍的初始邊界。但此時的邊界往往過小，不能容納所有標注，需要檢驗與調(diào)整。

2.2.2 邊界檢驗與調(diào)整

初始邊界需要檢驗是否滿足標注的最小容量要求。對于寬度為L，高度為H的邊界，先采用有效長度法考慮標注與原圖紙干涉的情況，即計算各零件圖塊多段線與邊界的交點，判斷交點兩端邊界是否與圖塊產(chǎn)生干涉。若有，則折減掉產(chǎn)生干涉的邊界長度，并不在此范圍布置引線終點。再通過引出點個數(shù)、標注內(nèi)容最大尺寸、標注最小容許間隙算出每條邊可容納的標注數(shù)量numH和numL。則當以下表達式為真時當前邊界滿足容量要求，停止調(diào)整； 反之則向外擴大邊界直至滿足要求：

2×(numH+numL)≥LabelNum

(5)

注：LabelNum指通過有效邊界算出的最多可布置標注個數(shù)。

對于圖7所示的構件，對柱頂、層間及柱腳四個子范圍分別計算其標注邊界，邊界計算結果如圖所示。

圖7 某柱構件圖標注子范圍及邊界

3 標注空間位置布局

3.1 引線終點布置

引線終點需要根據(jù)對應引出點的位置就近布置于邊線。布置時暫忽略引線交叉，只需預留出足夠放置最大標注內(nèi)容的空間。先按左—下—右—上逆時針順序?qū)⒁鳇c就近歸屬于相應的邊。從某一條邊開始，按照以下原則布置引線終點：

1)按照與引出點的x(上下邊)或y(左右邊)坐標值的逆時針順序布置引線終點；

2)過引出點作45°方向直線，若在此直線與邊線的交點上布置引線終點不產(chǎn)生重疊，則將引線終點布置于此(圖8-a)；

圖8 引出終點邊界布置原則

3)若(c)無法滿足空間容納要求，則嘗試反向挪動已布置標注以提供空間(圖8-b)； 若本邊已滿，則轉(zhuǎn)入下一邊布置(圖8-c)；

4)在下一條邊遞歸重復上述操作，直到引線終點全部布置完成。

3.2 處理引線交叉

布置引線終點時未考慮引線交叉，需要進行調(diào)整，即求解F3。

調(diào)整標注布置從調(diào)整引出點與引線終點的對應關系入手。首先考慮2個標注引線交叉這一最簡情況。如圖9所示，存在AC與BD(交叉)、AD與BC(不交叉)兩種匹配。由于三角形兩邊之和大于第三邊。因此有：

圖9 引線交叉的避免

AC+BD>AD+BC

可知引線不交叉時，引線長度之和最小?？赏普搉個引出點與n個引線終點對應，所得引線長度和最小時，引線互不交叉。

用圖的相關理論求解F3。對于n個引出點(S1， …，Sn)與n個引線終點(E1， ……En)，構造如圖10所示的帶權二分圖G(V，E)，該圖中引出點兩兩之間或引線終點兩兩之間互不相連，而任一引出點與引線終點均相連，邊ij的權取為點Si和點Ej的距離dij；

圖10 引出點與引線終點的二分圖

引出點與引線終點的對應關系稱為匹配。對于上述的圖G，尋找引線互不交叉的節(jié)點對應關系，相當于尋找權和Σdij最小的匹配。尋找該匹配可采用Kuhn-Munkres算法(K-M算法)。該算法參考匈牙利算法，求解帶權二分圖權和最大匹配[9-10]。由于本算法所求為和最小匹配，故將各邊權取負求解。

綜上所述，引出點與引線終點的配對可按以下步驟進行：

1)對引出點與引線終點構造上述二分圖；

2)使用K-M算法對二分圖進行匹配；

3)根據(jù)匹配后的對應關系，在各引線終點Ei處布置引出點Sj對應的標注內(nèi)容；

4 算法應用

采用C++編程，將上述圖紙布局算法應用于同濟大學3D3S Solid鋼結構深化軟件，對某鋼結構框架柱構件組(引出標注67個)進行構件加工圖引出標注布局，并選取部分已有算法對比，結果如表1和圖11所示。

表1 不同算法布局效果及執(zhí)行時間對比

圖11 各布局算法布局結果

4.1 效果評價

根據(jù)布局效果可看出，貪心法由于局部最優(yōu)缺陷，標注的干涉現(xiàn)象嚴重，基本不具備實用性。模擬退火算法為隨機搜索，執(zhí)行速度慢，且由于標注密集，數(shù)萬次迭代依然無法收斂而中止執(zhí)行，因此也難以實用。邊界排列法以整幅圖為邊界，沒有劃分子標注范圍，容易產(chǎn)生引線過長、布局散亂等問題，效果很不美觀，也需要大量修改。前文圖1所示的Tekla等商用軟件采用自動或半主動標注，也存在部分標注干涉沖突現(xiàn)象。

相比其他算法或商用軟件的布局效果，本算法布局后各引出標注在子范圍內(nèi)布局，互相無干涉重疊，而且圖紙美觀、整潔。

4.2 效率評價

本算法時間復雜度取決于聚類及K-M算法，為o(n3)，低于均勻排列法的o(n4)，高于貪心算法的o(n)。但由于本算法無需如貪心法那樣對搜索范圍內(nèi)每個可能布置進行小步長的計算迭代，故時間常數(shù)項遠小于貪心法。在鋼結構加工圖常見的問題規(guī)模下(n<100)總耗時更低。

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

5 結論

1)本文提出的圖紙引出標注布局算法采用邊界標注的形式，針對鋼結構加工圖引出標注的分布特點進行優(yōu)化，圖紙整潔美觀，標注無沖突干涉。與已有算法相比，本算法布局效果更好，圖紙更加美觀，執(zhí)行效率更高，具有更好的實用性；

2)采用合成聚類法劃分子范圍，在子范圍內(nèi)分別布局，比均勻排列布局更美觀；

3)通過構造引出點與引出終點的距離權二分圖，采用Kuhn-Munkres算法解決引線交叉問題，具有更好的布局效果及效率；

4)本文布局算法的時間復雜度為o(n3)，由于避免迭代，在鋼結構加工圖常見的問題規(guī)模下執(zhí)行時間更短。