室內路網模型的構建方法研究與實現

盧 偉，魏峰遠，張 碩，索榮遙

(1.河南理工大學 測繪與國土信息工程學院，河南 焦作 454003；2.北京博陽世通信息技術有限公司，北京 100101)

1 引言

隨著城市變化突飛猛進，高大的建筑物不斷增加，而且越來越多樣化，室內導航以及基于位置的服務(location-based service，LBS)顯得越來越重要[1-2]。室內路網模型的建立可以幫助人們在一些陌生或復雜的室內環境中(例如飛機場、會議室、展覽廳、企業、醫院、博物館等室內區域)，用最短的時間，走最短的路，辦最快的事。目前室外導航技術已相當成熟，如車載導航、手機導航、PDA手持導航等，這些均采用全球定位系統(global positioning system，GPS)衛星信號進行定位，通過結合相關的電子地圖和導航軟件完成位置服務。室內導航與室外導航在某些技術方面存在很多不同點，如定位技術、路網數據構建等。近年來，對室內導航系統及關鍵技術的研究逐漸興起，如室內移動導航系統的路徑規劃方法研究[3]、室內精確定位導航系統的設計與實現[4]、位置服務中面向路網的位置匿名技術研究與實現[5]等。但目前針對室內路徑點獲取及路網模型構建方面的研究仍處于起步階段，沒有形成一套完整、規范的建模流程。如何確定室內路徑點并建立路網模型是信號源部署和室內導航的基礎環節，具有非常重要的現實意義。

2 概述

2.1 室內位置信息圖

室內位置信息圖，是指反映室內空間信息布局情況的空間信息圖，該圖既簡潔地描述了周圍環境又包含了足夠的信息量[3]。

建筑物內部的結構物(又可稱為障礙物，如墻體、走廊、展覽臺、墻壁壁畫、桌椅等)，將整個室內空間劃分成房間、公共場所以及可以進入、不可直接進入的區域。室內物體的形狀基本上都可近似看成規則圖形(如圓形、長方形、三角形等)，所以在構造室內位置信息圖時，可以用點線連接形式表達空間布局信息。具體方法是將空間存在相互連接的地方表示成點的形式，并按每個物體與房間的比例大小，將其表示成直線段、三角形、四邊形等點線形狀。

(1)節點，如橫、豎墻壁交接處為一個節點；門與墻的連接處為兩個節點。

(2)直線段，如較小物體，表示成直線段；對于不可進入或不能直接進入的區域，以直線段表示其邊界。

(3)三角形，如形狀近似為三角形的物體，三條邊為不能穿越的部分。

(4)四邊形，如較大物體，將其近似成四邊形；圓形物體，取圓的外切四邊形表示，四條邊線為不可穿越的部分。

2.2 Delaunay三角網剖分

Delaunay(簡稱DT)三角網剖分方法屬于生成非結構化網格[6-7]的方法，這類方法逐步成為目前最流行的全自動網格生成方法之一，其對于區域邊界線和內部媒質分界線形狀不規則的情況以及場的分布變化較大的情況都能較好的適應。

Delaunay三角網剖分是前蘇聯數學家Delaunay在1934年提出的：對于任意給定的平面點集，只存在著唯一的一種三角網剖分方法，滿足所謂的“最大化最小角”優化準則，即所有最小內角之和最大。這種剖分方法遵循“空外接圓”和“最小角最大”準則，因此，在各種二維三角網剖分[8-10]中，只有Delaullay三角網剖分才同時滿足全局和局部最優，特別適用于有限元分析應用中的網格生成，獲得性能優良、形狀最佳的三角形單元。

3 室內路網模型的構建方法

3.1 室內空間區域剖分

實際建立室內路網模型時要合理地建立路徑，并不需要對整個室內空間區域進行剖分，這樣既可以保證路網的完整，又能有效地減少工作量。根據室內空間布局的用途將室內環境分為兩部分，一是無需剖分區域，如走廊、衛生間、小型房間、無障礙物直接可達的房間等，用簡單的直線段連接成路徑，即為最短路徑；二是需要剖分區域，如博物館展覽大廳、機場大廳、商場房間等大型室內環境存在障礙物，則必須進行空間區域剖分，使構建的路徑可以避開障礙物且盡量滿足最短條件。

以圖1所示的展廳(26.5 m×16.5 m)布局為例，根據構造室內位置信息圖的思想，對展廳實現空間描述，將圖1(a)環境圖中的墻體、門、展臺等室內物體信息轉換成相應的坐標位置，用點線方式表示，如圖1(b)。

圖1 展廳

其中，A1A2、A3A4、A5A6和A7A8分別表示門，Wl、W2、W3分別表示位于房間內部的障礙物。因為構建網路模型時僅考慮障礙物所在位置的可達性，所以房間四周的物體可忽略。

室內位置信息圖建立起來之后，要對由障礙物圍成的空間進行剖分處理，以便選取路徑點。具體的室內空間區域剖分方法是：在ArcGIS中用整個空間區域的散點集，即圖1(b)中J1-J25表示共25個結點，創建TIN不規則三角網，該三角網滿足Delaunay三角網原則，剖分結果如圖2(a)所示。但在ArcGIS中創建TIN不規則三角網時，軟件默認的剖分區域為散點集的外圍區域，所以當剖分區域為凸多邊形時，可完美剖分，得到室內空間區域剖分圖；當剖分區域為凹多邊形時，會出現多余剖分，需要人工進行刪除處理，得到室內空間區域剖分圖，如圖2(b)所示。

圖2 室內空間區域剖分圖

3.2 路徑點的選取

經過剖分處理后的室內空間被更加細化、準確描述成小的空間區域。在這些小空間區域中移動時，需要明確下一步的方向和位置，而剖分后的小區域無法直接用作移動路徑的點，所以需要對路徑點進行選取。

路徑點的選取方法是：將Delaunay三角網剖分后的各空間區域量化表示成路徑點，即選擇剖分后的小區域(三角形)的一個特征點(如重心、內心等)作為該小區域的表示，只要在該小區域內部范圍內，均用這個特征點表示路徑點。

特征點的選取原則：所有三角形都存在這樣的特征點，該點最好分布于三角形的內部，其特征明顯且容易獲得。

圖3 三角形的重心

考慮以上選取原則與實際計算的復雜性，綜合ArcGIS軟件中“Feature To Point”的判斷轉點方法，于是選擇三角形的重心作為其特征點。

三角形的重心：是三角形三邊中線的交點。如圖3，設三角形的三個頂點坐標分別為A(x1,y1)、B(x2,y2)，C(x3,y3)，則其重心的坐標如式(1)所示計算：

(1)

遍歷圖中全部剖分形成的三角形(29個)之后并按照以式(1)計算，得到各小區域的重心，作為構建路網模型的路徑點(L1-L29表示29個路徑點)，如圖4所示。

圖4 路徑點的選取

3.3 路徑的建立與優化

路徑的建立方法：將空間區域量化成的路徑點(如圖4上的點L1-L29)連接起來構成的線段來表示各個區域之間可以通行的路徑，配合ArcGIS進行二次開發來完成路徑的建立與優化。在忽略障礙物存在的情況下，路徑點之間的位置關系共可以構建406條連接線，如圖5所示。

圖5 路徑的建立

分析存在障礙物的情況，必須對圖5(b)進行適當處理，增加構建路徑的限制條件。本文選用以下限制條件來進行路徑的篩選與優化：

(1)路徑間的可取代性

相鄰路徑點的連線距離最短。但在構建路徑時，一些非相鄰路徑點的連線距離(如圖6中c的值)可以近似等于相鄰路徑點的連線距離之和(如圖6中a+b的值)，從而產生大量近似可以替代的路徑，浪費存儲空間。

圖6 三角形 判斷法

本文采用三角形判斷法，如圖6所示，通過設定參量σ作為參考值進行路徑的刪減。其中圖上A、B、C為路徑點，ɑ、b、c分別代表路徑點之間的路徑。

路徑間的可取代性判斷式：

(2)

若滿足式(2)中的條件，則路徑c可以被取代，即刪除路徑c，保留路徑ɑ、b。σ的選值根據實際應用需求而定，本文取σ=0，0.02和0.05的情況進行分析。

(2)障礙物與路徑的位置關系

若路徑與表示障礙物的結點連線相交或超出剖分區域，則刪除該路徑。為了更加精確、細致的構建路網，本文取“路徑與障礙物實際區域是否相交”為限制條件，進行路徑的刪減。

根據上述兩個限制條件，當σ=0時，路徑點連線減少到189條，如圖7(a)；當σ=0.02時，路徑點連線減少到91條，如圖7(b)；當σ=0.05時，路徑點連線可繼續減少到80條，如圖7(c)。

圖7 避開障礙物的路徑圖

3.4 路網模型的構建與實現

(1)網絡數據集的創建

將σ=0，0.02和0.05時的路徑，分別在ArcCatalog中進行網絡數據集的創建(New Network Dataset)，在ArcMap中打開時的表現如圖8(c)所示。

圖8 A1A2→A3A4的最短路線

如圖8所示，當從門A1A2出發到達門A3A4時，需要避開障礙物W1，圖中的粗線表示三種情況下A1A2與A3A4之間的最短路線。

(2)路徑理論值與實際值之間的誤差分析

選取實驗區域中10條路線的理論值與實際值之間的誤差進行數據分析，根據計算，得到數據統計表1。

表1 距離數據統計表

其中，S0表示起始點與目的點之間的最短距離理論值；S0.02、S0.05表示當σ=0.02、σ=0.05構建路徑時起始點到目的點所用距離實際值；ε0.02、ε0.05表示當σ=0.02、σ=0.05時路徑距離實際值與理論值之間的差值。

(3)對路網進行配準

將建立好的網絡數據集路網導入ArcMap中，找到與室內地圖中實驗區域相對應的三個角點，將其坐標改成之前記錄的值，對路網進行配準，如圖9(a)，完成路網模型的構建。以系統Web版為測試平臺，加載制作好的室內地圖及路網模型，在地圖上選取起始點，自動生成最優路徑操作，其效果圖如圖9(b)所示。另外，還可以對地圖進行拖拽等操作。

圖9 室內地圖及路網模型

4 結語

本文根據對室內環境的空間結構分析，建立了室內位置信息圖，并在此基礎上結合Delaunay三角網剖分思想，探索了室內空間區域剖分方法，實現了從路徑點獲取到路網模型構建的全過程處理。實驗表明，這種室內路網模型構建方法可行、有效。隨著人們對室內移動位置服務需求的增加，室內路網模型的構建將成為一項基礎且關鍵的任務。本文提出的室內路網模型構建方法是針對二維的空間信息圖進行相應的表示與處理，雖然可以為室內路網制作和位置服務應用開發提供借鑒，但過程中丟失了部分信息如室內部分高度等。如何針對三維室內環境進行詳細的描述與分析，建立路網模型是下一步的研究方向。

[1] 余濤，余彬.位置服務[M].北京：機械工業出版社，2005.

[2] WANG Shu，MIN J W，YI B K.Location Based Services for Mobiles：Technologies and Standards[EB/OL].[2014-08-02].http：//mobile-location-services.googlecode.com/svn-history/r44/trunk/Reference/ICC2008LBSforMobilessimplifiedR2.pdf.

[3] 徐靜.室內移動導航系統的路徑規劃方法研究[D].長春：長春理工大學，2009.

[4] 楊德軍.室內精確定位導航系統的設計與實現[D].北京：北京郵電大學，2011.

[5] 鄭準永.位置服務中面向路網的位置匿名技術研究與實現[D].大連：大連理工大學，2013.

[6] STEVEN J.OWEN.A Survey of Unstructured Mesh Generation Technology[EB/OL].[2014-08-02].http：//ima.udg.edu/～sellares/ComGeo/OwenSurv.pdf.

[7] 陳建軍.非結構化網格生成及其并行化的若十問題研究[D].杭州：浙江大學，2006.

[8] CHEN Hao，BISHO P J.Delaunay Triangulation for Curved Surfaces[C]//Proceedings of the 6th International Meshing Roundtable.Park City：[s.n.]，1997：115-127.

[9] 武曉波，王世新.Delaunay三角網的生成算法研究[J].測繪學報，1999.28(1)：28-35.

[10] 賀全兵，黎貴友，文進.生成Delaunay三角網的改進算法[J].計算機與數字工程，2005.8(34)：50-52.