可导航的室内地图与室内导航算法
李宏利1 李飞2
(1.北京长地万方科技有限公司, 北京 100043；2.广东瑞图万方科技股份有限公司，佛山 528305) 摘要
本文从分析室内地图的需求和现状出发，研究了可导航的室内地图数据模型，给出了室内地图的数据组织方法和表达方式，特别是研究了室内导航系统的构成和使用室内地图进行不同楼层、不同地点间室内导航的基本算法及从室外跨入室内的无缝导航方法。

关键词
室内地图、位置服务、数据模型、室内导航
Indoor Map, LBS(Location Based Service)，Data Model，Indoor Navigation.
引言
随着以智能手机为代表的移动互联网的快速兴起与发展，随着人们生活水平提高、消费能力增强，人们对基于位置的移动生活服务需求与日俱增，人们不再满足于室外出发地到目的地之间的导航，而更需要在大型机场、火车站、百货商店、购物中心，大型室内地下停车场等这类极易迷路的室内场所的导航。

据抽样调查，现代人类有70%—80%的时间是在室内环境下生活与工作的，要提供优质的移动位置服务，不仅面向室外环境，更要能适应复杂的室内环境，这就要求必须有全面准确的可导航室内地图做支撑，实现室内的精确导航。

近年来室内地图的研究逐渐兴起，早在2011年11月Google发布了新版移动地图服务，其中就包括了大型商店和机场的室内地图功能。

此后国内不少手机地图厂商相继推出了不少室内地图作品，这些室内地图可以帮助用户清晰辨别每个楼层的建筑物各平面布局，详细搜索兴趣点的位置和深度服务信息，给用户带来全新的地理位置服务体验。

据不完全统计，目前可做展示使用的1:500的室内地图覆盖全国300多座城市，拥有超过数万座建筑物，1,00多万个室内POI，涵盖50多个场所类型。

由于卫星定位信号无法传播到室内精确解析定位，目前室内定位技术主要还是采用AGPS的基站定位或WIFI 指纹定位，这些定位方式好的也有几十米的误差，无法满足室内精细导航的需要，因此可导航的室内地图制作很少。

基于以上分析，本文的研究，面向未来室内定位技术平面位置可达到米级
精度、垂直精度可分出楼层的条件来研究室内可导航地图的概念模型、数据组织方法和表达方式，室内导航系统的构成和导航算法，以期将来能够依据可导航的室内地图实现高精度的室内导航。

1.室内地图数据模型
可导航的室内地图不但要解决各个楼层平面布局的展示和位置服务信息的搜索，而更重要的是解决一个楼层内的两个不同地点间的路径规划、分处不同楼层两个地点间的路径规划、从楼外的一点到楼内任意一层的任意地点的路径规划。

为此需要研究室内地图的数据模型和据此的室内导航算法。

1.1 模型要点
基于上述目的，本文设计给出的室内导航电子地图的数据模型要点是：1）室内导航地图与室外导航地图采用同一坐标系统、同一投影方式，通过设置室外道路连接结点形式连接室外道路，从而达到室内室
外一体化无缝导航。

2）一幢建筑（Building）为一个构图计算单元，由多个楼层（Floor）数据组构成。

对具有室内连通关系的多幢建筑群视为一幢建筑。

3）每个楼层由一组平面布局要素、信息点要素和具有点/线拓扑连通关系的通道要素组成。

4）一个楼层内的路径通达关系，用层内通道要素的点、线平面拓扑连通关系表达。

5）楼层间的路径通达关系，由以步行楼梯、垂直电梯、电动扶梯口、坡道为代表的层间转换结点的垂直拓扑连通关系表达。

1.2 单楼层平面图结构模型
一个楼层平面图的组成及相互关系如图1所示：
图1. 楼层平面图组成结构
这个关系图若忽略楼层间垂直连接结点，其实与普通的室外导航电子地图一致。

1.3 多楼层间的垂直拓扑连接关系模型
多个楼层之间的垂直拓扑连接关系如图2所示：
图2. 多楼层间的垂直拓扑关系图
这表达了依靠垂直拓扑连接结点和结点间的关系，可以由任意一层去往其他各层的目的地。

如图3所示，空心圆圈为垂直结点、实心圆为平面连接结点，结点间的实线段为平面连接通道。

若由M层的C点，到达N层的目的地F点，只需找出M到N垂直可通达的转换结点Pm和Pn，以及C到Pm和Pn到F的平面最优路径即可完成从C到F的路径规划，图中表达的黑粗线即是从出发地C到目的地F规划处的路径。

关键的难点是找到Pm和由Pm找Pn。

图3 不同楼层间路径规划示例图
2.室内地图数据组织
2.1 一幢建筑物的数据文件组织结构
室内地图数据库的组织结构是顶层为室内地图的总文件夹（IndoorMap）, 其下为各个地级以上城市文件夹，以城市字母缩写表达，再其下为城市内各个建筑物文件夹，一幢建筑为一个室内地图文件夹，其下有各个专题数据层。

以下是北京市（BJM）领先大厦（LXDS）室内地图数据组织的结构样例：
图4. 室内地图的文件组织样例
一个楼层内的文件主名命名规律是：
字母“F”+“楼层号”+字母下划线“_”+“数据专题类别码”
EG表示此图层为导航弧段；
ND表示此图层为导航结点；
PG表示此图层为设施面；
PT表示此图层为信息点。

楼层号为负值时, 表示该楼层属于地下建筑, 地下一层为“-1”。

如“F2_EG”,表示该图层为第二层楼的导航弧段。

如“F-1_ND”,表示该图层为地下一层楼的导航结点, 包括楼梯口。

若此建筑物内部具有全景观景点，则在建筑物文件夹下设有Pano_Photos 文件夹，存储与观景点相对应的360度全景照片。

2.2 一个楼层平面图的组成与表达
一个楼层平面图由拓扑连接结点、拓扑连接弧段、信息点和设施面四个图层组成，如图1。

具体存储结构与表达方式是：
表3：设施面
表4：信息点
图层名称 信息点 几何类型 point
文件名称 F*_PT 约束条件 “*”号表示楼层号 序号 属性字段名 数据类型 作用描述 属性值或值域描述 1 ID Integer 唯一识别码 正整数
2 Type Integer 类别 正整数，类别同设施面。

3 Name Char[50] 名称 字符串
4 PY Name Char[200] 名称的拼音 字符串
5 ABName Char[25] 名称缩写 字符串
6 PYABName Char[100] 名称缩写的拼音 字符串
7 Phone Char[20] 电话 字符串
8 Address Char[20] 楼内门址 字符串
9 Pano_Photo Char[20] 室内全景照片 JPG 文件名字符串
3. 室内地图导航系统的构成
作为一个可导航的室内电子地图数据库系统完成室内导航的任务，需要各个模块的间的紧密配合，基于数据流的模块关系图如下：
图4. 室内地图导航系统的组成模块
4. 室内导航的基本算法
基于本文给出的数据模型和组织方式，如图3所示，从M 层的C 点到N 层的F 点的科学合理的行进线路的路径规划计算步骤是：
1） 在楼层M 平面图上计算距起点C 最近的一个楼梯口结
点Pm ，计算方法是无墙阻隔的几何距离最短，且根据
表1的NodeType 、NodeFlow 和 Floors 项判断是可以达
地图数据
地图显示数据 路径规
划数据
请求接收模块
地图检索模块 地图存储模块
输入的需求
路径计算与导航模块
地图显示模块
到N层的结点。

2）在楼层M平面图上计算该起点C到最近的一个楼梯口
结点Pm的平面经由路径，使用Dijkstra (狄克斯特
拉)算法，取经由路径最短。

3）由找到的楼层M平面图上最近的一个楼梯口结点Pm，
根据它与其他楼层楼梯口结点的垂直拓扑关系，即表
1楼层转换结点间关系字段Stair_Nodes，遍历计算
楼层N上距楼层M楼梯口结点最近的楼梯口结点Pn。

4）最后依据在楼层N平面图上找到的楼梯口结点Pn，以
此为起点计算达到楼层N的最后目的地F点的平面经
由路径，使用Dijkstra (狄克斯特拉)算法，取经由
路径最短。

5）将上述步骤1）、2）、3）、4）计算得到的路径依次
串联起来，即为所求的室内导航路径，如图3的黑
粗线。

若最近的楼梯口不能到达目的楼层，则继续循
环，直到找到可到达目的楼层的楼梯口。

结束语
本文根据对室内地图需求和室内环境的空间结构分析，设计了可导航的室内地图数据模型，并在此基础上结合地图数据访问需求，探索了地图数据组织方法和表达方式，研究了室内地图导航系统的构成和基本的导航算法，实验表明这种室内地图制作方法简单可行、有效，导航效果满足人们对室内移动位置服务的需求。

室内地图的制作是一项基础且关键的任务，随着室内定位技术的成熟，高精度的可导航室内地图需求会越来越强烈。

本文提出的可导航室内地图制作方法和室内导航算法可为室内地图制作和室内位置服务应用开发提供借鉴。

参考文献
[1] 刘兆宏等，矢量室内地图建模与制作方法，数字通信，2012-第8期。

[2] 大众点评室内地图，/s/blog_6828dc760101g09f.html
作者简介：李宏利，男，61岁，北京长地万方科技有限公司总工程师，教授级高工，享受国务院政府特殊津贴，主持或参与卫星导航产业多项国家标准编写，是我国地理信息科学和卫星导航产业的知名专家。