張煒鍇 鄭加柱 陳媛媛

摘 要：為構建滿足室內位置服務的導航網絡和提高構建導航網絡的便捷性，在建筑信息模型（BIM）作為室內三維數(shù)據來源的基礎上，提出一種基于對偶圖思想的室內導航網絡構建方法。該方法基于BIM模型與限定德勞內（Delaunay）三角剖分細化算法，利用對偶原則的思想，通過解析BIM模型的IFC文件，將其所包含的語義信息、拓撲關系和3D幾何關系進行映射，提取出適用于室內導航及位置服務的輕量化網絡模型，并以某建筑數(shù)據為基礎進行了實例研究。結果表明：該方法能夠將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的基本要素，然而室外成熟的路網索引技術不能直接應用于具有復雜拓撲結構的室內空間。多年來，研究人員一直致力于開發(fā)一種自動生成室內導航網絡的方法，目前主流的方法為兩類：支持幾何網絡模型（Geometric Network Models，GNM）生成的幾何方法和開發(fā)規(guī)則柵格模型（Regular Grid Models，RGM）的柵格方法[3]。雖然柵格方法具有更高的精度，但由于幾何方法包含空間語義信息和粗粒度級別的幾何信息[4]，能滿足跨樓層的導航需求和LBS對上下文感知能力及適應能力的要求;此外，在場景較大的室內空間，幾何網絡模型與柵格模型相比能節(jié)省大量的數(shù)據處理時間[5]，所以幾何方法被廣泛用于LBS服務中。Isikdag等[6]提出室內模型與導航網絡模型互為對偶的特性，Tang等[7]、武恩超等[8]采用將中軸變換算法與室內模型相結合，重建室內幾何拓撲網絡。Liu等[9]提出只使用語言描述的邏輯網絡模型，作為室內導航的參考。

當前室內地圖尚未充分發(fā)展到像室外地圖這樣的標準化表示，構建室內導航模型的源數(shù)據眾多，包括二維平面圖、建筑信息模型（BIM）和City GML等[10-11]。建筑信息模型是建筑物全壽命周期中所有物理和功能特征的數(shù)字化表示，隨著BIM技術的逐步普及，基于IFC標準的建筑信息模型已經成為支持室內導航的一種重要數(shù)據來源[6， 12]。其詳盡的幾何語義、要素材質、功能信息及各要素之間的關聯(lián)關系，能為室內導航提供較充分的數(shù)據支持[13]。

綜上所述，在目前的研究中，大多數(shù)室內導航框架將CAD平面圖作為原始數(shù)據集，對室內路網進行了大量簡化，在路徑規(guī)劃時大多只考慮單一平面樓層的最短路徑，但面向室內導航時最短路徑并不代表最優(yōu)路徑，復雜的室內因素和用戶本身的特定需求對路徑的選擇存在巨大影響。此外，建筑物在其生命周期中不斷變化并定期進行翻新，若采用傳統(tǒng)的手動生成導航模型，對諸如醫(yī)院、商場等大型建筑而言將花費大量的人力、物力。本文采用基于BIM數(shù)據的原始模型和基于對偶圖思想所簡化的對偶模型，利用限定 Delaunay三角剖分細化算法對室內空間進行剖分，構建面向室內位置服務的幾何網絡模型。

1 室內網絡模型的構建方法

1.1 室內導航網絡模型數(shù)據結構

室內導航通常需要多種數(shù)據的支持，本文所構建的室內導航網絡主要包括基于BIM數(shù)據的原始模型和基于對偶圖思想所簡化的對偶模型，其數(shù)據結構如圖1所示。原始模型包括三維空間的幾何表示和建筑物內各種構件的拓撲關系，原始模型主要用于提供信息、數(shù)據檢索及導航可視化。對偶模型是以點和線為主要要素，表示物理連接的幾何網絡，用于計算所需的最佳導航路徑。

1.2 構建本體模型

為了構建本體模型，本研究主要通過解析工業(yè)基礎類標準（industry foundation classes，IFC）的建筑信息模型（BIM），獲得BIM與室內導航相關的語義信息。語義信息給室內導航要素的分類提供依據，主要包含室內各導航要素的屬性、相對關系及功能[14]。IFC中定義了600余種實體和300多種補充數(shù)據類型以及可拓展屬性集[15] ，通過形式化將IFC中各種屬性間接定義為系統(tǒng)行為，并以表的形式存儲于節(jié)點或線段之中，從而得到本體模型（Ontology Model）。本體模型主要應用于導航數(shù)據屬性檢索和空間推理，本文構建的本體模型結構基本分類包括空間、路徑、路徑點、障礙物和興趣點，每一分類中的要素都與IFC數(shù)據中的實體所對應。

IFC標準中的元素采用層次結構，其中所有元素都具有基類（IfcProduct）的屬性和方法，并細分為空間元素（IfcSpatialStructureElement）、物理元素（IfcElement）、端口元素（IfcPort）和其他。IfcSpatialStructureElement包含場地（IfcSite）、樓層（IfcBuildingStorey）和空間（IfcSpace）等子元素。通過對空間元素進行樓層映射，可以提取室內每個樓層的相關信息，例如IfcSpace為建筑物內包含某些具有特定功能的區(qū)域。IfcElement是構成建筑、工程和施工行業(yè)（Architecture，Engineering&Construction，AEC）產品的所有構件的概括，其子類引入了詳細規(guī)范，如建筑物構件類（IfcBuildingElement）、家具類（IfcFurnishingElement）、設備類（IfcEquipmentElement）。這里的IfcBuildingElement是建筑物的主要功能部件，例如墻（IfcWall）、門（IfcDoor）、柱（IfcColumn）和樓梯（IfcStair）等。Ifc實例可以將外部屬性分配給IfcBuildingElement要素，例如可以給IfcDoor賦予“公開”或“不公開”以表示該區(qū)域是否能通行。除此之外，為了使室內導航網絡更好地實現(xiàn)室內位置服務，應根據具體需求增加豐富的信息點（POI）。通常導入的LOD 300以上BIM模型會包含除結構構件外的服務性實體模型，如IfcFurnishingElement是所有家具對象的概括，本文使用其安置位置（IfcLocalPlacement）和范圍盒（BoundingBox）屬性來確定室內障礙物的位置及邊界。同樣IfcEquipmentElement是所有服務設備的概括，如自動售貨機等實體構件可以作為室內導航網絡的興趣點。本體模型的構建，使得室內導航網絡具有良好的語義感知能力。

1.3 構建層次型圖模型

建筑物通常由多個樓層構成，這也是室內導航環(huán)境與室外導航的重要區(qū)別之一。針對這一特點，室內空間通常采用多層網絡拓撲模型，各個樓層可以通過樓梯、電梯進行連通。在IFC模型中，Storey Count屬性提供該建筑物中的樓層數(shù)，IfcBuildingStorey作為樓層實體，包含梁、柱、墻、門、 窗、樓梯和電梯等構件。但是考慮到實際建立室內網絡模型時要生成符合使用者通行習慣的合理路徑，并不能對整個樓層區(qū)域進行剖分，所以對樓層采取構建子空間的方法。構建的子空間分為3類。

（1）帶有入口的封閉空間。

（2）開放空間，通常作為通往其他封閉空間的通道。

（3）跨樓層連通空間，如樓梯間、電梯間等。

子空間的構建主要利用IFC中的IfcSpace類生成對偶模型，IfcSpace表示實際或理論上界定的區(qū)域或體積，在指定情況下，IfcSpace可以與建筑物的樓層關聯(lián)，也可與場地外部空間關聯(lián)。因此空間組提供了包含在某一個樓層中的空間集合。IfcSpace也可以部分分解，其中每一部分都定義部分空間。這可以由IfcSpatialStructureElement的組合類型屬性定義，分別可以由complex、element、partial表示空間組、空間、部分空間。此外，在同一樓層的室內子空間利用節(jié)點之間（房間-門、走廊-樓梯＼電梯）、節(jié)點與邊（門-走廊）之間的連通實現(xiàn)整個室內環(huán)境連通的模型。

1.4 構建幾何網絡模型

幾何網絡主要是以節(jié)點和邊所構成的物理網絡，其高度可用屬性H表示，是一種2.5 D模型，主要應用于提供距離等幾何信息。本研究主要基于平面圖的限定德勞內（Delaunay）三角剖分細化算法進行構建。Shewchuk[16]提出的限定Delaunay三角剖分細化算法是一種用于生成非結構化三角形網格的技術，能有效覆蓋指定域[17]，并且所生成的三角形能滿足形狀和大小約束。細化算法是通過在低質量的三角形外接圓心處插入細分點，使用Lawson算法或Bowyer-Watson算法維護Delaunay三角剖分屬性，以進行Delaunay三角剖分的增量更新，從而避免狹長三角形。

1.4.1 樓層空間區(qū)域的剖分

1.4.1.1 對多邊形邊界進行采樣

對于提取出的子空間IFC幾何信息，目前支持使用二維曲線（Curve2D）或幾何曲線集（GeometricCurveSet）類型的2 D幾何表示。通過對子空間的邊界和子空間內部的家具等障礙物進行采樣，生成二維有界圖形，以供 Delaunay三角剖分細化算法生成非結構化網格。

1.4.1.2 計算限定Delaunay三角細化剖分

將上一步采集的內外邊界輸入限定 Delaunay三角剖分細化算法，其所創(chuàng)建的三角形與一般三角剖分算法相比，除了具有內外邊界的約束，還避免了細長的三角形。限定 Delaunay三角剖分細化算法適用于具有各種不規(guī)則形狀的室內空間，并且均勻覆蓋于區(qū)域空間中，提高了幾何精度。

1.4.1.3 選取路徑點

經過細化剖分處理后，子空間被描述為更加準確、尺度更小的空間區(qū)域。在這些細化的剖分區(qū)域中進行移動，根據剖分區(qū)域中的拓撲關系，需要明確每個小區(qū)域中下一個路徑點的方位，而剖分所得的三角形無法直接作為路徑點，所以應選取合適的特征點作為路徑點。路徑點的選擇通常為剖分后的小三角形的重心或者邊上的中點?？紤]到在走廊等細長空間內若選擇小三角形的重心作為特征點，所生成的路徑為Z字形，需要使用其他算法進行簡化和平滑處理。由于限定 Delaunay三角剖分細化算法的特性，避免了狹長三角形的生成，因此選取子空間內部所有三角形邊的中點為路徑點，能較大程度避免路基的彎折，此外路徑點不能位于外部或者內部限制邊界上。

1.4.1.4 鏈接路徑點

根據三角形與邊界的關系，確定路徑的鏈接方法，路徑點只鏈接至與其相鄰的三角形上的路徑點。路徑點的鏈接主要通過建立BSP樹結構來實現(xiàn)，算法步驟如下。

（1）以子空間中位于左下角的路徑點作為根節(jié)點，其所在的三角形為源三角形，與其共享邊的鄰接三角形為子樹，判斷鄰接三角形除源三角形是否還存在鄰接三角形。

（2）若除源三角形外無其他鄰接三角形，則說明其為規(guī)則矩形，未進行細化剖分，只保留其共享邊上的路徑點。

（3）若除源三角形還存在一個或兩個鄰接三角形，則將鄰接三角形上共邊的中點插入BSP樹中，與根節(jié)點鏈接。

（4）從根節(jié)點開始，根據共邊判斷鄰接三角形與源三角形的前后關系，前則遍歷左子樹，后則遍歷右子樹，遍歷所有結構化三角形，最終形成子空間內完整的路徑網絡。

由圖2可見，路徑點①、②、③、④、⑤所在的分割平面將房間分割成A、B、C、D、E、F 6個區(qū)域，以①作為根節(jié)點，遍歷相鄰的分割平面，得到所有可能的BSP結構樹，從而對各路徑點進行鏈接。由圖3可見，此方法同樣適用于狹長的的走廊，能夠較為完整地反映出可供通行的導航網絡路徑。

1.4.2 生成非水平路徑

非水平路徑是沿著樓梯、電梯等進行跨樓層通行的路徑。對于樓梯，采用提取第一級踏步、最后一級踏步和休息平臺的特征點，通過特征點的連接形成與樓梯幾何特征一致的非水平路徑。對于電梯，通常在BIM模型中只會構建電梯井來表示，在各樓層樓板上進行開口，所以通過提取電梯井的平面投影的重心，將所獲得的樓層高度作為z坐標依次賦予重心，并連接這些點形成電梯路徑。

2 室內導航網絡構建與分析

2.1 網絡數(shù)據集的構建

為了驗證本文提出的基于BIM模型的室內導航網絡構建方法，本文以南京林業(yè)大學教學主樓為試驗對象（圖4），采用以REVIT建模的BIM模型作為數(shù)據來源，建立原型系統(tǒng)進行驗證。主要通過Dijkstra算法對所構建的室內導航網絡進行尋徑長度準確性驗證。Dijkstra算法是一種經典的最短路徑尋路算法，通過指定起始點和終止點來快速求解最短路徑。Dijkstra算法的基本原理是在路網中每次找到離起始點最近的一個路徑點，然后以起始點為中心，向外層層拓展，直至終止點處（圖5）。

2.2 路徑理論值與實際值之間的誤差分析

隨機選取試驗區(qū)域中6條路線的理論值與實地測量的實際值之間的誤差進行數(shù)據分析，根據計算得到統(tǒng)計數(shù)據見表1。

由表1可知，本實驗體現(xiàn)出采用三角剖分的幾何網絡較靈活、尋路效率較高的特點，適用于大型開放空間。由于其剖分特性，可能會提供不符合實際的彎折導航路徑，從而導致路徑規(guī)劃時所產生的誤差，且誤差隨著路徑長度的增加而增加。但模型中的幾何網絡長度相對于實地測量的路線長度的平均誤差基本在3%以內， 此方法生成的室內導航網絡的準確性基本滿足室內導航的需求。如何優(yōu)化導航網絡的幾何精度將在以后的研究中加以改進。

3 結束語

本文基于BIM模型數(shù)據，通過提取語義信息、幾何信息和拓撲關系建立對偶模型，利用限定 Delaunay三角剖分細化算法對子空間進行剖分，探索了考慮真實室內環(huán)境導航幾何網絡的構建方法，從而為基于室內位置信息的導航服務提供可靠的數(shù)據來源。試驗表明，這種室內導航網絡構建方法不僅能提供較高的幾何網絡精度，且能提供豐富語義信息給路徑規(guī)劃作為參考。隨著室內定位技術的發(fā)展及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]盧偉，魏峰遠，張碩，等. 室內路網模型的構建方法研究與實現(xiàn)[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.