基于BIM的室内导航网络构建方法

张炜锴 郑加柱 陈媛媛

摘 要：为构建满足室内位置服务的导航网络和提高构建导航网络的便捷性，在建筑信息模型（BIM）作为室内三维数据来源的基础上，提出一种基于对偶图思想的室内导航网络构建方法。该方法基于BIM模型与限定德劳内（Delaunay）三角剖分细化算法，利用对偶原则的思想，通过解析BIM模型的IFC文件，将其所包含的语义信息、拓扑关系和3D几何关系进行映射，提取出适用于室内导航及位置服务的轻量化网络模型，并以某建筑数据为基础进行了实例研究。结果表明：该方法能够将BIM模型中的导航要素进行抽象化表达，基本满足跨楼层室内导航服务的要求，并支持上下文感知的室内位置服务，所构建的点-边几何导航网络模型具有设置灵活、寻路效率高的特点。

关键词：导航网络;位置服务;建筑信息模型（BIM）;三角剖分

Abstract：In order to construct a navigation network satisfying the indoor location-based service and improve the convenience of building navigation network， based on the Building Information Model （BIM） as the indoor three-dimensional data source， a method of building indoor navigation network based on dual graph is proposed. The method is based on the BIM model and Constrained Delaunay triangulation refinement algorithm， using the idea of the dual principle， the IFC file of the BIM model is parsed， and the semantic information， topological relationship and 3D geometric relationship contained in the BIM model are mapped. This method extracts lightweight network model suitable for indoor navigation and location service， and based on some building data， a case study is carried out. The results show that this method can abstract the navigation elements in BIM model， basically meet the requirements of cross floor indoor navigation service， and support the context aware indoor location service. The point edge geometric navigation network model has the characteristics of flexible setting and high efficiency of road finding.

Keywords：Navigation network; location-based service; Building Information Model （BIM）; triangulation

0 引言

随着近年来室内定位技术的兴起，基于位置的服务 （Location-based Service， LBS） 也开始从室外拓展到室内[1-2]。室内导航网络是室内LBS的基本要素，然而室外成熟的路网索引技术不能直接应用于具有复杂拓扑结构的室内空间。多年来，研究人员一直致力于开发一种自动生成室内导航网络的方法，目前主流的方法为两类：支持几何网络模型（Geometric Network Models，GNM）生成的几何方法和开发规则栅格模型（Regular Grid Models，RGM）的栅格方法[3]。虽然栅格方法具有更高的精度，但由于几何方法包含空间语义信息和粗粒度级别的几何信息[4]，能满足跨楼层的导航需求和LBS对上下文感知能力及适应能力的要求;此外，在场景较大的室内空间，几何网络模型与栅格模型相比能节省大量的数据处理时间[5]，所以几何方法被广泛用于LBS服务中。Isikdag等[6]提出室内模型与导航网络模型互为对偶的特性，Tang等[7]、武恩超等[8]采用将中轴变换算法与室内模型相结合，重建室内几何拓扑网络。Liu等[9]提出只使用语言描述的逻辑网络模型，作为室内导航的参考。

当前室内地图尚未充分发展到像室外地图这样的标准化表示，构建室内导航模型的源数据众多，包括二维平面图、建筑信息模型（BIM）和City GML等[10-11]。建筑信息模型是建筑物全寿命周期中所有物理和功能特征的数字化表示，随着BIM技术的逐步普及，基于IFC标准的建筑信息模型已经成为支持室内导航的一种重要数据来源[6， 12]。其詳尽的几何语义、要素材质、功能信息及各要素之间的关联关系，能为室内导航提供较充分的数据支持[13]。

综上所述，在目前的研究中，大多数室内导航框架将CAD平面图作为原始数据集，对室内路网进行了大量简化，在路径规划时大多只考虑单一平面楼层的最短路径，但面向室内导航时最短路径并不代表最优路径，复杂的室内因素和用户本身的特定需求对路径的选择存在巨大影响。此外，建筑物在其生命周期中不断变化并定期进行翻新，若采用传统的手动生成导航模型，对诸如医院、商场等大型建筑而言将花费大量的人力、物力。本文采用基于BIM数据的原始模型和基于对偶图思想所简化的对偶模型，利用限定 Delaunay三角剖分细化算法对室内空间进行剖分，构建面向室内位置服务的几何网络模型。

1 室内网络模型的构建方法

1.1 室内导航网络模型数据结构

室内导航通常需要多种数据的支持，本文所构建的室内导航网络主要包括基于BIM数据的原始模型和基于对偶图思想所简化的对偶模型，其数据结构如图1所示。原始模型包括三维空间的几何表示和建筑物内各种构件的拓扑关系，原始模型主要用于提供信息、数据检索及导航可视化。对偶模型是以点和线为主要要素，表示物理连接的几何网络，用于计算所需的最佳导航路径。

1.2 构建本体模型

为了构建本体模型，本研究主要通过解析工业基础类标准（industry foundation classes，IFC）的建筑信息模型（BIM），获得BIM与室内导航相关的语义信息。语义信息给室内导航要素的分类提供依据，主要包含室内各导航要素的属性、相对关系及功能[14]。IFC中定义了600余种实体和300多种补充数据类型以及可拓展属性集[15] ，通过形式化将IFC中各种属性间接定义为系统行为，并以表的形式存储于节点或线段之中，从而得到本体模型（Ontology Model）。本体模型主要应用于导航数据属性检索和空间推理，本文构建的本体模型结构基本分类包括空间、路径、路径点、障碍物和兴趣点，每一分类中的要素都与IFC数据中的实体所对应。

IFC标准中的元素采用层次结构，其中所有元素都具有基类（IfcProduct）的属性和方法，并细分为空间元素（IfcSpatialStructureElement）、物理元素（IfcElement）、端口元素（IfcPort）和其他。IfcSpatialStructureElement包含场地（IfcSite）、楼层（IfcBuildingStorey）和空间（IfcSpace）等子元素。通过对空间元素进行楼层映射，可以提取室内每个楼层的相关信息，例如IfcSpace为建筑物内包含某些具有特定功能的区域。IfcElement是构成建筑、工程和施工行业（Architecture，Engineering&Construction，AEC）产品的所有构件的概括，其子类引入了详细规范，如建筑物构件类（IfcBuildingElement）、家具类（IfcFurnishingElement）、设备类（IfcEquipmentElement）。这里的IfcBuildingElement是建筑物的主要功能部件，例如墙（IfcWall）、门（IfcDoor）、柱（IfcColumn）和楼梯（IfcStair）等。Ifc实例可以将外部属性分配给IfcBuildingElement要素，例如可以给IfcDoor赋予“公开”或“不公开”以表示该区域是否能通行。除此之外，为了使室内导航网络更好地实现室内位置服务，应根据具体需求增加丰富的信息点（POI）。通常导入的LOD 300以上BIM模型会包含除结构构件外的服务性实体模型，如IfcFurnishingElement是所有家具对象的概括，本文使用其安置位置（IfcLocalPlacement）和范围盒（BoundingBox）属性来确定室内障碍物的位置及边界。同样IfcEquipmentElement是所有服务设备的概括，如自动售货机等实体构件可以作为室内导航网络的兴趣点。本体模型的构建，使得室内导航网络具有良好的语义感知能力。

1.3 构建层次型图模型

建筑物通常由多个楼层构成，这也是室内导航环境与室外导航的重要区别之一。针对这一特点，室内空间通常采用多层网络拓扑模型，各个楼层可以通过楼梯、电梯进行连通。在IFC模型中，Storey Count属性提供该建筑物中的楼层数，IfcBuildingStorey作为楼层实体，包含梁、柱、墙、门、 窗、楼梯和电梯等构件。但是考虑到实际建立室内网络模型时要生成符合使用者通行习惯的合理路径，并不能对整个楼层区域进行剖分，所以对楼层采取构建子空间的方法。构建的子空间分为3类。

（1）带有入口的封闭空间。

（2）开放空间，通常作为通往其他封闭空间的通道。

（3）跨樓层连通空间，如楼梯间、电梯间等。

子空间的构建主要利用IFC中的IfcSpace类生成对偶模型，IfcSpace表示实际或理论上界定的区域或体积，在指定情况下，IfcSpace可以与建筑物的楼层关联，也可与场地外部空间关联。因此空间组提供了包含在某一个楼层中的空间集合。IfcSpace也可以部分分解，其中每一部分都定义部分空间。这可以由IfcSpatialStructureElement的组合类型属性定义，分别可以由complex、element、partial表示空间组、空间、部分空间。此外，在同一楼层的室内子空间利用节点之间（房间-门、走廊-楼梯＼电梯）、节点与边（门-走廊）之间的连通实现整个室内环境连通的模型。

1.4 构建几何网络模型

几何网络主要是以节点和边所构成的物理网络，其高度可用属性H表示，是一种2.5 D模型，主要应用于提供距离等几何信息。本研究主要基于平面图的限定德劳内（Delaunay）三角剖分细化算法进行构建。Shewchuk[16]提出的限定Delaunay三角剖分细化算法是一种用于生成非结构化三角形网格的技术，能有效覆盖指定域[17]，并且所生成的三角形能满足形状和大小约束。细化算法是通过在低质量的三角形外接圆心处插入细分点，使用Lawson算法或Bowyer-Watson算法维护Delaunay三角剖分属性，以进行Delaunay三角剖分的增量更新，从而避免狭长三角形。

1.4.1 楼层空间区域的剖分

1.4.1.1 对多边形边界进行采样

对于提取出的子空间IFC几何信息，目前支持使用二维曲线（Curve2D）或几何曲线集（GeometricCurveSet）类型的2 D几何表示。通过对子空间的边界和子空间内部的家具等障碍物进行采样，生成二维有界图形，以供 Delaunay三角剖分细化算法生成非结构化网格。

1.4.1.2 计算限定Delaunay三角细化剖分

将上一步采集的内外边界输入限定 Delaunay三角剖分细化算法，其所创建的三角形与一般三角剖分算法相比，除了具有内外边界的约束，还避免了细长的三角形。限定 Delaunay三角剖分细化算法适用于具有各种不规则形状的室内空间，并且均匀覆盖于区域空间中，提高了几何精度。

1.4.1.3 选取路径点

经过细化剖分处理后，子空间被描述为更加准确、尺度更小的空间区域。在这些细化的剖分区域中进行移动，根据剖分区域中的拓扑关系，需要明确每个小区域中下一个路径点的方位，而剖分所得的三角形无法直接作为路径点，所以应选取合适的特征点作为路径点。路径点的选择通常为剖分后的小三角形的重心或者边上的中点。考虑到在走廊等细长空间内若选择小三角形的重心作为特征点，所生成的路径为Z字形，需要使用其他算法进行简化和平滑处理。由于限定 Delaunay三角剖分细化算法的特性，避免了狭长三角形的生成，因此选取子空间内部所有三角形边的中点为路径点，能较大程度避免路基的弯折，此外路径点不能位于外部或者内部限制边界上。

1.4.1.4 链接路径点

根据三角形与边界的关系，确定路径的链接方法，路径点只链接至与其相邻的三角形上的路径点。路径点的链接主要通过建立BSP树结构来实现，算法步骤如下。

（1）以子空间中位于左下角的路径点作为根节点，其所在的三角形为源三角形，与其共享边的邻接三角形为子树，判断邻接三角形除源三角形是否还存在邻接三角形。

（2）若除源三角形外无其他邻接三角形，则说明其为规则矩形，未进行细化剖分，只保留其共享边上的路径点。

（3）若除源三角形还存在一个或两个邻接三角形，则将邻接三角形上共边的中点插入BSP樹中，与根节点链接。

（4）从根节点开始，根据共边判断邻接三角形与源三角形的前后关系，前则遍历左子树，后则遍历右子树，遍历所有结构化三角形，最终形成子空间内完整的路径网络。

由图2可见，路径点①、②、③、④、⑤所在的分割平面将房间分割成A、B、C、D、E、F 6个区域，以①作为根节点，遍历相邻的分割平面，得到所有可能的BSP结构树，从而对各路径点进行链接。由图3可见，此方法同样适用于狭长的的走廊，能够较为完整地反映出可供通行的导航网络路径。

1.4.2 生成非水平路径

非水平路径是沿着楼梯、电梯等进行跨楼层通行的路径。对于楼梯，采用提取第一级踏步、最后一级踏步和休息平台的特征点，通过特征点的连接形成与楼梯几何特征一致的非水平路径。对于电梯，通常在BIM模型中只会构建电梯井来表示，在各楼层楼板上进行开口，所以通过提取电梯井的平面投影的重心，将所获得的楼层高度作为z坐标依次赋予重心，并连接这些点形成电梯路径。

2 室内导航网络构建与分析

2.1 网络数据集的构建

为了验证本文提出的基于BIM模型的室内导航网络构建方法，本文以南京林业大学教学主楼为试验对象（图4），采用以REVIT建模的BIM模型作为数据来源，建立原型系统进行验证。主要通过Dijkstra算法对所构建的室内导航网络进行寻径长度准确性验证。Dijkstra算法是一种经典的最短路径寻路算法，通过指定起始点和终止点来快速求解最短路径。Dijkstra算法的基本原理是在路网中每次找到离起始点最近的一个路径点，然后以起始点为中心，向外层层拓展，直至终止点处（图5）。

2.2 路径理论值与实际值之间的误差分析

随机选取试验区域中6条路线的理论值与实地测量的实际值之间的误差进行数据分析，根据计算得到统计数据见表1。

由表1可知，本实验体现出采用三角剖分的几何网络较灵活、寻路效率较高的特点，适用于大型开放空间。由于其剖分特性，可能会提供不符合实际的弯折导航路径，从而导致路径规划时所产生的误差，且误差随着路径长度的增加而增加。但模型中的几何网络长度相对于实地测量的路线长度的平均误差基本在3%以内， 此方法生成的室内导航网络的准确性基本满足室内导航的需求。如何优化导航网络的几何精度将在以后的研究中加以改进。

3 结束语

本文基于BIM模型数据，通过提取语义信息、几何信息和拓扑关系建立对偶模型，利用限定 Delaunay三角剖分细化算法对子空间进行剖分，探索了考虑真实室内环境导航几何网络的构建方法，从而为基于室内位置信息的导航服务提供可靠的数据来源。试验表明，这种室内导航网络构建方法不仅能提供较高的几何网络精度，且能提供丰富语义信息给路径规划作为参考。随着室内定位技术的发展及BIM技术的普及，室内导航服务将有更为广阔的应用前景，如何打通室内外一体化导航的瓶颈，将是下一步的研究方向。

【参 考 文 献】

[1]TANEJA S， AKINCI B， GARRETT J H， et al. Algorithms for automated generation of navigation models from building information models to support indoor map-matching[J]. Automation in Construction， 2016， 28（61）： 24-41.

[2]LIN W Y， LIN P H. Intelligent Generation of indoor topology （i-GIT） for human indoor pathfinding based on IFC models and 3D GIS technology[J]. Automation in Construction， 2018， 94： 340-359.

[3]LEWANDOWICZ E， LISOWSKI P， FLISEK P. A modified methodology for generating indoor navigation models[J]. ISPRS International Journal of Geo-Information， 2019， 8（2）：60.

[4]AFYOUNI I， RAY C， CLARAMUNT C. Spatial models for context-aware indoor navigation systems： a survey[J]. Journal of Spatial Information Science， 2012， 16（4）：85-123.

[5]KRUMINAITE M， ZLATANOVA S. Indoor space subdivision for indoor navigation[C]// 2014 ISA14， Proceedings of the Six ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness， Dallas USA， 2014， 11：25-31.

[6]ISIKDAG U， ZLATANOVA S， UNDERWOOD J. A BIM-oriented model for supporting indoor navigation requirements[J]. Computers， Environment and Urban Systems， 2013，11（41）： 112-123.

[7]TANG S J， ZHU Q S， WANG W L， et al. Automatic topology derivation from Ifc building model for in-door intelligent navigation[J]. ISPRS - International Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences， 2015： 7-11.

[8]武恩超，張恒才，吴升. 基于中轴变换算法的室内外一体化导航路网自动生成方法[J]. 地球信息科学学报， 2018，20（6）：730-737

WU E C， ZHANG H C， WU S. Automatic generation method of indoor and outdoor integrated navigation network based on medial axis transform algorithm[J]. Journal of Geo-Information Science， 2018， 20（6）： 730-737.

[9]LIU L， ZLATANOVA S， LI B F， et al. Indoor routing on logical network using space semantics[J]. ISPRS International Journal of Geo-information， 2019， 8（3）： 126.

[10]XIE L， WANG R S， MING Z T， et al. A layer-wise strategy for indoor as-built modeling using point clouds[J]. Applied Sciences， 2019， 9（14）：2904.

[11]WANG R， PEETHAMBARAN J， CHEN D. LiDAR point clouds to 3D urban models： a review[J]. IEEE Journal of Selected Topics in Applied Earth Observations & Remote Sensing， 2018， 11（2）：606-627.

[12]CHEN A Y HUANG T. Toward BIM-enabled decision making for in-building response missions[J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（5）：2765-2773.

[13]李佩瑶，汤圣君，刘铭崴，等. 面向导航的Ifc建筑模型室内空间信息提取方法[J]. 地理信息世界， 2015，22（6）：78-84.

LI P Y， TANG S J， LIU M W， et al. Extraction approach of indoor space information from IFC building model for navigation[J]. Geomatics World， 2015， 22（6）： 78-84.

[14]林雕，宋国民，贾奋励. 面向位置服务的室内空间模型研究进展[J]. 导航定位学报， 2014，2（4）：17-21

LIN D， SONG G M， JIA F L. Review of the research progresses in spatial model for indoor location-based service[J]. Journal of Navigation and Positioning， 2014， 2（4）： 17-21.

[15]余雯婷，李希胜. 基于Bim技术的建筑设施管理信息提取与应用[J]. 土木工程与管理学报， 2016，33（1）：85-89.

YU W T， LI X S. BIM-based information extraction and application of building facility management[J]. Journal of Civil Engineering and Management， 2016， 33（1）： 85-89.

[16]SHEWCHUK J R. Delaunay refinement algorithms for triangular mesh generation[J]. Computational Geometry Theory & Applications， 2002， 22（1）：21-74.

[17]卢伟，魏峰远，张硕，等. 室内路网模型的构建方法研究与实现[J]. 导航定位学报， 2014，2（4）：63-67.

LU W， WEI F Y， ZHANG S， et al. Research on a method of constructing the indoor road network model[J]. Journal of Navigation and Positioning， 2014， 2（4）：63-67.