盧 偉，魏峰遠(yuǎn)，張 碩，索榮遙

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

1 引言

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

2 概述

2.1 室內(nèi)位置信息圖

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

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

(1)節(jié)點(diǎn)，如橫、豎墻壁交接處為一個(gè)節(jié)點(diǎn)；門與墻的連接處為兩個(gè)節(jié)點(diǎn)。

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

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

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

2.2 Delaunay三角網(wǎng)剖分

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

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

3 室內(nèi)路網(wǎng)模型的構(gòu)建方法

3.1 室內(nèi)空間區(qū)域剖分

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

以圖1所示的展廳(26.5 m×16.5 m)布局為例，根據(jù)構(gòu)造室內(nèi)位置信息圖的思想，對展廳實(shí)現(xiàn)空間描述，將圖1(a)環(huán)境圖中的墻體、門、展臺等室內(nèi)物體信息轉(zhuǎn)換成相應(yīng)的坐標(biāo)位置，用點(diǎn)線方式表示，如圖1(b)。

圖1 展廳

其中，A1A2、A3A4、A5A6和A7A8分別表示門，Wl、W2、W3分別表示位于房間內(nèi)部的障礙物。因?yàn)闃?gòu)建網(wǎng)路模型時(shí)僅考慮障礙物所在位置的可達(dá)性，所以房間四周的物體可忽略。

室內(nèi)位置信息圖建立起來之后，要對由障礙物圍成的空間進(jìn)行剖分處理，以便選取路徑點(diǎn)。具體的室內(nèi)空間區(qū)域剖分方法是：在ArcGIS中用整個(gè)空間區(qū)域的散點(diǎn)集，即圖1(b)中J1-J25表示共25個(gè)結(jié)點(diǎn)，創(chuàng)建TIN不規(guī)則三角網(wǎng)，該三角網(wǎng)滿足Delaunay三角網(wǎng)原則，剖分結(jié)果如圖2(a)所示。但在ArcGIS中創(chuàng)建TIN不規(guī)則三角網(wǎng)時(shí)，軟件默認(rèn)的剖分區(qū)域?yàn)樯Ⅻc(diǎn)集的外圍區(qū)域，所以當(dāng)剖分區(qū)域?yàn)橥苟噙呅螘r(shí)，可完美剖分，得到室內(nèi)空間區(qū)域剖分圖；當(dāng)剖分區(qū)域?yàn)榘级噙呅螘r(shí)，會出現(xiàn)多余剖分，需要人工進(jìn)行刪除處理，得到室內(nèi)空間區(qū)域剖分圖，如圖2(b)所示。

圖2 室內(nèi)空間區(qū)域剖分圖

3.2 路徑點(diǎn)的選取

經(jīng)過剖分處理后的室內(nèi)空間被更加細(xì)化、準(zhǔn)確描述成小的空間區(qū)域。在這些小空間區(qū)域中移動(dòng)時(shí)，需要明確下一步的方向和位置，而剖分后的小區(qū)域無法直接用作移動(dòng)路徑的點(diǎn)，所以需要對路徑點(diǎn)進(jìn)行選取。

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

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

圖3 三角形的重心

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

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

(1)

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

圖4 路徑點(diǎn)的選取

3.3 路徑的建立與優(yōu)化

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

圖5 路徑的建立

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

(1)路徑間的可取代性

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

圖6 三角形 判斷法

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

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

(2)

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

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

若路徑與表示障礙物的結(jié)點(diǎn)連線相交或超出剖分區(qū)域，則刪除該路徑。為了更加精確、細(xì)致的構(gòu)建路網(wǎng)，本文取“路徑與障礙物實(shí)際區(qū)域是否相交”為限制條件，進(jìn)行路徑的刪減。

根據(jù)上述兩個(gè)限制條件，當(dāng)σ=0時(shí)，路徑點(diǎn)連線減少到189條，如圖7(a)；當(dāng)σ=0.02時(shí)，路徑點(diǎn)連線減少到91條，如圖7(b)；當(dāng)σ=0.05時(shí)，路徑點(diǎn)連線可繼續(xù)減少到80條，如圖7(c)。

圖7 避開障礙物的路徑圖

3.4 路網(wǎng)模型的構(gòu)建與實(shí)現(xiàn)

(1)網(wǎng)絡(luò)數(shù)據(jù)集的創(chuàng)建

將σ=0，0.02和0.05時(shí)的路徑，分別在ArcCatalog中進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)集的創(chuàng)建(New Network Dataset)，在ArcMap中打開時(shí)的表現(xiàn)如圖8(c)所示。

圖8 A1A2→A3A4的最短路線

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

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

選取實(shí)驗(yàn)區(qū)域中10條路線的理論值與實(shí)際值之間的誤差進(jìn)行數(shù)據(jù)分析，根據(jù)計(jì)算，得到數(shù)據(jù)統(tǒng)計(jì)表1。

表1 距離數(shù)據(jù)統(tǒng)計(jì)表

其中，S0表示起始點(diǎn)與目的點(diǎn)之間的最短距離理論值；S0.02、S0.05表示當(dāng)σ=0.02、σ=0.05構(gòu)建路徑時(shí)起始點(diǎn)到目的點(diǎn)所用距離實(shí)際值；ε0.02、ε0.05表示當(dāng)σ=0.02、σ=0.05時(shí)路徑距離實(shí)際值與理論值之間的差值。

(3)對路網(wǎng)進(jìn)行配準(zhǔn)

將建立好的網(wǎng)絡(luò)數(shù)據(jù)集路網(wǎng)導(dǎo)入ArcMap中，找到與室內(nèi)地圖中實(shí)驗(yàn)區(qū)域相對應(yīng)的三個(gè)角點(diǎn)，將其坐標(biāo)改成之前記錄的值，對路網(wǎng)進(jìn)行配準(zhǔn)，如圖9(a)，完成路網(wǎng)模型的構(gòu)建。以系統(tǒng)Web版為測試平臺，加載制作好的室內(nèi)地圖及路網(wǎng)模型，在地圖上選取起始點(diǎn)，自動(dòng)生成最優(yōu)路徑操作，其效果圖如圖9(b)所示。另外，還可以對地圖進(jìn)行拖拽等操作。

圖9 室內(nèi)地圖及路網(wǎng)模型

4 結(jié)語

本文根據(jù)對室內(nèi)環(huán)境的空間結(jié)構(gòu)分析，建立了室內(nèi)位置信息圖，并在此基礎(chǔ)上結(jié)合Delaunay三角網(wǎng)剖分思想，探索了室內(nèi)空間區(qū)域剖分方法，實(shí)現(xiàn)了從路徑點(diǎn)獲取到路網(wǎng)模型構(gòu)建的全過程處理。實(shí)驗(yàn)表明，這種室內(nèi)路網(wǎng)模型構(gòu)建方法可行、有效。隨著人們對室內(nèi)移動(dòng)位置服務(wù)需求的增加，室內(nèi)路網(wǎng)模型的構(gòu)建將成為一項(xiàng)基礎(chǔ)且關(guān)鍵的任務(wù)。本文提出的室內(nèi)路網(wǎng)模型構(gòu)建方法是針對二維的空間信息圖進(jìn)行相應(yīng)的表示與處理，雖然可以為室內(nèi)路網(wǎng)制作和位置服務(wù)應(yīng)用開發(fā)提供借鑒，但過程中丟失了部分信息如室內(nèi)部分高度等。如何針對三維室內(nèi)環(huán)境進(jìn)行詳細(xì)的描述與分析，建立路網(wǎng)模型是下一步的研究方向。

[1] 余濤，余彬.位置服務(wù)[M].北京：機(jī)械工業(yè)出版社，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] 徐靜.室內(nèi)移動(dòng)導(dǎo)航系統(tǒng)的路徑規(guī)劃方法研究[D].長春：長春理工大學(xué)，2009.

[4] 楊德軍.室內(nèi)精確定位導(dǎo)航系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京郵電大學(xué)，2011.

[5] 鄭準(zhǔn)永.位置服務(wù)中面向路網(wǎng)的位置匿名技術(shù)研究與實(shí)現(xiàn)[D].大連：大連理工大學(xué)，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] 陳建軍.非結(jié)構(gòu)化網(wǎng)格生成及其并行化的若十問題研究[D].杭州：浙江大學(xué)，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三角網(wǎng)的生成算法研究[J].測繪學(xué)報(bào)，1999.28(1)：28-35.

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