Dijkstra算法在BIM審查中的應(yīng)用

文｜北京構(gòu)力科技有限公司 魏重潔 王委 王嘉 何啟明；中交天津港灣工程研究院有限公司 宋博文

0 引言

BIM 技術(shù)對于促進(jìn)建筑全生命周期的信息化具有重要的意義，目前在實(shí)際項(xiàng)目中的應(yīng)用頗為廣泛。隨著BIM 技術(shù)的普及，BIM 信息化數(shù)據(jù)審查的意義也逐漸凸顯[1-2]。傳統(tǒng)的二維施工圖審查并沒有真正的實(shí)現(xiàn)智能化審查，需要審查工作人員對提交的二維圖紙進(jìn)行全專業(yè)的審查工作，將存在以下問題：問題（1）：在審圖過程中，由于審圖人員對規(guī)范的理解、專業(yè)水平、經(jīng)驗(yàn)以及審查尺度等不一致，這會造成審查結(jié)果的不一致。問題（2）：由于審查工作涉及的專業(yè)眾多，需要審查的規(guī)范眾多。隨著各個專業(yè)的飛速發(fā)展，各個專業(yè)所涉及審查規(guī)范的版本也在不停的更新之中，審查工作量大。在審圖工作進(jìn)行時，存在挑選重要審查部位進(jìn)行針對性審查。由此，造成了審查工作的不全面，規(guī)范條文漏審的情況。問題（3）：政府管控難。主管部門無法及時獲取施工圖審查過程中各環(huán)節(jié)存在的問題，對施工圖設(shè)計(jì)、審查質(zhì)量的真實(shí)情況難以準(zhǔn)確掌握，監(jiān)管的有效性和時效性均不能得到保證。針對以上問題，2017年湖南省以工程建設(shè)項(xiàng)目三維數(shù)字報(bào)建為切入點(diǎn)開啟基于BIM 模型的施工圖數(shù)字化審查。2019年，指導(dǎo)各地開展城市信息模型（CIM）基礎(chǔ)平臺建設(shè)，推進(jìn)智慧城市建設(shè)，北京、雄安、廣州、南京、廣州、廈門、雄安等多個城市被住房和城鄉(xiāng)建設(shè)部列為城市信息化建設(shè)和建筑信息模型審查的試點(diǎn)城市[3-6]。

隨著建筑信息化審查工作的開展，具體條文內(nèi)容的審查以及建筑信息化數(shù)據(jù)的處理方法也成為數(shù)值化審查工作中的重點(diǎn)工作。特別是對應(yīng)建筑消防的數(shù)字審查工作，如建筑消防審查參考的一個主要規(guī)范《建筑設(shè)計(jì)防火規(guī)范》（GB 50016-2014，2018年版）[7]。這本規(guī)范中5.5.17 對于疏散路徑的審查，需要對審查模型中的疏散路徑進(jìn)行計(jì)算后與規(guī)范數(shù)值進(jìn)行比對。模型中疏散路徑的計(jì)算一直都是數(shù)值化審查中的難點(diǎn)，針對該問題，本文將Dijkstra 算法應(yīng)用到BIM 審查的數(shù)字計(jì)算中，更為準(zhǔn)確的求除疏散路徑。

表1 防火規(guī)范中疏散距離的規(guī)定

1 Dijkstra 算法

Dijkstra 算法處理的是一組結(jié)點(diǎn)集合數(shù)據(jù)中各個節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最短路徑問題是圖論研究中的經(jīng)典算法問題。最常用的路徑算法有：Dijkstra 算法、A*算法、SPFA 算法、Bellman-Ford 算法和Floyd-Warshall 算法[8-11]。本文中主要正對Dijkstra 算法在消防審查中疏散路徑問題的應(yīng)用進(jìn)行描述。

為更好得理解Dijkstra 算法，如圖1所示，現(xiàn)有結(jié)點(diǎn)集合S=[P1、P2、P3、P4、P5、P6]以及其各節(jié)點(diǎn)之間的路徑信息，①為結(jié)點(diǎn)編號，-3-為路徑信息，各個結(jié)點(diǎn)之間雙向距離相等，再應(yīng)用Dijkstra 算法對已知結(jié)點(diǎn)集合S 求其最短路徑。依據(jù)圖1的路徑星系，第一步列出一個二維數(shù)據(jù)結(jié)構(gòu)，儲存結(jié)點(diǎn)集合S 中各個結(jié)點(diǎn)之間的直接路徑數(shù)據(jù)，形成表2所示的對稱的二維矩陣。

表2 直接路徑信息儲存表

圖1 結(jié)點(diǎn)集合以及其路徑線示意圖

第二步以結(jié)點(diǎn)1 直接到達(dá)各個結(jié)點(diǎn)的路徑距離為結(jié)點(diǎn)1 到各個結(jié)點(diǎn)的初始最短路徑距離，求到結(jié)點(diǎn)1 路徑最短的那個結(jié)點(diǎn)。根據(jù)最初的直接路徑信息儲存表可以確定，結(jié)點(diǎn)1 的路徑最短結(jié)點(diǎn)為結(jié)點(diǎn)2，并可以確定結(jié)點(diǎn)1 到結(jié)點(diǎn)2 的最短路徑為直接到達(dá)的路徑，即結(jié)點(diǎn)2-結(jié)點(diǎn)1。計(jì)算結(jié)點(diǎn)1 通過結(jié)點(diǎn)2 到達(dá)各個結(jié)點(diǎn)的路徑，并且將該路徑值與結(jié)點(diǎn)1 直接到達(dá)各個結(jié)點(diǎn)的路徑距離對比，取兩者的最小值，可以得到結(jié)點(diǎn)1 各個結(jié)點(diǎn)的最短路徑距離如表3所示。可以發(fā)現(xiàn)結(jié)點(diǎn)5、結(jié)點(diǎn)6 到結(jié)點(diǎn)1 的最短路徑得到了刷新。

表3 通過結(jié)點(diǎn)2 刷新的最短路徑

第三步獲取通過結(jié)點(diǎn)2 刷新的最短路徑的最短路徑結(jié)點(diǎn)（除結(jié)點(diǎn)2 外），可以確定此時的最短路徑結(jié)點(diǎn)為結(jié)點(diǎn)4，并且可以確定此時結(jié)點(diǎn)4 到結(jié)點(diǎn)1 的最短路徑為直接到達(dá)路徑，即結(jié)點(diǎn)4-結(jié)點(diǎn)1。計(jì)算結(jié)點(diǎn)1 通過結(jié)點(diǎn)4 再到各個結(jié)點(diǎn)的路徑距離，并與表2中的路徑距離對比，取兩者的最小值，可以得到結(jié)點(diǎn)1 到各個結(jié)點(diǎn)的最短路徑距離如表4所示。在該步驟比較中，并沒有最短路徑得到刷新。

表4 通過結(jié)點(diǎn)4 刷新的最短路徑

第四步獲取通過結(jié)點(diǎn)4 刷新的最短路徑的最短路徑結(jié)點(diǎn)（除結(jié)點(diǎn)2、結(jié)點(diǎn)4 外），可以確定此時的最短路徑結(jié)點(diǎn)為結(jié)點(diǎn)5，并且可以確定此時結(jié)點(diǎn)5 到結(jié)點(diǎn)1 的最短路徑為結(jié)點(diǎn)5-結(jié)點(diǎn)2-結(jié)點(diǎn)1。計(jì)算結(jié)點(diǎn)1 通過結(jié)點(diǎn)5 再到各個結(jié)點(diǎn)的路徑距離，并與表3中的路徑距離對比，取兩者的最小值，可以得到結(jié)點(diǎn)1 到各個結(jié)點(diǎn)的最短路徑距離如表5所示。在該步驟比較中，并沒有最短路徑得到刷新。

表5 通過結(jié)點(diǎn)5 刷新的最短路徑

第五步獲取通過結(jié)點(diǎn)5 刷新的最短路徑的最短路徑結(jié)點(diǎn)（除結(jié)點(diǎn)2、結(jié)點(diǎn)4、結(jié)點(diǎn)5外），可以確定此時的最短路徑結(jié)點(diǎn)為結(jié)點(diǎn)3，并且可以確定此時結(jié)點(diǎn)3 到結(jié)點(diǎn)1 的最短路徑為結(jié)點(diǎn)3-結(jié)點(diǎn)2-結(jié)點(diǎn)1或者結(jié)點(diǎn)3-結(jié)點(diǎn)1。計(jì)算結(jié)點(diǎn)1 通過結(jié)點(diǎn)3 再到各個結(jié)點(diǎn)的路徑距離，并與表4中的路徑距離對比，取兩者的最小值，可以得到結(jié)點(diǎn)1 到各個結(jié)點(diǎn)的最短路徑距離如表6所示。在該步驟比較中，并沒有最短路徑得到刷新。

表6 通過結(jié)點(diǎn)3 刷新的最短路徑

2 Dijkstra 算法的應(yīng)用

2.1 計(jì)算前處理

在進(jìn)行實(shí)際樣例模型計(jì)算之前，需要對實(shí)際樣例模型進(jìn)行簡化處理。獲取Revit模型的房間內(nèi)輪廓線以及疏散門、安全出口的位置點(diǎn)。如圖2所示，在對求圖中各個房間的疏散門到疏散走道的安全出口之間的疏散距離，即疏散門到安全出口的最短路徑。在求最短距離問題時，可以將房間內(nèi)的疏散距離轉(zhuǎn)化為特征點(diǎn)之間最短路徑問題。特征點(diǎn)集合由疏散走道的輪廓線端點(diǎn)、疏散門以及安全出口的位置點(diǎn)組成，即S=[P1、P2、P3、P4、P5、P6、P7、P8、P9、P10]。如圖2所示，分別計(jì)算點(diǎn)集合S中P3、P4、以及P6 到P9 的最短路徑。

圖2 樣例模型示意圖

如圖3所示，在對點(diǎn)集合進(jìn)行計(jì)算時，我們需要根據(jù)各個點(diǎn)之間的實(shí)際距離確定各個結(jié)點(diǎn)之間的路徑距離，即取樣例模型中各個結(jié)點(diǎn)的連線長度。需要注意，在實(shí)際問題中，當(dāng)兩點(diǎn)直線連線穿越墻體時，人在疏散時無法按照該直線距離逃生，該疏散路徑可直接丟棄，即將兩點(diǎn)之間的路徑距離直接賦值正無窮大，進(jìn)行后續(xù)計(jì)算。

2.2 Dijkstra 計(jì)算

在計(jì)算如圖3所示的樣例模型時，先根據(jù)Dijkstra 算法，算出所有結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。

圖3 樣例模型Dijkstra 算法路徑線示意圖

第一步：

求出各個結(jié)點(diǎn)之間的距離，并存入一個二維數(shù)組D[10,10]，作為P1 結(jié)點(diǎn)到第P10 個結(jié)點(diǎn)之間的初始最短距離；

初始化一個一維數(shù)組Length，并存入P1 結(jié)點(diǎn)到其他結(jié)點(diǎn)的距離；

初始化一個一維數(shù)組Used，并存入Pi結(jié)點(diǎn)是否被遍歷，序號為0 即Used[0]=true，其他為false；

初始化一個字典，并存入P1 結(jié)點(diǎn)的最短路徑所經(jīng)過的結(jié)點(diǎn)序號。

第二步：

初始化一個最小值dMin=double 值的最大值；

初始化一個序號k=0，即P1 結(jié)點(diǎn)在S中的序號；

循環(huán)所有的結(jié)點(diǎn)，找到?jīng)]有被遍歷過的結(jié)點(diǎn)中距離P1 最短的結(jié)點(diǎn)Pm（dMin=P1至Pm 之間的距離），并將k 刷新為結(jié)點(diǎn)Pm的序號m-1，數(shù)組Used[k]刷新為true。

循環(huán)所有的結(jié)點(diǎn)，找到?jīng)]有被遍歷過的結(jié)點(diǎn)Pn，如果Length[n-1]大于dMin 加上D[m-1,n-1](即結(jié)點(diǎn)P1 到結(jié)點(diǎn)Pn 的距離大于結(jié)點(diǎn)P1 通過結(jié)點(diǎn)Pm 到結(jié)點(diǎn)Pn 的距離)，則刷新數(shù)組Length 的值，Length[n-1]=dMin+D[m-1,n-1]，并更新字典中最短路徑的結(jié)點(diǎn)序號。

表7 疏散門至安全出口的最短路徑

第三步：

重復(fù)第二步，直至所有點(diǎn)集S 中結(jié)點(diǎn)被遍歷，以此求得各個結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。

在求得所有結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑后，分別獲取P3 至P9，P4 至P9 以及P6 至P9 的最短路徑，如圖4所示。

圖4 初始疏散路徑結(jié)果

2.3 結(jié)果后處理

通過Dijkstra 算法對樣例模型進(jìn)行計(jì)算，我們能夠得到疏散門位置點(diǎn)到安全出口位置點(diǎn)的距離。

實(shí)際最短疏散距離還需要對比疏散門邊到安全出口門邊的距離，此時只需要對比各個疏散門位置點(diǎn)與兩個門框在疏散路徑的最短距離，可確定為最終的疏散路徑，如圖5所示。

圖5 疏散路徑結(jié)果

2.4 計(jì)算結(jié)果在審查中的應(yīng)用

將以上求解的疏散路徑結(jié)果應(yīng)用以實(shí)際項(xiàng)目的審查之中，如圖6所屬的項(xiàng)目，疏散門到安全出口的最短路徑為33.116m，不滿足5.5.17 中疏散門至安全出口的疏散距離應(yīng)該小于等于15m 的要求。

圖6 疏散路徑算法在審查項(xiàng)目中的應(yīng)用

3 結(jié)論

本研究將Dijkstra 算法應(yīng)用到BIM 審查的數(shù)字計(jì)算中，對《建筑設(shè)計(jì)防火規(guī)范》（GB 50016-2014，2018年版）中5.5.17條文中的疏散門到安全出口的疏散路徑進(jìn)行計(jì)算。將房間輪廓線的兩個端點(diǎn)以及疏散門、安全出口的位置點(diǎn)作為特征點(diǎn)集合，應(yīng)用Dijkstra 算法對特征點(diǎn)集合進(jìn)行計(jì)算。將得到的初步疏散路徑再次經(jīng)過門寬部分最短路徑對比，得到最終的疏散路徑。根據(jù)計(jì)算的最短路徑，與規(guī)范5.5.17 中的相關(guān)規(guī)定進(jìn)行比對，以此審查出不滿足規(guī)范的距離。