一种全球离散格网系统框架下的室内空间网格数据模型

邬群勇，曾庆权，张爱国

一种全球离散格网系统框架下的室内空间网格数据模型

邬群勇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—），男，江西新干人，博士，副教授，研究方向为地理信息工程及测绘工程。