摘 要： 以建筑AutoCAD矢量圖形文件為研究載體，以墻體為主要研究對象，設計了墻體數據深度優先探測提取算法。根據提取出的墻體數據集合，設計了基于凹點分割的墻體裁剪算法，該算法已在實踐中進行了反復驗證，高效可靠。在此基礎上提出了以中軸線+屬性形式代替墻體的設計思想，構建墻體抽象模型，為建筑工程量自動計算提供數據支持。
近年來，隨著計算機技術和信息技術的迅猛發展，建筑工程概預算領域中出現了大量的預算軟件，但這些軟件只是在人工讀圖并計算出工程量的基礎上完成定額套用、調整、費用計算、報表編制等工作，工程量計算工作還停留在由預算師人工識別圖紙的階段。因此，如何實現工程量的自動計算是目前建筑工程概預算領域研究的主要熱點之一，而建筑工程圖的自動識別問題是制約工程量計算自動化水平提高的主要瓶頸。本文模仿人工識圖的思路與方法，以建筑AutoCAD中墻體識別建模為例，設計出一套有效識別墻體、裁剪建模的算法，解決AutoCAD與工程量計算的接口問題，為實現建筑工程量計算的自動化提供參考。
1 AutoCAD矢量文件研究與墻體元素提取
AutoCAD采用矢量數據格式文件DXF存儲圖形信息[1]。DXF是一種被多數圖形設計軟件接受的文件存儲格式，其實際上已經成為一種行業標準。隨著AutoCAD的新版本不斷推出，對DXF文件格式作了進一步調整，但基本框架保持不變。DXF文件按先后順序分為7大段，其中實體段是研究的主要目標，在實體段中保存著所有離散的圖形圖元[1]，這些實體有Point、Line、Circle、Arc、Trace、Solid、Polyline、Vertex和3Dface等圖形圖元。每段由鍵值對組成，鍵（通常稱為組碼）表明其后的值的類型，使用這些鍵值對可以將AutoCAD圖形元素組織到由記錄組成的區域中。
本文在對建筑墻體識別之前，首先將DXF格式文件轉化為可讀性更好、被軟件普遍接受的XML格式文件[2-4]。DXF格式文件轉換成XML格式文件后的數據格式如圖1所示。從DXF文件中讀取的信息還處于離散狀態，之間沒有任何聯系，在進行墻體識別、裁剪、建模之前要對這些離散數據進行必要的預處理，使其滿足識別需要。在房屋建筑制圖統一標準[5]中，對建筑制圖中的各種圖形元素畫法都作出了非常具體的規定，其中墻體具有以下特點。
（1）任何一段墻體都構成一個封閉的區域，并且構成墻體的線段數要大于或等于4；
（2）每段墻體之間通過門、窗等建筑構件相連接；
（3）通常按照建筑中墻體的外型，可以將墻體分為L型、T型、C型、＋型、直線型和復雜的不規則類型等。建筑圖中墻體的常見形狀如圖2所示。
構成墻體的主要圖元就是線段，墻體是由若干條線段形成的一個封閉區域。對于墻體的數據提取，可以采用深度優先遍歷方法[6-7]，在已讀出的大量線段中任意選取一條作為起始點，根據線段兩端的坐標去匹配下一條線段，直到回到起點。
根據以上特點，設計用于在離散數據中識別提取墻體的算法1。
算法1：墻體識別提取算法
（1）?坌line?奐{linei|i≥1}。
（2）提取l1起點坐標S{x，y，z}。
（3）提取l1終點坐標P{x，y，z}，與{linei|i≥1}中其他線段起點坐標匹配。
（4）匹配成功，得到l2，存儲l1，l1=l2。
（5）LOOP重復步驟（3）~步驟（4），循環計數器count
IF P{x，y，z}==S{x，y，z}，存儲所有墻體線段；
IF count>i，放棄所有線段，重新探測。
經過算法1處理后，從眾多離散線段中識別、提取出墻體集合{walli|i≥1}{linei|i≥1}。
2 墻體圖形裁剪算法設計
在成功獲取墻體集合后，采用提取墻體中軸線的方法建立墻體數學模型，但對于形式復雜的墻體造型，若直接提取中軸線會造成建筑工程量計算的重復，導致數據偏差，所以還要對墻體進行進一步的細分。本文提出了基于凹點多邊形墻體裁剪算法[8-11]，將復雜墻體分割成相對簡單的墻體單元。
針對平面直角坐標系中墻體構造的多邊形，判斷凹點及采集算法如下。
算法2：凹點判斷與墻體裁剪算法
在建筑CAD中絕大多數墻體都是水平或鉛直的，同時存在有一定角度或弧形的墻體。對于水平和鉛直類墻體，可以使用比較法判斷凹點；對于有一定角度的墻體，拐點可以采用斜率法進行判斷；對于弧形墻體，將進行特殊處理，不在本文討論范圍內。
（1）對于水平鉛直墻體的凹點判斷與裁剪算法。
①從墻體集合{walli|i≥1}中選取一組封閉墻體數據，以x分量最小的點作為起點。
②嚴格按照順時針方向遍歷墻體線段。
定義：起始線段li（i=1），起點坐標s（xi，yi），終點坐標e（xi，yi），順時針鄰接線段為li+1，起點坐標s（xi+1，yi+1），終點坐標e（xi+1，yi+1），兩線段交點為P，即e（xi，yi）=s（xi+1，yi+1）。
IF （e|yi>s|yi） and （e|xi+1>e|xi） THEN P為凸點；
IF （e|yi>s|yi） and （e|xi+1<e|xi） THEN P為凹點；
IF （e|yi<s|yi） and （e|xi+1<e|xi） THEN P為凸點；
IF （e|yi<s|yi） and （e|xi+1>e|xi） THEN P為凹點；
簡單來說，從起點開始，x、y坐標變化滿足下面規律就是最簡墻體；否則，若存在凹點，就延長線段交于墻體線段集合中的某條線段，并分離出一段墻體。
裁剪算法過程演示如圖3所示。在圖3（a）中，選出A為遍歷起點。遍歷過程為：AB（Y↑）→BC（X↑）→CD（Y↓）→DE（X↓）→EF（Y↑）→FG（X↓），在EF-FG線段交點處出現凹點，記錄F點信息，向墻體集合中添加輔助線段FX，并將EF延長到X，即用EX代替DF，并將CD、DE、EX、XC從墻體集合中分離出來形成單獨集合。重復以上算法，對剩余墻體集合繼續遍歷，任何一段復雜的墻體集合通過該算法都能分解成為最簡墻體，即得到墻體的最簡形式。
（2）使用斜率判定非水平鉛直墻體的凹點。
定義：d為相鄰兩條線段的斜率差，由于墻體線段不在水平鉛直狀態，無需考慮分母為零的情況。
IF（e|yi>s|yi）
IF d>0 THEN P為凹點
IF d<0 THEN P為凸點
IF（e|yi>s|yi）
IF d>0 THEN P為凸點
IF d<0 THEN P為凹點
3 墻體數據模型構建
圖紙識別的最終目的是要建立起墻體的數學模型，并在此基礎上實現對建筑工程量的估算[12]。模型是全面反映墻體形狀和結構的基礎，并附加以必要的屬性。墻體的中軸線是確定墻體的核心數據，利用分解后的簡單墻體中平行的兩長邊端點信息，可以確定中軸線兩端點坐標，并將該段墻體的厚度等設計參數一并存入中軸線數據結構中，形成一個關于墻體中軸線鏈表。設墻體的兩條平行邊為l1和l2，起點為s，終點為e，則中軸線兩端點坐標為：
可以用鏈表構造其內部存儲結構，鏈表的節點定義如圖4所示。
有了以上軸線抽象模型，可以方便、準確地計算墻體的長度，重構墻體輪廓，方便后期建筑工作量提取[13]。
本文在對AutoCAD矢量數據文件大量研究的基礎上，以建筑工程中墻體為例，設計了墻體深度優先識別提取算法；針對提取的復雜墻體，設計了基于凹點分割的墻體裁剪算法，并以墻體中軸線模型加屬性的方式重構墻體，為工程量計算提供有效支持。在算法設計過程中注重與具體問題相結合，加入識別裁剪過程中的輔助因素，降低了通用算法的復雜度，使算法簡潔而高效。
參考資料
[1] Autodesk Inc. DXF Reference. http：//www.autodesk.com/techpubs/autocad/acadr14/dxf/.
[2] 王志勃.基于DXF文件格式的讀取與XML轉換[J].新學術，2007（6）：240-243.
[3] 劉傳亮，陸建德.AutoCAD DXF文件格式與二次開發圖形軟件編程[J].微機發展，2004（9）：101-104.
[4] 舒飛.中文版AutoCAD 2004二次開發標準教程[M].上海：上海科學普及出版社，2004.
[5] GB/T 50001-2001. 房屋建筑制圖統一標準[S].
[6] DOSCH P H， MASINI G. Reconstruction of the 3D structure of a building from the 2D Drawings of its Floors[J]. Proceedings of the 5th International Conference on Document Analysis and Recognition， Bangalore（India），1999：487-490.
[7] Yu Yuhong， SAMAL A. A system for recognizing a large class of engineering drawings[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（8）： 868-890.
[8] 宋曉眉，程昌秀，周成虎.簡單多邊形頂點凹凸性判斷算法綜述[J].國土資源遙感，2011，90（3）：25-30.
[9] 陳炳發，錢志峰，廖文和.簡單多邊形凸凹性自識別算法[J].計算機輔助設計與圖形學學報，2002（3）：214-218.
[10] FEITO F， TORRES J C， URENA A. Orientation， simplicity， and inclusion test for planar polygons[J]. Computers & Graphics，1995，19（4）：595-600.
[11] DORI D， Liu Wenyin. Automated CAD conversion with the machine drawing under standing system：Concepts algorithm and performance[J]. IEEE Transaction on System， Man and Cybernetics， part A： System and Humans， 1999，29（4）：411-416.
[12] 孫靜波，侯秀萍，鄭虹.建筑圖數字化存貯與工程量計算模型的實現[J].計算機工程與應用，2003（10）：222-225.
[13] 陸再林，張樹有，譚建榮.基于圖形理解的預算工程量提取算法[J].計算機輔助設計與圖形學學報，2002（5）：442-446.