摘 要： 以建筑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.