鋼結(jié)構(gòu)加工圖引出標(biāo)注布局算法研究

舒沈睿 張其林 滿延磊

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

引言

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

圖1 某鋼結(jié)構(gòu)柱構(gòu)件組三維模型及其加工圖

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

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

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

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

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

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

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

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

1 問題模型與求解思路

1.1 問題模型

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

圖3 引出標(biāo)注空間占位基本要素

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

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

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

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

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

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

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

圖4 三種引出標(biāo)注干涉情況

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

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

(1)

1.2 求解思路分析

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

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

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

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

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)

求解目標(biāo)F1i，可得子范圍的邊界Bi。

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

求解目標(biāo)F3i，對引出點和引線終點進(jìn)行匹配，匹配后各條引線互不交叉。

2 標(biāo)注邊界獲取

2.1 子范圍劃分

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

子范圍劃分可按照如下步驟進(jìn)行：

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

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

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

圖6 某柱構(gòu)件圖子范圍劃分結(jié)果

2.2 標(biāo)注邊界計算

2.2.1 初始邊界

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

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

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

2×(numH+numL)≥LabelNum

(5)

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

對于圖7所示的構(gòu)件，對柱頂、層間及柱腳四個子范圍分別計算其標(biāo)注邊界，邊界計算結(jié)果如圖所示。

圖7 某柱構(gòu)件圖標(biāo)注子范圍及邊界

3 標(biāo)注空間位置布局

3.1 引線終點布置

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

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

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

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

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

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

3.2 處理引線交叉

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

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

圖9 引線交叉的避免

AC+BD>AD+BC

可知引線不交叉時，引線長度之和最小。可推論n個引出點與n個引線終點對應(yīng)，所得引線長度和最小時，引線互不交叉。

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

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

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

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

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

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

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

4 算法應(yīng)用

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

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

圖11 各布局算法布局結(jié)果

4.1 效果評價

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

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

4.2 效率評價

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

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

5 結(jié)論

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

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

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

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