一種全球離散格網系統框架下的室內空間網格數據模型

鄔群勇，曾慶權，張愛國

一種全球離散格網系統框架下的室內空間網格數據模型

鄔群勇1,2，曾慶權1,2,3，張愛國3

（1. 福州大學空間數據挖掘與信息共享教育部重點實驗室/衛星空間信息技術綜合應用國家地方聯合工程研究中心，福州 350108；2. 數字中國研究院（福建），福州 350003；3. 廈門理工學院 計算機與信息工程學院，福建 廈門 361024）

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

空間參考框架；全球離散格網；位置編碼；室內模型；路徑規劃

0 引言

近年來，地理信息科學的研究與應用范圍逐漸由宏觀的室外環境向復雜多樣化的室內空間拓展[1]。室內定位技術與室外空間標準不兼容導致應用場景相互隔離。相比室外空間數據模型，室內空間數據模型中的技術參數、數據類型更多樣化，存在更復雜的空間約束。所以如何構建室內外一體化數據模型成為當前研究的重要方向之一。

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

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

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

本文基于數學工具“2階基調[16]”進行數據模型設計與形式化定義，設計模型相關類型組成及查詢操作，基于該模型與DGGS設計空間計算函數和語義查詢函數。

1 IGGM模型形式化定義

基于2階基調定義的數據模型能夠直接有效地在關系型數據庫中實現對應的數據模型。該工具通過給出類別和類型的構造聲明及底層的類型操作函數，使得數據模型尤其是時空數據模型的結構更為樸素與嚴謹。

基于全球離散格網的室內空間數據模型的形式化定義為

IGGM = (,,)（1）

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

IGGM的格網結構圖如圖1所示：模型構建在DGGS之上，利用DGGS的幾何結構組成室內格網集，并將格網集進行組織設計形成描述空間元素幾何信息的基本幾何體（點、線、區域），同數據庫基本數據類型如字符串、數字、時間格式、日期格式等組成模型的類型系統。而DGGS中由格網拓撲關系設計的函數集則作為另一重要組成部分被封裝為操作算子。

圖1 IGGM結構

1.1 IGGM幾何框架

IGGM模型由格網系統構成格網單元、格網線和格網面3種基本幾何體。模型中不同的空間元素由對應的幾何體構成，并以此為單位保存相關語義屬性。

格網點為模型的最基本單元，與DGGS中提取的室內格網集的格網單元一一對應。1個室內格網點（interior grid，IG）為1個4元組，即

格網線是由格網單元進行排列組合而成的線幾何體，用于表示墻體、圍欄、邊界、門等空間元素。1條由多個格網單元組成的1維列表結構的格網線定義為

式中IG為形成格網線的格網點。

室內格網面（區域）由格網點組成，室內房間以及聯通區域都需要使用室內區域對其進行描述。1個室內網格面IREGION是由多個網格單元組成，其定義為

1.2 IGGM的類型系統

對模型類型系統而言，類別主要包含了IDENT、DATA、TIME、INGEO、CONS、STATE、ELEM、IGGM。其中IDENT為標識符、DATA為基本數據類型集合、TIME為時間類型集合如（day、time等）、INGEO為基本幾何體，CONS為約束條件類型集合；STATE則代表狀態類型集合， ELEM對應空間元素類型集合，IGGM代表室內規則格網模型類型。

對室內空間模型而言，最重要的1部分即為空間元素。室內房間元素的定義由1個3元組構成，即

式中：ElemID為元素標識符；IReg為構成元素的格網面；ThemDes對應字符串類型，用于保存元素主題、關鍵字等。

室內墻元素的定義由3元組構成，即

式中ILine為構成元素的格網線。

室內靜態物元素的定義由3元組構成，即

室內門元素的定義由4元組構成，即

式中Dcons為約束信息，通過對時間約束和元素間通行狀態進行組合，表達不同時間段，由門元素連接的空間元素通行狀態。

室內出口元素的定義由4元組構成，即

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

1.3 模型的操作算子定義

模型操作算子由類別基調描述，主要有空間屬性操作算子、拓撲操作算子、幾何操作算子和空間規劃操作算子。利用算子對數據進行操作，結合控制過程能夠滿足多種應用需求。

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

空間拓撲操作主要有3種：包含關系判斷（Contain），判斷格網單元是否在區域或線上；鄰接關系判斷（Adjacent），判斷各基本幾何體的鄰接關系。

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

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

2 基于PostgreSQL的IGGM模型設計

選擇采用PostgreSQL[17]設計對應數據庫數據類型與數據表，用以描述格網與空間元素數據及幾何操作（如表1所示）。其中根據室內空間元素與模型的幾何體設計了7個數據表結構，分別對應格網點、格網線、格網區域、房間、靜態障礙物、出口、門。每個元素與幾何體的屬性由數據表中的字段類型表示，字段數據類型為數據庫基本類型或復合類型。

表1 室內空間元素與模型幾何體設計

3 實驗與結果分析

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

圖2 研究區域

3.1 室內數據格網模型構建

實例采用的全球離散格網系統為Uber公司的H3格網系統。該格網系統為正二十面體六邊形格網剖分，其基礎多邊形小，投影變形小，網結構具有一致的方向、距離分辨率。該系統具有完備的單元索引及操作函數，能為模型應用提供基礎。

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

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

圖3 六邊形格網平面圖

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

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

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

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

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

第1步，獲得起始節點、的網格標識符。

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

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

第4步，由優先級列表中選出優先級最高的格網作為當前節點Current，判斷當前節點是否為終點，若是，則根據花費列表，由終點回溯至起點獲得路徑Path；若Current不為，則進入第5步；

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

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

本文通過設計1個語義場景，體現模型數據類型及操作算子在空間規劃計算中的應用。

實例如下：

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

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

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

選取電梯旁大廳1點作為起點，自習室南墻附近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”的線幾何體，獲得其唯一標識符后，使用操作算子Neightborhood以此查詢鄰接大廳的GeoID，選出格網作為空間查詢的起點。同理，獲得名字為“studyRoom south-wall”的空間元素格網ID，使用Buffer線幾何體周圍的網格，選出1個格網作為查詢的終點。2個點作為A*函數的起終點參數，返回值為格網數組。并使用LineLength計算距離。由查詢操作獲得輸出路徑（如圖5所示）。

圖5 室內路徑規劃結果

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

表2 不同規模下查詢效率 ms

從7組結果中可以看到，查詢速率一方面與路徑距離長短有關，另一方面不同室內復雜程度增加算法遍歷的格網數量，影響查詢速度。

3.4 與路網模型的對比

實驗通過對比常見的室內路網模型測試基于DGGS的室內數據格網模型在路徑規劃能力中的特征。對照的路網模型在原有的圖書館平面圖中設計拓撲網絡，使用pgRouting、PostGIS實現A*算法。

如圖6所示為室內數據格網模型與路網模型在A*算法下路徑規劃的結果（采用3.3節7組起終點進行測試）。圖中灰色格網路徑為格網模型下最短路徑，線段為采用路網模型獲得的最短路徑。

圖6 最短路徑比較

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

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

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

4 結束語

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

[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]林雕, 宋國民, 賈奮勵. 面向位置服務的室內空間模型研究進展[J]. 導航定位學報, 2014, 2(4): 17-21.

[3]閆金金, 尚建嘎, 余芳文, 等. 面向實時定位的室內空間結構分析及制圖方法[J]. 武漢大學學報（信息科學版）, 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]游天, 王光霞, 呂曉華, 等. 一種面向室內導航的通行區域模型及其自動提取算法[J]. 武漢大學學報(信息科學版), 2019, 44(2): 177-184.

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

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

[10]原璟, 程承旗, 童曉沖, 等. 基于PDR和地理網格的室內外一體化定位方法[J]. 地理與地理信息科學, 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]童曉沖. 空間信息剖分組織的全球離散格網理論與方法[M]. 北京: 測繪出版社, 2016: 20-24.

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

[15]童曉沖, 賁進, 汪瀅. 利用數值投影變換構建全球六邊形離散格網[J]. 測繪學報, 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

鄔群勇，曾慶權，張愛國. 一種全球離散格網系統框架下的室內空間網格數據模型[J]. 導航定位學報, 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

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

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

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