一種全球離散格網(wǎng)系統(tǒng)框架下的室內(nèi)空間網(wǎng)格數(shù)據(jù)模型

鄔群勇，曾慶權(quán)，張愛國

一種全球離散格網(wǎng)系統(tǒng)框架下的室內(nèi)空間網(wǎng)格數(shù)據(jù)模型

鄔群勇1,2，曾慶權(quán)1,2,3，張愛國3

（1. 福州大學(xué)空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室/衛(wèi)星空間信息技術(shù)綜合應(yīng)用國家地方聯(lián)合工程研究中心，福州 350108；2. 數(shù)字中國研究院（福建），福州 350003；3. 廈門理工學(xué)院 計算機與信息工程學(xué)院，福建 廈門 361024）

針對室內(nèi)外數(shù)據(jù)模型兼容性低，室內(nèi)模型缺乏統(tǒng)一空間參考框架的問題，提出1種全球離散格網(wǎng)框架下的室內(nèi)空間網(wǎng)格模型：室內(nèi)模型通過引入全球離散格網(wǎng)系統(tǒng)（DGGS）作為坐標(biāo)參考系統(tǒng)提供位置編碼信息，并將DGGS作為模型的幾何結(jié)構(gòu)基礎(chǔ)對室內(nèi)空間離散化；然后以離散空間網(wǎng)格作為基本組織單元，對模型的類型系統(tǒng)進(jìn)行設(shè)計；最后利用格網(wǎng)系統(tǒng)的層次結(jié)構(gòu)與網(wǎng)格索引特性完成基于A*算法的室內(nèi)路徑規(guī)劃。實驗結(jié)果表明，該模型具有在統(tǒng)一框架下空間規(guī)劃計算的可行性和有效性。

空間參考框架；全球離散格網(wǎng)；位置編碼；室內(nèi)模型；路徑規(guī)劃

0 引言

近年來，地理信息科學(xué)的研究與應(yīng)用范圍逐漸由宏觀的室外環(huán)境向復(fù)雜多樣化的室內(nèi)空間拓展[1]。室內(nèi)定位技術(shù)與室外空間標(biāo)準(zhǔn)不兼容導(dǎo)致應(yīng)用場景相互隔離。相比室外空間數(shù)據(jù)模型，室內(nèi)空間數(shù)據(jù)模型中的技術(shù)參數(shù)、數(shù)據(jù)類型更多樣化，存在更復(fù)雜的空間約束。所以如何構(gòu)建室內(nèi)外一體化數(shù)據(jù)模型成為當(dāng)前研究的重要方向之一。

國內(nèi)外主流室內(nèi)空間數(shù)據(jù)模型大致可分為基于幾何、符號的數(shù)據(jù)模型以及混合模型[2]。其中幾何模型重視室內(nèi)空間的平面結(jié)構(gòu)與可視化，具有嚴(yán)格遵循的量化標(biāo)準(zhǔn)[3-4]，被廣泛應(yīng)用在各個領(lǐng)域。幾何模型主要有基于幾何邊界的模型和室內(nèi)網(wǎng)格模型。室內(nèi)網(wǎng)格模型通過對室內(nèi)空間網(wǎng)格化，以網(wǎng)格為單元記錄室內(nèi)空間位置、導(dǎo)航信息等數(shù)據(jù)[5]。文獻(xiàn)[6]通過對室內(nèi)空間進(jìn)行六邊形格網(wǎng)化，對每個格網(wǎng)引入人流量、地標(biāo)可視度等參數(shù)，利用六邊形各向同性的特點設(shè)計實現(xiàn)多約束A*算法的數(shù)據(jù)模型。文獻(xiàn)[7]則設(shè)計了1種基于網(wǎng)格的室內(nèi)通行模型，并提出基于通行區(qū)域的模型自動提取算法。在具有室外拓展能力的室內(nèi)空間數(shù)據(jù)模型研究中，通常直接將室內(nèi)網(wǎng)絡(luò)與室外路網(wǎng)結(jié)合，其中多數(shù)室內(nèi)空間數(shù)據(jù)模型為幾何網(wǎng)絡(luò)模型（geometric network model, GNM）[8-9]，采用本地坐標(biāo)或無空間參考系統(tǒng)。其生成的室內(nèi)外導(dǎo)航路網(wǎng)能夠快速有效地求解最優(yōu)路徑，但缺乏更多樣的應(yīng)用場景，如室內(nèi)定位數(shù)據(jù)，工業(yè)機器人行動概率數(shù)據(jù)等的存儲。對于無空間參考系統(tǒng)的問題，文獻(xiàn)[10]利用全球經(jīng)緯度剖分網(wǎng)格作為定位參照系統(tǒng)，輔助行人航跡推算進(jìn)行室內(nèi)外一體化定位。

全球離散格網(wǎng)系統(tǒng)（discrete global grid system, DGGS）[11]作為1種地球擬合格網(wǎng)，對球體進(jìn)行高度細(xì)分，形成形狀近似、空間無縫、尺度連續(xù)的多層次網(wǎng)格[12]。這種特性為分布不均勻、精度不一的空間數(shù)據(jù)分享、集成等提供了統(tǒng)一的模式。其次，DGGS將地表細(xì)分為大小一致的格網(wǎng)單元，數(shù)據(jù)能夠以地理位置的形式進(jìn)行檢索，格網(wǎng)單元的編碼也更適合計算機進(jìn)行數(shù)據(jù)檢索存儲等操作運算[13]。本文在DGGS的基礎(chǔ)上，關(guān)注具有統(tǒng)一空間參考框架的室內(nèi)空間數(shù)據(jù)組織研究，提出1種基于DGGS的室內(nèi)空間格網(wǎng)模型（indoor global grid model, IGGM）。該模型以格網(wǎng)作為空間基本單元整合導(dǎo)航定位及空間語義等數(shù)據(jù)，實現(xiàn)室內(nèi)空間幾何特性等的統(tǒng)一表達(dá)。模型利用DGGS對室內(nèi)空間進(jìn)行規(guī)則剖分，得到具有全局位置信息的室內(nèi)離散空間，統(tǒng)一區(qū)域內(nèi)模型空間參考框架。全球離散格網(wǎng)系統(tǒng)天然地具有層次結(jié)構(gòu)與網(wǎng)格索引特性，可以有效解決不同場景下的多粒度需求，為模型提供了室內(nèi)距離計算、路徑規(guī)劃等空間計算基礎(chǔ)。

在應(yīng)用DGGS的過程中，值得注意的一點是全球尺度的格網(wǎng)方案能否滿足大比例下的空間模型設(shè)計。部分學(xué)者認(rèn)為全球離散格網(wǎng)本意既是將連續(xù)數(shù)量關(guān)系建立的地球空間模型離散化，多數(shù)DGGS采用了1984世界大地坐標(biāo)系(world geodetic coordinate system 1984,WGS84）作為地球信息度量空間的科學(xué)模型[14]，基于DGGS的小尺度空間模型完全構(gòu)建在虛擬橢球體這一度量空間上，所以室內(nèi)空間模型需要滿足的定位精度完全取決于建模所用數(shù)據(jù)精度。在進(jìn)行室內(nèi)空間格網(wǎng)模型設(shè)計中需要均勻大小的格網(wǎng)系統(tǒng)作為模型數(shù)據(jù)離散化的基礎(chǔ)，而DGGS在剖分過程中因地球為近似橢球體，導(dǎo)致不同位置下格網(wǎng)單元變形不均，變形總體呈現(xiàn)趨勢為隨著格網(wǎng)系統(tǒng)分辨率的增加而減小。文獻(xiàn)[15]指出在27 km以下的球面剖分，可將其視為平面，相應(yīng)層次內(nèi)格網(wǎng)單元變形能夠滿足應(yīng)用需求。

本文基于數(shù)學(xué)工具“2階基調(diào)[16]”進(jìn)行數(shù)據(jù)模型設(shè)計與形式化定義，設(shè)計模型相關(guān)類型組成及查詢操作，基于該模型與DGGS設(shè)計空間計算函數(shù)和語義查詢函數(shù)。

1 IGGM模型形式化定義

基于2階基調(diào)定義的數(shù)據(jù)模型能夠直接有效地在關(guān)系型數(shù)據(jù)庫中實現(xiàn)對應(yīng)的數(shù)據(jù)模型。該工具通過給出類別和類型的構(gòu)造聲明及底層的類型操作函數(shù)，使得數(shù)據(jù)模型尤其是時空數(shù)據(jù)模型的結(jié)構(gòu)更為樸素與嚴(yán)謹(jǐn)。

基于全球離散格網(wǎng)的室內(nèi)空間數(shù)據(jù)模型的形式化定義為

IGGM = (,,)（1）

式中：在模型中代表空間元素集，由所有不同元素組成，基于元素的數(shù)據(jù)表存儲了關(guān)于室內(nèi)空間對象的語義信息；為模型元素、格網(wǎng)間的操作算子；則是由格網(wǎng)單元組成的室內(nèi)格網(wǎng)集，其中包含了細(xì)膩的幾何關(guān)系與屬性數(shù)據(jù)；IGGM的數(shù)據(jù)類型為Iggm。

IGGM的格網(wǎng)結(jié)構(gòu)圖如圖1所示：模型構(gòu)建在DGGS之上，利用DGGS的幾何結(jié)構(gòu)組成室內(nèi)格網(wǎng)集，并將格網(wǎng)集進(jìn)行組織設(shè)計形成描述空間元素幾何信息的基本幾何體（點、線、區(qū)域），同數(shù)據(jù)庫基本數(shù)據(jù)類型如字符串、數(shù)字、時間格式、日期格式等組成模型的類型系統(tǒng)。而DGGS中由格網(wǎng)拓?fù)潢P(guān)系設(shè)計的函數(shù)集則作為另一重要組成部分被封裝為操作算子。

圖1 IGGM結(jié)構(gòu)

1.1 IGGM幾何框架

IGGM模型由格網(wǎng)系統(tǒng)構(gòu)成格網(wǎng)單元、格網(wǎng)線和格網(wǎng)面3種基本幾何體。模型中不同的空間元素由對應(yīng)的幾何體構(gòu)成，并以此為單位保存相關(guān)語義屬性。

格網(wǎng)點為模型的最基本單元，與DGGS中提取的室內(nèi)格網(wǎng)集的格網(wǎng)單元一一對應(yīng)。1個室內(nèi)格網(wǎng)點（interior grid，IG）為1個4元組，即

格網(wǎng)線是由格網(wǎng)單元進(jìn)行排列組合而成的線幾何體，用于表示墻體、圍欄、邊界、門等空間元素。1條由多個格網(wǎng)單元組成的1維列表結(jié)構(gòu)的格網(wǎng)線定義為

式中IG為形成格網(wǎng)線的格網(wǎng)點。

室內(nèi)格網(wǎng)面（區(qū)域）由格網(wǎng)點組成，室內(nèi)房間以及聯(lián)通區(qū)域都需要使用室內(nèi)區(qū)域?qū)ζ溥M(jìn)行描述。1個室內(nèi)網(wǎng)格面IREGION是由多個網(wǎng)格單元組成，其定義為

1.2 IGGM的類型系統(tǒng)

對模型類型系統(tǒng)而言，類別主要包含了IDENT、DATA、TIME、INGEO、CONS、STATE、ELEM、IGGM。其中IDENT為標(biāo)識符、DATA為基本數(shù)據(jù)類型集合、TIME為時間類型集合如（day、time等）、INGEO為基本幾何體，CONS為約束條件類型集合；STATE則代表狀態(tài)類型集合， ELEM對應(yīng)空間元素類型集合，IGGM代表室內(nèi)規(guī)則格網(wǎng)模型類型。

對室內(nèi)空間模型而言，最重要的1部分即為空間元素。室內(nèi)房間元素的定義由1個3元組構(gòu)成，即

式中：ElemID為元素標(biāo)識符；IReg為構(gòu)成元素的格網(wǎng)面；ThemDes對應(yīng)字符串類型，用于保存元素主題、關(guān)鍵字等。

室內(nèi)墻元素的定義由3元組構(gòu)成，即

式中ILine為構(gòu)成元素的格網(wǎng)線。

室內(nèi)靜態(tài)物元素的定義由3元組構(gòu)成，即

室內(nèi)門元素的定義由4元組構(gòu)成，即

式中Dcons為約束信息，通過對時間約束和元素間通行狀態(tài)進(jìn)行組合，表達(dá)不同時間段，由門元素連接的空間元素通行狀態(tài)。

室內(nèi)出口元素的定義由4元組構(gòu)成，即

式中Econs為出口約束信息，表示在約束條件下出口元素的通行狀態(tài)。

1.3 模型的操作算子定義

模型操作算子由類別基調(diào)描述，主要有空間屬性操作算子、拓?fù)洳僮魉阕?、幾何操作算子和空間規(guī)劃操作算子。利用算子對數(shù)據(jù)進(jìn)行操作，結(jié)合控制過程能夠滿足多種應(yīng)用需求。

空間屬性操作主要基于幾何體進(jìn)行相關(guān)空間屬性等信息的查詢，主要有：根據(jù)點數(shù)據(jù)的經(jīng)緯度坐標(biāo)確定所在格網(wǎng)單元的操作算子（GeoToGrid）；確定格網(wǎng)單元所在空間元素（GridToElem）；確定格網(wǎng)中心經(jīng)緯度（GridCenter）；路徑長度計算（IlineLength）；格網(wǎng)單元距離計算（Distance）；獲得鄰域元素或網(wǎng)格操作（Neighbrhood）。

空間拓?fù)洳僮髦饕?種：包含關(guān)系判斷（Contain），判斷格網(wǎng)單元是否在區(qū)域或線上；鄰接關(guān)系判斷（Adjacent），判斷各基本幾何體的鄰接關(guān)系。

空間幾何操作，主要有幾何體并集（Union）和緩沖區(qū)生成（Buffer）。

空間規(guī)劃操作，主要有最短路徑操作（Shortest-Path）等。

2 基于PostgreSQL的IGGM模型設(shè)計

選擇采用PostgreSQL[17]設(shè)計對應(yīng)數(shù)據(jù)庫數(shù)據(jù)類型與數(shù)據(jù)表，用以描述格網(wǎng)與空間元素數(shù)據(jù)及幾何操作（如表1所示）。其中根據(jù)室內(nèi)空間元素與模型的幾何體設(shè)計了7個數(shù)據(jù)表結(jié)構(gòu)，分別對應(yīng)格網(wǎng)點、格網(wǎng)線、格網(wǎng)區(qū)域、房間、靜態(tài)障礙物、出口、門。每個元素與幾何體的屬性由數(shù)據(jù)表中的字段類型表示，字段數(shù)據(jù)類型為數(shù)據(jù)庫基本類型或復(fù)合類型。

表1 室內(nèi)空間元素與模型幾何體設(shè)計

3 實驗與結(jié)果分析

本文選取某圖書館一層大廳及自習(xí)室周邊作為建模場景（如圖2所示）。該區(qū)域包含大門出口、大廳、自習(xí)室、電梯、玻璃門、走廊、障礙物（桌椅、書柜、柱子等）等空間元素，能充分驗證模型的有效性。

圖2 研究區(qū)域

3.1 室內(nèi)數(shù)據(jù)格網(wǎng)模型構(gòu)建

實例采用的全球離散格網(wǎng)系統(tǒng)為Uber公司的H3格網(wǎng)系統(tǒng)。該格網(wǎng)系統(tǒng)為正二十面體六邊形格網(wǎng)剖分，其基礎(chǔ)多邊形小，投影變形小，網(wǎng)結(jié)構(gòu)具有一致的方向、距離分辨率。該系統(tǒng)具有完備的單元索引及操作函數(shù)，能為模型應(yīng)用提供基礎(chǔ)。

在室內(nèi)數(shù)據(jù)格網(wǎng)模型建模中，不同學(xué)者根據(jù)應(yīng)用場景的特點選擇不同分辨率的格網(wǎng)。用于路徑規(guī)劃的室內(nèi)空間模型通常根據(jù)行人步長或最小制圖單位選擇邊長為1.0~0.5 m的正方形格網(wǎng)分辨率[3,7,10]；概率機器人鄰域根據(jù)機器人大小及傳感器分辨率選用邊長為1.00~0.15 m的正方形格網(wǎng)分辨率[18]。根據(jù)實驗區(qū)域“圖書館”及路徑規(guī)劃的應(yīng)用需求進(jìn)行判斷，網(wǎng)格分辨率大約為行人步長或書架、自習(xí)桌間距，即1.0~0.5 m之間。據(jù)此，使用第15級格網(wǎng)作為格網(wǎng)基本單元，平均六邊形格網(wǎng)單元面積約0.9 m2，邊長約為0.5 m。能夠滿足室內(nèi)數(shù)據(jù)格網(wǎng)模型的構(gòu)建需求。在構(gòu)建過程中，利用操作算子“Geo2Grid”將錨點經(jīng)緯坐標(biāo)轉(zhuǎn)為所在格網(wǎng)標(biāo)識符，將全球離散格網(wǎng)引入室內(nèi)，作為IGGM模型室內(nèi)基礎(chǔ)格網(wǎng)。

選擇實驗區(qū)域輪廓坐標(biāo)，由Region函數(shù)集生成某區(qū)域15級格網(wǎng)的Keyhole 標(biāo)記語言（Keyhole markup language，KML）文件和shp文件。在shp屬性表中添加GeoID、ExitID、StaticID、RoomID、WallID、DoorID字段，并為字段添加對應(yīng)空間元素與幾何體ID。生成格網(wǎng)平面圖，如圖3所示。

圖3 六邊形格網(wǎng)平面圖

導(dǎo)出平面圖數(shù)據(jù)表，障礙物、墻對應(yīng)占用網(wǎng)格，不通行。門、出口、房間對應(yīng)通行區(qū)域。其中門往往作為樞紐網(wǎng)格連通模型中的其余元素，而出口網(wǎng)格則連通另一室內(nèi)外模型。將平面圖數(shù)據(jù)表的不同字段分別轉(zhuǎn)換成不同數(shù)據(jù)庫表中對應(yīng)的csv表格，并采用PostgreSQL GUI工具pgAdmin Ⅲ導(dǎo)入PostgreSQL數(shù)據(jù)庫進(jìn)行存儲和管理。

為證明該數(shù)據(jù)模型具有空間計算能力，本文采用PostgreSQL中的面向存儲過程語言-PL/pgSQL設(shè)計實現(xiàn)基于A*算法的路徑尋找函數(shù)，作為該室內(nèi)空間數(shù)據(jù)模型的空間計算實例。

3.2 基于IGGM模型與A*算法的最短路徑算子

該最短路徑算子的實現(xiàn)基于A*算法并依賴IGGM模型的基本算子Distance與Adjacent進(jìn)行格網(wǎng)操作。具體實現(xiàn)步驟如圖4所示。

圖4 基于IGGM的A*算法流程

第1步，獲得起始節(jié)點、的網(wǎng)格標(biāo)識符。

第2步，初始化模型。加載模型操作算子，聲明相關(guān)變量。

第3步，更新優(yōu)先級隊列及花費列表（CostList），優(yōu)先級列表中存儲待拓展節(jié)點的模型標(biāo)識符及對應(yīng)優(yōu)先級，優(yōu)先級的計算方式()=()+()。()為當(dāng)前節(jié)點至起點的花費Cost。()為當(dāng)前點至終點的六邊形網(wǎng)格距離，由模型算子Distance計算獲得。

第4步，由優(yōu)先級列表中選出優(yōu)先級最高的格網(wǎng)作為當(dāng)前節(jié)點Current，判斷當(dāng)前節(jié)點是否為終點，若是，則根據(jù)花費列表，由終點回溯至起點獲得路徑Path；若Current不為，則進(jìn)入第5步；

第5步，由模型算子Adjacent獲得子節(jié)點Child。檢索數(shù)據(jù)表IWall、IStaic，判斷子節(jié)點是否為不可通行元素(Wall、Static)。若是則進(jìn)入第3步，重新選擇當(dāng)前節(jié)點，否則計算子節(jié)點Child的優(yōu)先級(),并添加至優(yōu)先級隊列。

3.3 基于空間語義的IGGM模型路徑規(guī)劃實例

本文通過設(shè)計1個語義場景，體現(xiàn)模型數(shù)據(jù)類型及操作算子在空間規(guī)劃計算中的應(yīng)用。

實例如下：

詢問：從電梯旁的房間走到自習(xí)室靠近室外處的最短路徑及其距離。

對任務(wù)進(jìn)行分解，可以得出查詢設(shè)計2種空間類型，需要至少使用4個操作算子才能完成查詢操作，分別是：Neighborhood（元素的鄰域）、Buffer（緩沖區(qū)計算）、路徑尋找、線距離計算（Linelength）。實例實現(xiàn)邏輯如下：通過使用SQL語句查詢模型中電梯對應(yīng)的元素標(biāo)識符，使用鄰接算子Neighborhood獲得電梯旁空間元素標(biāo)識符。由元素標(biāo)識符在數(shù)據(jù)庫中檢索，選擇該元素對應(yīng)的1個網(wǎng)格獲得其標(biāo)識符。同理獲得自習(xí)室對應(yīng)標(biāo)識符，并由Buffer獲取自習(xí)室外墻附近的空間，從中選擇1個網(wǎng)格獲得其標(biāo)識符。將2個標(biāo)識符作為起終點，使用路徑尋找算子計算得到2點最短路徑。并利用算子ILinelength計算得到2點距離。

根據(jù)前文提到的數(shù)據(jù)獲取與地圖制作流程獲得某單位圖書館大廳與自習(xí)室及周邊空間數(shù)據(jù)，按照數(shù)據(jù)模型的要求存儲在對應(yīng)數(shù)據(jù)表中。

選取電梯旁大廳1點作為起點，自習(xí)室南墻附近1點為終點。查詢語句為

Select Astar(

select h3index from Room where GeoID =(select Neighborhood(select GeoID from IExit where name = ‘ElevatorDoor’) limit 1),

Select h3index from (select Buffer(select Iline from IWall where name =’studyRoom south-wall’)limit 1)

)

Select LineLength（resultRecods）

查詢語句中，對iexit表中查詢名字為“ElevatorDoor”的線幾何體，獲得其唯一標(biāo)識符后，使用操作算子Neightborhood以此查詢鄰接大廳的GeoID，選出格網(wǎng)作為空間查詢的起點。同理，獲得名字為“studyRoom south-wall”的空間元素格網(wǎng)ID，使用Buffer線幾何體周圍的網(wǎng)格，選出1個格網(wǎng)作為查詢的終點。2個點作為A*函數(shù)的起終點參數(shù)，返回值為格網(wǎng)數(shù)組。并使用LineLength計算距離。由查詢操作獲得輸出路徑（如圖5所示）。

圖5 室內(nèi)路徑規(guī)劃結(jié)果

實驗所用筆記本電腦配置為Inter?CoreTMI3-3227U CPU 1.9GHz，8G內(nèi)存，Windows10 64位操作系統(tǒng)。選擇7組代表不同室內(nèi)復(fù)雜程度與距離的點作為輸入，測試算法在IGGM模型下的效率，所得結(jié)果如表2所示。

表2 不同規(guī)模下查詢效率 ms

從7組結(jié)果中可以看到，查詢速率一方面與路徑距離長短有關(guān)，另一方面不同室內(nèi)復(fù)雜程度增加算法遍歷的格網(wǎng)數(shù)量，影響查詢速度。

3.4 與路網(wǎng)模型的對比

實驗通過對比常見的室內(nèi)路網(wǎng)模型測試基于DGGS的室內(nèi)數(shù)據(jù)格網(wǎng)模型在路徑規(guī)劃能力中的特征。對照的路網(wǎng)模型在原有的圖書館平面圖中設(shè)計拓?fù)渚W(wǎng)絡(luò)，使用pgRouting、PostGIS實現(xiàn)A*算法。

如圖6所示為室內(nèi)數(shù)據(jù)格網(wǎng)模型與路網(wǎng)模型在A*算法下路徑規(guī)劃的結(jié)果（采用3.3節(jié)7組起終點進(jìn)行測試）。圖中灰色格網(wǎng)路徑為格網(wǎng)模型下最短路徑，線段為采用路網(wǎng)模型獲得的最短路徑。

圖6 最短路徑比較

表3 不同模型下A*算法對比

經(jīng)過人工檢驗和計算，以六邊形格網(wǎng)距離“溫哥華距離[19]”作為判斷標(biāo)準(zhǔn)，7組實驗中格網(wǎng)模型最短路徑均為空間內(nèi)最短路徑。由表3可知，相較路網(wǎng)模型而言，格網(wǎng)模型的路徑距離平均縮短了12.9 %，最多縮短了24.2 %，室內(nèi)格網(wǎng)模型的最短路徑更為準(zhǔn)確。而且根據(jù)實驗結(jié)果判斷，隨著格網(wǎng)分辨率的增加，2種模型的差距將會更大。造成這一差距的主要原因在于，格網(wǎng)模型與路網(wǎng)模型相比具有更好的靈活性，而路網(wǎng)模型的規(guī)劃路徑只能局限在已有的拓?fù)渚W(wǎng)絡(luò)中，起終點的選擇上也只能基于現(xiàn)有的節(jié)點。

綜上，通過實現(xiàn)基于全球離散格網(wǎng)系統(tǒng)的A*算法，驗證了該模型能夠以地理格網(wǎng)單元為單位整合多種類型數(shù)據(jù)，兼具室外拓展與室內(nèi)空間計算能力，能夠有效進(jìn)行室內(nèi)路徑分析。一定程度上證明了利用全球離散格網(wǎng)系統(tǒng)進(jìn)行室內(nèi)數(shù)據(jù)建模的可行性與有效性，通過實現(xiàn)最短路徑分析也為擴散分析、室內(nèi)空間中心分析等應(yīng)用場景的實現(xiàn)提供可能。

4 結(jié)束語

當(dāng)今大數(shù)據(jù)時代下，室內(nèi)外空間數(shù)據(jù)的生產(chǎn)、發(fā)展、應(yīng)用日益完善，需要更多地研究和探索室內(nèi)外一體化的數(shù)據(jù)生產(chǎn)、制作和應(yīng)用。本文針對室內(nèi)場景下缺乏統(tǒng)一參考坐標(biāo)系統(tǒng)的問題，在傳統(tǒng)的室內(nèi)格網(wǎng)模型基礎(chǔ)上引入全球離散格網(wǎng)系統(tǒng)。該模型以全球離散格網(wǎng)系統(tǒng)作為坐標(biāo)參考系統(tǒng)，利用系統(tǒng)中格網(wǎng)單元作為空間數(shù)據(jù)格網(wǎng)模型基本單位，構(gòu)建具有語義信息的空間元素，使用2階基調(diào)進(jìn)行數(shù)據(jù)模型的數(shù)學(xué)形式化定義，保障該模型中元素與操作能夠在現(xiàn)有數(shù)據(jù)模型上實現(xiàn)。本文基于PostgreSQL數(shù)據(jù)庫與H3全球離散格網(wǎng)系統(tǒng)實現(xiàn)該數(shù)據(jù)模型，并完成了該模型下的最短路徑規(guī)劃的空間計算能力實驗。實驗中，導(dǎo)航路徑規(guī)劃能夠有效獲得六邊形格網(wǎng)下的最短路徑，且隨著格網(wǎng)精度的提高，能夠獲得更高精度的最短路徑。下一步工作除了進(jìn)一步完善模型、拓展空間計算能力外，將研究如何根據(jù)現(xiàn)有數(shù)據(jù)進(jìn)行數(shù)據(jù)模型的自動化生成。

[1]VANCLOOSTER A, VAN DE WEGHE N, DE MAEYER P. Integrating indoor and outdoor spaces for pedestrian navigation guidance: a review[J].Transactions in GIS, 2016, 20(4): 491-525.

[2]林雕, 宋國民, 賈奮勵. 面向位置服務(wù)的室內(nèi)空間模型研究進(jìn)展[J]. 導(dǎo)航定位學(xué)報, 2014, 2(4): 17-21.

[3]閆金金, 尚建嘎, 余芳文, 等. 面向?qū)崟r定位的室內(nèi)空間結(jié)構(gòu)分析及制圖方法[J]. 武漢大學(xué)學(xué)報（信息科學(xué)版）, 2016, 41(8): 1079-1086.

[4]LIN Z, XU Z, HU D, et al. Hybrid spatial data model for indoor space: combined topology and grid[J]. ISPRS International Journal of Geo-Information, 2017, 6(11): 343-359.

[5]LI X, CLARAMUNT C, RAY C. A grid graph-based model for the analysis of 2D indoor spaces[J]. Computers, Environment and Urban Systems, 2010, 34(6): 532-540.

[6]WANG W, AI T, GONG C. Indoor route planning under hexagon network considering multi-constrains[J]. International Archives of the Photogrammetry, Remote Sensing & Spatial Information Sciences, 2018, 42(4): 693-696.

[7]游天, 王光霞, 呂曉華, 等. 一種面向室內(nèi)導(dǎo)航的通行區(qū)域模型及其自動提取算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2019, 44(2): 177-184.

[8]張文元, 丁京禎, 楊麗娜, 等. 室內(nèi)外一體化最優(yōu)路徑分析算法實現(xiàn)[J]. 計算機工程與應(yīng)用, 2018, 54(18): 58-65.

[9]武恩超, 張恒才, 吳升. 基于中軸變換算法的室內(nèi)外一體化導(dǎo)航路網(wǎng)自動生成方法[J]. 地球信息科學(xué)學(xué)報, 2018, 20(6): 730-737.

[10]原璟, 程承旗, 童曉沖, 等. 基于PDR和地理網(wǎng)格的室內(nèi)外一體化定位方法[J]. 地理與地理信息科學(xué), 2016, 32(6): 32-36.

[11]SAHR K. Central place indexing: hierarchical linear indexing systems for mixed-aperture hexagonal discrete global grid systems[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 2019, 54(1): 16-29.

[12]JUBAIR M I, ALIM U, CLYN J, et al. Icosahedral maps for a multiresolution representation of earth data[C]//The European Association for Computer Graphics.Proceedings of Conference on Vision, Modeling and Visualization. Aire-la-Ville, Switzerland: Eurographics Association,2016: 161-168.

[13]童曉沖. 空間信息剖分組織的全球離散格網(wǎng)理論與方法[M]. 北京: 測繪出版社, 2016: 20-24.

[14]胡海, 游漣, 宋麗麗, 等. 地球格網(wǎng)化剖分及其度量問題[J]. 測繪學(xué)報, 2016, 45(1): 56-65.

[15]童曉沖, 賁進(jìn), 汪瀅. 利用數(shù)值投影變換構(gòu)建全球六邊形離散格網(wǎng)[J]. 測繪學(xué)報, 2014, 42(2): 268-276.

[16]GüTING R H. Second-order signature: a tool for specifying data models, query processing, and optimization[C]//The Association for Computing Machinery(ACM). Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.Washington:ACM, 1993: 277-286.

[17]PostgreSQL. PostgreSQL 10. 9 Documentation[EB/OL].[2019-04-01].https: //www. postgresql. org/docs/10/ index. html.

[18]THRUN S, BURGARD W, FOX D. Probabilistic robotics[M]. Cambridge: MIT Press, 2005: 180-184.

[19]YAP P. Grid-based path-finding[C]//NRC National Research Council-Canada. Proceedings of Conference of the Canadian Society for Computational Studies of Intelligence. Berlin: Springer-Verlag Berlin Heidelberg, 2002: 44-55.

An indoor spatial grid data model in the frame of DGGS

WU Qunyong1,2, ZENG Qingquan1,2,3, ZHANG Aiguo3

（1. Key Lab of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University/National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China;2. The Academy of Digital China (Fujian), Fuzhou 350003, China;3. School of Computer and Information Engineering, Xiamen University of Technology, Xiamen, Fujian 361024, China）

Aiming at the problems of the low-compatibility of indoor/outdoor data models and the lack of a unified spatial reference frame for indoor models, the paper proposed an indoor spatial grid model in the frame of discrete global grid system (DGGS): the information of location coding was provided by the indoor spatial grid model through introducing DGGS as the coordinate reference system, and DGGS was deemed as the geometric structure basis of the model to discretize the indoor space; then the discrete space grid was used as the basic organizational unit to design the type system of the model; finally the indoor path-planning based on A* algorithm was completed by using the characteristic of the hierarchical structure and the grid-indexing of the grid system. Experimental result verified the feasibility and effectiveness of the spatial planning and computing of the model under the unified reference frame.

spatial reference frames; discrete global grid system (DGGS); location coding; indoor model; path-planning

P228

A

2095-4999(2020)02-0055-08

鄔群勇，曾慶權(quán)，張愛國. 一種全球離散格網(wǎng)系統(tǒng)框架下的室內(nèi)空間網(wǎng)格數(shù)據(jù)模型[J]. 導(dǎo)航定位學(xué)報, 2020, 8(2): 55-62.（WU Qunyong, ZENG Qingquan, ZHANG Aiguo. An indoor spatial grid data model in the frame of DGGS[J]. Journal of Navigation and Positioning, 2020, 8(2): 55-62.）

10.16547/j.cnki.10-1096.20200210.

2019-07-17

國家自然科學(xué)基金項目（41471333）；中央引導(dǎo)地方科技發(fā)展專項（2017L3012）；福建省自然科學(xué)基金項目（2016J01198）；福州大學(xué)空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室開放基金課題（2018LSDMIS07）。

鄔群勇（1973—），男，山東諸城人，博士，研究員，研究方向為時空數(shù)據(jù)分析與地理信息服務(wù)。

張愛國（1976—），男，江西新干人，博士，副教授，研究方向為地理信息工程及測繪工程。