室内导航路径规划算法的实现分析研究-USB迷|专注于互联网分享

2023年12月14日发(作者：犁文敏)

Abstract

In modern society，Outdoor road perplexing，Inside the building is also changing。

when one of us is away，We are more and more cannot do without the help of a navigation

system In a strange or familiar place. The outdoor navigation system has been quite

mature, But the indoor navigation system not been applied for the study of indoor

navigation, The key point is that modeling and indoor navigation algorithm for indoor

positioning, Until now, the indoor positioning has not been able to use the mature scheme;

The indoor map does not form a unified standard; At the same time indoor

navigation algorithms need to be designed for a particular situation, These are worthy of

further investigation and verification of the part. Aiming at the above problem, we put

forward a kind of path planning algorithm in space, and the path planning system from the

map building algorithm optimization and Implementation.

Aiming at the problem in path planning，In this paper, the space structure of the

minimum unit location in the room is simulated by the simplified room profile diagram.

Using Delaunay triangulation to determine the path points outside the room, the special

adjacency table storage map is designed, which provides the data for the algorithm. On

this basis, using A* algorithm as the basic algorithm of indoor path planning; According to

the speed of convergence of nodes and different functions, the H (n) is determined, and the

value function of the target node is h (n) when the distance is small. The data structure and

storage of the OPEN and CLOSED table are optimized and the algorithm efficiency is

improved. At the same time, according to the principle of the outdoor highway network,

this paper presents a multi story path planning algorithm, and analyzes its algorithm. With

the premise of the full connection between floors, the algorithm can plan the route of the

starting point to the destination more efficiently.

Finally, taking the laboratory project as an example, the practical application of the

path planning algorithm is carried out. The path planning of indoor and multi - layered

indoor is preliminarily realized. The empirical results show that the optimization path

planning algorithm is real and feasible.

Keywords：Indoor path planning；Indoor map；triangulation；A* algorithm

II目录

摘要................................................................................................................. I

<.II

1 绪论

1.1 研究背景与意义 ....................................................................................(1)

1.2 室内导航系统的国内外研究现状 ........................................................(2)

1.3 本文的组织结构 ....................................................................................(4)

2 室内导航关键技术研究

2.1 室内定位.................................................................................................(6)

2.2 室内地图建模.........................................................................................(9)

2.3 最短路径算法.......................................................................................(13)

3 室内导航的地图与算法设计

3.1 室内地图的构建和存储 ......................................................................(18)

3.2 基于单层空间的算法优化 ..................................................................(25)

3.3 基于多层空间的算法优化 ..................................................................(32)

3.4 总结.......................................................................................................(37)

4 室内路径规划的实现

III1.4 路径规划的相关网络接口 ..................................................................(38)

1.5 路径规划的客户端实现 ......................................................................(39)

1.6 路径规划的服务器实现 ......................................................................(42)

1.7 路径规划结果分析 ..............................................................................(47)

5 结论与展望

2.4 结论.......................................................................................................(49)

2.5 工作展望...............................................................................................(49)

致谢............................................................................................................(51)

参考文献......................................................................................................(52)

IV1 绪论

1.8 研究背景与意义

现代社会中，户外路况错综复杂，建筑的内部情况也不断变化。出门在外，来

到一个陌生或熟悉的地方，我们越来越离不开导航系统的帮助。传统意义上的导航

通常是通过实际地图和网络查询进行，信息的爆炸凸显出传统导航方式的低效率。

有效的导航可以是一种高效的信息查询和传递，可极大的提升个人的办事效率，有

效提高社会生产力。

现存的导航系统主要为室外导航系统[1]和室内导航系统。室外导航系统已经相当

成熟，如室外车载的导航系统凯立德、高德地图，万利达导航地图等等[2]。以上的导

航方式广泛的采用了以基于全球定位系统（GPS）[3]的导航，有的同时在蜂窝无线网

络可以覆盖到的地方辅助以蜂窝无线定位（Celluar wireless location）[4]。GPS 定位系

统是美国从 20 世纪 70 年代开始，由美国三军研制的军用定位系统，在几十年的发

展之后转向民用开放。它的定位的原理，是根据已知的用户到卫星之间的距离，运

用三边的测量方法获得用户与卫星之间的距离。GPS 的定位精度在室外民用可以达

到 5m。蜂窝无线定位系统分为基于网络的定位系统，基于移动台的定位系统和混合

定位系统。在人们生活中常见的是基于移动台的系统，它的原理和 GPS 系统相类似，

是以确定的移动台位置来定位用户。

随着手机等个人设备的扩展，室内建筑的复杂化加深，人们对室内导航的需求

迅速增大。特别在一些复杂的室内环境，如大型商场、复杂写字楼、大型购物中心、

展览馆等，用户常常需要知道在室内的位置，并知晓如何到达另一个确定的位置。

室内的拓扑结构复杂，情况多变，不便于建模，这都是室内导航系统需要克服的难

点。

现有常见的室内导航系统的核心包括室内地图信息建模，室内导航算法，室内

定位技术。由于室内导航的特殊性，室外导航的技术无法直接照搬于室内导航：

1首先在定位方面，室外导航系统往往依赖于室外良好的网络与数据基础，但是

GPS 和蜂窝信号进入室内之后会有严重的衰减，同时会有严重的多径效应产生，定

位精度非常低。室内定位的网络与测量数据需要独立的系统加以支撑。

其次在地图信息建模方面，建筑内的导航和路网之上的导航是完全不同的。以

车载系统为主的室外导航中，用户是只能行驶在路网上的；而以个人为用户的室内

导航系统中，人是有可以自由移动的区域的，行动路径的抽象不能如同公路网一般

简单实用点和线的连接。地图的抽象和建模需要结合室内情况进行，有的室内建筑

可以提供平面的建筑图纸，而有的完全需要人为测量绘制，需要具体问题具体分析。

最后，在导航算法与路径表示方面，由于信息获取和地图定义方式的不同，需

要独立的寻路算法和对路径的优化方式，无法直接照搬现有的系统。室内地图在空

间结构上有其独特的组织结构，空间上的分层性质、相互层次的独立和连接性质都

是其结构特点，也是可以算法针对优化的地方。

室内导航的定位近些年是研究热点，基于 RADAR 的室内 wifi 定位[5]、RFID 定

位[6]、基于 iBeacon 的蓝牙定位[7]、地磁定位[8]方式等等层出不穷，但是其中的大多

数定位方式有着极大的局限性，部署困难，使用准备周期长；对于室内路径导航系

统研究较少，更多还是集中于机器人在有限条件下的路径导航；国内室内地图的制

作和研究还处于起步阶段，室内地图建模还未形成统一规范的制作标准；以及在室

内导航中的路径规划算法。这些都是值得进一步研究和验证的部分。

1.9 室内导航系统的国内外研究现状

当前，对于室内导航系统的研究主要集中在两大课题的探讨：一是对室内定位

系统的研发，以室内感知系统、智能教室为典型代表；二是通过移动机器人实现导

航任务，该领域的研究重点是对机器人自身性能的不断改进，而对于导航功能的完

善则相对滞后。

对于室内定位而言，较早的室内定位研究有英国剑桥 ORL 在 1992 年研发的基

于蜂窝单元的 Active Badge 定位导航系统[9]，它的主要技术是利用红外线作为收发工

具，其优点在于可以省去具体的测距环节，但同时也受到其他干扰光线的影响，在

2精准度上难以有十足的保证，因而该系统并没有得到广泛地应用。

微软公司与 1998 年研发了 RADAR 室内定位系统，它是在改进 RSSI 技术基础

上的室内无线射频定位系统，指纹识别是其技术关键，主要通过构建信号传播模型

与场景法的方式来定位。RADAR 定位系统利用不同物体对信号传播的影响，构建信

号传播距离与信号接收强度间的信号衰减模型，随后算出信号传播距离，进而确定

位置值。RADAR 室内定位系统能很好地定位 2-3 米的室内范围，但受室内具体环境

的影响，RADAR 室内定位系统对位置的判断主要给出的是范围值，不能精确地判断

目标的具体定位。由于 WIFI 的广泛使用，基于 WIFI 的 RSSI 定位近些年成为热点，

但是还不能有较稳定的应用场合。

对于整体室内导航课题，韩国学者 Doohee Yun 与 Haeyong Jun 进行了系统研究，

他们将 GPS 信号运用于室内导航，所运用的主要方法是载波相位双差分测量法。

凯立德移动导航系统是一种由导航软件与电子地图组合而成的应用软件信息系

统，该导航系统被广泛地运用于手机应用程序之中。

法国航空公司 Thales 利用超宽带技术[10]研发出一套室内导航系统，这种新型的

无线电信号主要采用的是 radio pulses，该技术能帮助消防人员在施救过程中确定消

防车与其他消防人员的具体方位。

由我国自主研发的北斗卫星导航系统在北京奥运会期间被广泛运用于室内场馆

的监控工作，已具有相当成熟的室内区域导航功能。

Google Map 6.0 软件已经可以将室内场所的电子地图带入到 Android 设备中，但

是室内场所的电子地图并没有导航的功能，只是帮助用户找到最近的目的地。为了

缓解这一问题，谷歌公司又研发了 Floor Plan Marker 软件，这款软件具有更好的定

位功能，在引导用户前往目的地的过程中，还能够利用 WiFi 信号、GPS 等方式搜集

位置信息。当这些信息被收录到 Google Maps 的数据库以后，如果在该区域中有人

通过 Google Maps 进行定位，就能够顺利进行导航了。同时，谷歌公司也研发了全

新升级版的 Google Maps API，它能帮助开发者在地图导航的基础上研发更多的新应

用。

室内导航系统需要有较高的实用性与应变能力，在具体的导航过程中如果发生

3突发状况未能实现预计移动路线，那么导航系统必须快速重新组织最优路线。此外，

在实践过程中，导航电子地图的规模往往较大，在最优路径的算法中需要充足的储

存空间与时速有相对严格的要求。因此，为了能与之相适应，需要在算法上进行优

化，也就是说需要对最优路径与运行速度、储存空间等方面进行权衡，最后选择最

为合适的路径解。

在算法中，最符合导航系统需求的是基于图论的图搜索算法，即从初始点到目

标点进行搜索的算法。目前，与计算最短路径相关的算法约有 17 种，有学者对其中

了若干算法进行了科学测试，测试结果表明有 3 种算法具有较好的可行性，这 3 种

算法分别为：TQQ 算法、DKA 算法以及 DKD 算法。TQQ 算法的特点是适合于单源

点到剩余点之间最短距离的计算，它是基于图增长理论的算法。而 DKA 算法与 DKD

算法则更适宜于计算两个点之间的最短距离，Dijkstra 算法[11]是它的基础理论。无论

是哪种算法，都很大程度上考虑到了空间储存问题，不惜用时间效率换取存储空间，

这主要是受到了以前电脑硬件水平的制约。而现如今，硬件方面已得到很大的提升，

不再是算法中必须面对的首要问题，因而有条件对以往的算法进行适度改进，将追

求时间效率最为重要任务。

总体而言，当前的导航技术与算法研究的改进能到很大程度上缓解室内导航系

统中的最优路径选择问题。但需要注意的是，室内导航对于不同的应用环境有着不

同的应用需求，需要与之相应的导航技术对其进行高效定位。因此，研究者多集中

于对典型的、具体的环境中提出最优的具体方案，但能在实际系统中得到普遍应用

的相对较少，由于受到不同环境以及应用条件的制约，导航系统还有有待研究出更

优化的路径计算方式。

1.10 本文的组织结构

本文基于实验室项目中对于室内导航的需求，设计构建了可用于导航的室内地

图系统，并实现了导航的路径规划算法。本文第一章主要介绍了室内导航系统的发

展状况以及现实意义，总结概括的本文的结构。

4第二章分节介绍了室内导航在定位、地图以及算法方面涉及的关键技术和理论

基础。

第三章设计地图和导航算法。在这一章中主要用到了有限元三角划分进行室内

信息以及室内路径点的模拟，介绍了地图的存储方式。而后提出了一种室内路径规

划算法。该算法在单层空间中基于 A*算法，在多层空间中使用路网的策略进行多次

A*寻路，进行不同方式的路径规划。

第四章介绍了在项目中路径规划模块在不同平台上的划分和具体实现。结合路

径规划模块的具体实现效果，说明了地图和路径规划算法的有效性。

第五章进行了总结和分析，确定了下一步的研究方向。

52 室内导航关键技术研究

智能手机的普及和移动互联网的发展，带动了室内导航的发展。室内导航的关

键技术有地图信息建模，室内导航算法，室内定位技术。以下将分别对现有技术进

行简要研究。

1.11 室内定位

室内定位技术的是室内导航系统的关键技术，近几年来大型科技巨头以及一些

世界的知名大学都在研究室内定位技术，同时室内定位也成为一些小型创业公司的

发展热点。室内定位已经是研究的最大热门之一，本节简要研究室内定位的基本方

法，以及一些已经被提出的有一定使用价值的定位方案。

2.6 室内无线定位的基本方法

室内无线定位的基本方法[12]主要分以下四种：信号强度法（Received Signal

Strength Indication，RSSI）、时间法（Time of Arrival，TOA）、时间差法（Time Difference

of Arrival，TDOA）和角度法（Angle of Arrival，AOA）。其中后三种方法较为传统，

是由室外定位的方法衍生而来。

角度法（AOA）：在两个或两个以上的位置上，设置带有方向测量功能的基站，

基站可以获得终端发射出的无线电信号角度信息，然后通过测量不同信号交汇的方

式来估计终端的精确位置。

时间法（TOA）：时间法是根据三个已知位置的基站，来确定终端的位置。不

考虑误差时，已知每个基站的位置和到达的时间，可以通过求取 S=T*C 来获取每个

基站到测量点的精确位置，从而三点确定测量点位置。

时间差法（TDOA）：时间差法与时间法稍有不同，是检测信号到两个确定基站

的时间差来确定移动终端的位置，这样不需要基站和测量点之间有严格的时间同步，

极大降低了成本。这种定位方式精度上有相当的提高，比 TOA 法要容易实现的多，

6有一定的实用性，因此 TDOA 的使用比较广泛。

以上的传统方法无法克服室内的复杂环境，信号传播及其受限，受到多径效应

的干扰严重，精度受限，因此在室内定位，更多使用信号强度方法（Received Signal

Strength Indication，RSSI）。其基本原理，是利用需要测量点接收到信号的强度的衰

减和传输距离的关系来进行定位。要使用这个方法，需要先根据实际环境建立信号

衰减和传输距离之间的损耗函数模型，利用多个固定信号源进行三变测量，根据模

型来估量被测量点和固定信号源之间的距离。

虽然很多的室内定位系统都采用的是 RSSI 定位，但是不同的系统采用的都是不

同的原理和不同的方法。比如在经典的 RADAR 系统中使用 RSSI 定位使用的是位置

指纹法，将距离不同的节点的距离设为一组向量，通过比对该组向量的权值计算而

在系统中取得与之最相近的点；对于同样经典的 LANDMARC 系统，则采用权重质

心法对信号强度相当的数据进行处理[13]。接下来将简要介绍现有的室内定位方案。

1.12 室内定位方案

室内定位的解决方案中，从来都少不了信号的接收机和固定信号台的概念。由

于手机的普及以及移动互联网的发展，手机上的传感器日渐增多，比如重力传感器，

惯性传感器，GPS 模块等等。室内定位常将手机中的传感器作为定位的信号接收机，

用以收集固定信号台发出的数据，并加以处理。常见的室内定位技术方案主要有：

RFID 定位技术、蓝牙技术、A-GPS 技术、WIFI 技术等。

1）射频识别（RFID）是一种无线通信技术，可以通过无线电信号识别特定的目

标，并读写储存的数据，在这个过程中不需要建立直接的接触[14]。运用 RFID 定位

技术的系统常常由多个阅读器和标签构成，在需要定位的物体上附着射频标签，通

过获取射频来进行定位。过去的 13.56MHZ 以下的低频端射频识别系统，已经在如

图书馆等应用场合加以应用，近些年中高频段（860MHZ-960MHZ，UWB）的系统

也已经被广泛研究，并在一定范围内得到了使用，比如电子打卡、货物跟踪等等。

其优点在于，信号的传播距离可控，最长可高达 200 米，完全可以满足室内的使用

7要求，使用基于到达时间的定位技术，定位精度可达 0.1-1m。但是，为达到室内定

位使用的高频超宽带技术（UWB）技术成本高，硬件的规模大，价格昂贵，而且 UWB

不符合大多数公司的使用标准。公众是否会使用 UWB，FCC（联邦通信委员会）还

在考虑，使得该技术的未来还不清楚[18]。

2）辅助 GPS 定位技术，同时利用了全球卫星定位系统 GPS 和移动基站，是一

种结合网络基站信息和 GPS 信息对移动台进行定位的技术[15]。这一项技术在

GSM/GPRS、WCDMA 和 CDMA2000 网络中可以提升 GPS 信号的覆盖情况。A-GPS

可以使得接收器专心处理和跟踪 GPS 信号，将下载和解码来自 GPS 卫星的导航数据

的任务交给了 A-GPS[16]。使用这样的架构，可以极大的减少首次定位耗时，增加 GPS

的灵敏程度，使得 GPS 可以得到更好地使用。这种定位方式的出发点，是为了解决

在地面 GPS 信号弱的地方的定位效果，问题是，即便是在狭小的范围里，都几乎无

法收到 GPS 信号，在复杂的室内环境更是如此，导致辅助 GPS 定位几乎成为辅助系

统的定位。同时，部署 A-GPS 有着相当高的成本。

3）Wi-Fi 技术，是遵循 802.11x 系列产品标准的局域网技术，可以用于个人电脑，

手持设备，小型终端以无线方式组成局域网。使用 Wi-Fi 定位的系统，采集室内的不

同热点的 WiFi 信号强度 RSSI，采用信号传播模型与经验测试相结合的方式进行定

位[17]。由于 WiFi 热点的普及以及安装的简易程度，系统的成本较低，只需要安装很

少的基站。系统定位的精度在 1-20 米的范围内，其精度比普通的移动基站定位要高

出一个数量级。但是由于测算的过程只简单依靠传播模型，wifi 信号在室内的传播会

受到多径衰落和其它信号的影响，在室内状况复杂的时候，定位精度会受到影响，

容易出错，定位器的能耗也很高。Horus 系统提供了一种用于位置估算的联合集群技

术，该技术使用概率的方法来实现。

4）蓝牙技术，在室内定位上和 WiFi 定位类似，需要使用信号强度 RSSI 进行位

置的测算。蓝牙定位首先要在室内安装蓝牙接入设备，让室内形成多个类似的蜂窝

结构。随着蓝牙 4.0 技术的成熟，蓝牙定位克服了以往信号发射距离短的问题，同时

由于在单个时序周期长时间沉睡，蓝牙 4.0 的低功耗性也引起了不少厂商的关注。

2013 年苹果公司在研发者大会上公布了一款基于低功耗蓝牙的室内定位无线解决方

8案产品 iBeacon，可以在固定空间内发出信号，为接入系统的设备提供位置服务。蓝

牙定位系统在当前是一种很理想的技术，但是依旧存在定位系统的精度不够，在有

信号干扰时得不到保障的问题。

1.13 室内地图建模

室内地图的建模，是为将复杂的室内情况，抽象成为计算机可以处理和显示的

数据形式。在这个过程中，需要使用到图论的相关概念，将室内地图抽象成为可为

地图显示和寻路算法使用的图。需要使用到有限元法对室内空间结构中能通过的点

进行选取，以进一步进行路径的抽象。本节简要介绍需要使用的图论知识，以及有

限元法的基本知识。

2.7 图论基本概念

图论（Graph theory）是数学的一个分支学科，它以图为研究对象，研究顶点和

边组成的图形的数学理论和方法[19]。这里讨论的图并不是几何学之中的图形而是客

观世界表现事物之间关系的一种数学抽象，这种数据抽象需要在计算机中转化为数

据结构，用于地图和路径的呈现。

图：设V( ) {

1,v ,,vP}是一个非空有限集合，E(G) {e1,e ,,eP}是与 V 不

G v

2 2

相交的有限集合。图 G 指的是一个有序的三元组(V( ), ( ), )，其中 是关联函

G E G

数，是使得 E(G)中的每一个元素对应于 V(G)中的无序元素对。简单来说，V(G)是点

 表达的是某一条边对应的两点的映射的集合[20]。

的集合，E(G)是边的集合，

有向图和无向图：对于图 G 中的

v v

 ，映射 (e ) { , }，若对于任意 ，有

G n m G



) {v v 必有 (

) {v ,v }

(e  , }  e  ，映射为对称的，则可以用  v ,  一对无序对

n m m n m

代替这两个有序对，称为这两个点之间的一条边，这样的图被称为无向图。若映射 G

中的元素不对称，则可以将第一个元素称为起点，后一个元素称为终点，这样的图

称为有向图。

9邻接和关联：对于无向图 G，若有边e = v ,v

p

E ，则 m 和 n 点互为邻接点，

而且边 p 依附于点 n 和 m，边 p 关联于点 m 和点 n；对于有向图 G，若有弧

e v v E

{ , } ，则称点 n 邻接到点 m，点 m 邻接自点 n，边 p 关联于点 m 和点 n。

n m

度：对于有向图 G，有入度和出度的概念。一个顶点的入度是指与该顶点相关

联的入边的条数之和，而一个顶点出度则是指的和该顶点相关的出边的条数之和。

对于无向图 G 来说，一个顶点的度指的是所有与之相关联的边数之和。

子图：有两个图 G=

(V(G),E(G), )

和

G  (V(G ),E(G ), )

, 如果有

' ' '

V  且 E(G)  E(G'

) ，则有 G 是 G’的子图。

(G) V (G'

)

赋权图：给定图 G 之后，又是需要给 G 中的每条弧 q 赋予一个数 w(q) 。通常 w(q)

被称为赋予弧 q 的权。每条边都有赋权的图被称为赋权图，赋权的有向图又被称为

有向网络。

路径：在图 G=

( ( ), (G), )

v v

ia ( 

i a 1)

(v ,v

 E G a n  (V (G), E(G),G

) ，则称为从顶点 v 到顶点 v’的一条路径。

) ( ), [0, 1]

如果图是有向图，则路径也应该是有向的。序列中不存在重复点的路径被称为有向

路径。

1.14 有限元法中的三角剖分

有限元法自 20 世纪 60 年代问世以来，被广泛应用于各类工程分析研究中，可

以说，近年来有限元法的发展极大补充并丰富了网格划分方法，为室内导航路径研

究提供了可操作的算法基础。具体而言，有限元法要经过以下三个步骤：首先，确

立有限元模型[21]；其次，进行有限元的解算；最后，对有限元模型结果的处理。可

见，有限元模型的确立，即在给定分析域生成一个合理、科学的有限元网格是利用

有限元法进行室内导航研究的首要环节，也是关键环节。然而，网格划分是一个需要精确化的工程技术，如果研究对象属于较为复杂的几何体，那么可能在划分过程

中比较容易出现失误。当前，对于有限网格的生产方法大致可划分为两种：一是以

映射法为主题的结构化网格；二是根据对象特点生成的非结构网格[22]。在本研究中，

10生成地图主要应用的是非结构化网格中的一种——Delaunay 法[23]。这一方法的最大

优势在于能较好地处理室内边界线不明的情况，此外该方法还能很好的适应分布变

化不规律的情况。

一般而言，网格划分的方法主要基于三角形与四边形两种形态的单元划分。其

中三角形是较为普遍且简单易行的划分方法，这主要是因为三角形的模拟性较好，

能通过各种构造方式对二维图像进行最大限度的模拟。因而在本研究中笔者将采用

Delaunay 三角剖分的方法进行室内地图的路径选点。

1、Delaunay 三角剖分的基本特征

充分了解 Delaunay 三角剖分的特征是科学运用该方法进行室内导航定位的逻辑

前提。总体而言，Delaunay 三角剖分具有以下 6 点基本特征：

（1）唯一性：即通过三角剖分法所得的测算结果是唯一，与构建位置的起始点

无关。

（2）区域性：当改变一个三角形顶点的位置或对其进行增添、删除时，对区域

的整体性影响不大，且产生的影响主要作用于最靠近该顶点的一个三角形。

（3）最接近性：三角形形成的原则是以接近的三个点为顶点，在此基础上形成

的三角形的各条边互不相交。

（4）最优性：对最接近的两个三角形所构成的四边形，其对角线如若能相互替

代，那么原三角形内中最小的那个角将不会产生增大的趋势。

（5）凸多边性：由 Delaunay 三角剖分法构成的三角网，其外形是一个凸多边形

状态。

（6）最规则性：如果对各个三角形中的最小角进行升序处理，那么用 Delaunay

法得到的三角网将能得到最大的数值。

2. Delaunay 三角法的基本原理

平面域与节点是进行 Delaunay 三角法的基本对象，将平面域设定为

R ，平面域

内的各节点设定为

 

P P4

，通过连接各节点能构成三角形，且只有一种连接

1,P2

方法能使得任意三个节点组合而成的三角形，其外接圆仅包含这三个节点。在有

11 

P P4

个节点的平面域内，其三角形划分存在一个几何对偶，通常我们将此

1,P2

称之为由多个凸边形组合而成的 Voronoi 图，在此，我们将 Voronoi 图内的 n 个凸多

边形设定为

P



P



P



P

。与其他节点相比，任何一个凸多边形

 

.......

S P

内的各个点到节点 P 的距离都是最短的，此类型的凸多边形我们可设定为：

 



S P

 

 

x R ：，P  d x P i j  n i  j ，该公式的具体内涵是指对

d x

, , 1, 2, 3...... ,

平面域内的节点

P 与另外

n1个节点之间的连线做垂直平分线，由此将构成

n1个

半平面域，详见图 2.1：

图 2.1 Voronoi 多边形偶图

从图 2.1 中可获知，通常 Voronoi 中的凸多边形共用一个顶点，且各个凸多边形

中仅存在一个节点，将共用一个顶点的三个凸多边形内的唯一节点相连接，由此得

到的一个三角形区域称为一个 Delaunay 三角形，详见图 2.2。图 2.2 Delaunay 三角形

12由此可见，Delaunay 三角网具有以下几点特性：一是 Delaunay 三角网内的三角

形不会相互重叠，各三角形之间保持着各自的独立性；二是该三角网是 Voronoi 凸多

边形的点的连线；三是 Delaunay 三角形是根据相邻的三个顶点串联起来的，并且这

三个顶点在 Voronoi 凸多边形中有与之相应的公共顶点，这个公共顶点即是外接圆的

圆心。

总体观之，Delaunay 三角法具有减少误差与计算量的优势。在 DT 中，位置相

近的两个三角形所构成的一个凸四边形在进行对角线交换后，所形成的另外两个三

角形中的最小角会小于原来两个三角形中的最小角。因此，DT 在生成网格的应用中

独具优势。

1.15 最短路径算法

室内导航算法其实就是在室内地图的基础上，找寻最短路径的算法。其中大多

数的算法是通用算法，其中存在几种最经典的算法，分别是 Dijkstra 算法，Floyd 算

法，还有一种发展很快的 ant 算法。

2.8 Dijkstra 算法

最短路径问题一直是各个学科的研究热点，经典的图论和不断发展的计算机技

术使得新的最短路径算法不断出现，但是其中最经典的算法是 Dijkatra 算法[24][25]。

Dijkatra 算法是 1959 年为 ra 提出的算法，在图论中是计算最短路径的著名

算法，使用该算法可以求出任意一点到其它顶点的最短路径

【40】。

传统的 Dijkstra 算法的基本思想，第一步，是从起点求出距起点长度最短的一条

路径，然后通过对路径长度迭代，计算得到源点到其它各个目标节点的距离[41]。在

实际的运算过程中，计算者可以引入一个辅助的向量 D，向量中的分量的初值由边

或者弧上的权值来确定。如果两点 v 和 vi 之间没有直连关系，那么权值 D[i] 为正无

穷大。从点 v 出发的长度最短的一条最短路径是长度为

D[ j]  min{D[ j]| v V}的路



径，该路径为(v,v )。设下一条次短长度的最短路径的终点是v ，则这一条路径可能

i k

13为( ,v )

v v 。它的长度为从v

到

v 的弧上面的权值，或者是 D[j]中的

，或者为( ,

,v )

值与

v 到v 弧上权值的和。

i k

可以假设一维数组 S 是已经找到最短路径的终点集合。这样的话，下一条最短

路径需要加入的点 x 要么是(v, x) ，要么是中间只经过点集 S 中的点最后到达点 x 的

路径。以反正法来证明。假设下一条生成的最短路径之中，有一个点不在 S 之中，

说明有一条终点不在 S 之内，但是长度比这个路径要短的路径。以上的结果是不可

能的，因为算法产生 S 的过程是按照长度递增的次序来的，所有的长度比此路径短

的路径应该已经全部被包含在了集合 S 之中。所以以上假设是不成立的。所以下一

条次短的最短路径长度一定为

D[ j]  min{D[i]| vi

V  S}.同时 D[i] 的值只能为以上

两种情况之一。

证明了以上事实以后，可以由第一步和第二部进行迭代运算，计算出最短路径，

具体步骤如下：

1）如果使用带权值的邻接矩阵 c 来表示一个带权的图，则c[i, j]表示弧(vi

,vj

)上

的权值。若(vi

,v )不存在，则c[i, j]   (使用可以表示的最大整数来表示)，S 已经找

到从 n-1 点出发的最短路径的集合，其初始状态为空集。从v 到其它的节点的路径

长度向量为 d[n]，那么从 d[n]出发到图上的其它顶点 vi

可能达到的最短路径长初值

为：

d[i]  c[v ,i],v

0

2）选择v

使得

D[ j]  min{D[i]| vi

V  S}，

必然成为前求得的从v 出发的最

短路径的终点。使得 S  S {v }

3）改变从 d[n] 出发到集合

V S

任意一个顶点

可达的最短路径长。当

d[j]+c[j,k]

4）重复操作 2）3）一共 n-1 次。以此求得 d[n]出发到图上各个顶点的最短路径

以路径权值递增的序列。 141.16 Floyd 算法

Floyd 算法[26][27]的设计目的是求任意俩个顶点之间的最短路径，其算法的基础思

想是在带权地图中反复使用插入算法，构建出新的矩阵。在经过 n 次插入之后，得

到一个新的地图距离矩阵，在操作的过程中获取两点间的最短路径。

对于图中任意两个节点 Vm

和 Vn，假设它们的邻接矩阵为 D0，则需要使用 D0

进行对 D1 的计算。D1 的意义是从 Vm

到 Vn

的经过一个节点的邻接矩阵，其计算过

程是：算出两点之间经过一个点的所有可能的路径，然后比较并且选择出最短路径，

然后替代 D0 中的对应路径。以此为例反复进行迭代运算，直至迭代算出 Dn，其意

义为任意两点间最多经过 2n-1 个中间点时的最短路径。直到迭代运算使得矩阵不再

改变时，说明最短距离矩阵已经建立好。其基础算法如下：

1）制作基础距离的矩阵

 (d(0)ij

)

有：

 W ,ij

相邻

)ij



 

ij n

,( 1,2,3 )







 ij

，不相邻



2）构造迭代矩阵

 (d(n)ij

)其中有：



d



( 

( 1



k )

ir rj

k 1)

n(



min 1,2,3

3）若某次迭代

Dn1

 Dn

，则迭代停止，找到最短路径，否则第二步继续。

1.17 Ant 算法

蚁群算法[28]生成比较晚，是一种新的仿生类算法。这种算法在近些年逐渐被人

重视，是一种新的通用型算法。这种算法的命名 ANT 是来源于生物中的蚂蚁。其原

本模型是自然界中的蚂蚁在觅食的时候，会在走过的道路上留下一种叫做信息素的

物质。这种物质会累积叠加，并且会影响后来的蚂蚁的行为，使得后来的蚂蚁有更

高的概率从该路径上行进，反过来使得信息素的含量更加高。在这个过程中信息素提供了一种正反馈的循环。正所谓选择的人越多，其概率就越高，这种正反馈行为

可以被使用在最短路径的查询中。

因为蚁群算法是一种频率分配算法，其主要步骤为路径构建和信息素的更新，

15在构建路径的每一步中都需要随机比例规则选择下一个节点，随机比例规则如下：





(t)

   

如果j未被访问ij

过

 

]

(t) *  (t)









ij ij















 

 (t) *  (t)

k未被访问

如果节点 j 被访问过，则

Pij

(t)=0.其中，i,j 分别为起点和终点；ij

1/ dij

为能

见度，是 ij 之间距离的倒数； (t) 为时间 t 时由 i 到 j 的信息素强度。, 为两常数，

分别是信息素和能见度的加权值。

其主要步骤如下：

1）以随机比例规则对路径进行初始化，设置蚂蚁数量 m 和信息素蒸发概率。

2）为每个蚂蚁随机选择出发点。然后以随机比例规则选择下一个访问的点。

3）当所有点被遍历完成时，每只蚂蚁的路径都构建完毕并被记录。 163 室内导航的地图与算法设计

建筑物之内的导航与室外导航的重要区别点在于，室外地图常常以道路为划分，

户外导航的用户(车辆)只能行驶在道路上，而在室内的用户行为不定，可以在自由空

间内活动。需要找到合适合理的方法来进行室内地图的建模，并以此为基础进行室

内路径的建模。

路径在直观上是由点和线段组成，点用以表达空间中特殊的地理位置，而前端

表达地理位置之间的关系。为了完成室内导航的任务，需要构建出室内路径，而室

内路径的构建实际上就是路径点和通行顺序的构建。因此室内情景的建模，需要首

先构建以点和线为基础的室内环境图，描绘室内信息；然后，确定可以用于人通行

的路径点；最后，将点构建成路径联通关系图，具体设计过程在 3.1 中详细介绍。

在建立室内地图之后，下一步的工作是路径规划。路径规划是在现有室内地图

的模型基础上，根据用户提供的起点信息和想要到达的终点信息，查询并规划出从

起点到终点的每一步的移动轨迹，其目的是引导用户通过优化的合理的路线到达目

的地。路径规划算法流程图如下：

17客户端选择起

点和终点

网络通信

起点和终点是否在同一

topo之内

否

是

使用单层搜

索策略

使用多层搜

索策略

否

是否搜索到路径

拼接数据多

层路径

是

客户端提示

搜索错误未

取得路径

客户端获取

路径points并

显示

图 3.1 路径规划模块流程图

其中关键点在于在同层和不同层中的搜索策略，以下将在 3.2 和 3.3 节中详细介

绍算法中的搜索策略。

1.18 室内地图的构建和存储

室内地图是对室内情况的总体描述。室内地图的数据描述需要同时兼顾数据的

处理和表述，需要对室内地图需要的信息进行较为详实的抽象。考虑到室内建筑的

分层次，将室内地图抽象为 Area，Topo，Location 三层次。

Area：城市或建筑群，用于抽象室内建筑的大规模集群，属于地图最高层次。

Topo：部分区域的拓扑结构数据抽象，与 Area 为从属关系。Topo 可以为一个建

筑，一个楼层或楼层中的一片区域。该区域比 Area 覆盖范围小，但是范围并不固定，

18并且可以多层 Topo 相互从属形成 Topo 链条，形容室内部分区域。

Location：具体地点。该部分为室内地图最小单位的抽象（店铺，房间），内部

有着独立的几何关系和联通关系，从属于一个确定的 Topo 结构。该部分描绘具体房

间的地理位置信息，联通关系，形状，功能，类别等。

室内地图的主体集中于 Topo 和 Location 层次，Area 层次主要用于地图的分片和

与室外地图的衔接。

1.19 室内信息描绘

通常建筑物之内有一些常见的结构体，比如墙壁、走廊、门口，这些物体将空

间划分成一系列有独立作用的空间，这些用于划分的结构体，如墙壁、桌子等，被

视为障碍物。障碍物有的会影响通行，但是有的障碍物不会。

所以，我们可以用有限元描述室内空间结构。具体方法是，对于空间中相互连

接的地方，表现成点的形式，比如墙与墙的夹角部分，两段墙的交错部分，门的两

侧等等。对于不能通过的部分，使用直线连接进行表示。

图 3.1 室内部分区域的环境图

根据以上的思想对图 3.1 中的同层平面框架实现空间描述，门，墙壁等障碍物被

转化为以下的相应坐标模式，表现如下。

19图 3.2 室内情况描述图

图 3.2 中我们可以清楚的看到建筑的内部布局，其中的那些直线段无法穿越，为

障碍物；点表现为特殊的交汇点，比如桌子和墙壁，门和墙壁的交汇点。通过判断

和分析，得到点和线之间的关系，通过等比例的绘制使用线去连接点.

考虑到项目需求中，对地图导航的实际使用者为软件用户。以图 3.2 为例，假设

用户要从房间 A 到达房间 B，房间 AB 内的桌椅存在与否，并不构成用户从 A 到达

B 的干扰。若以室内路径规划为项目实际需求，则房间内的桌椅和窗口等物体的描

绘对项目是没有意义的。因此，对室内情况进一步简化，忽略室内障碍物结构。二

次简化后的图主要用于描绘联通环境，获取足够用于路径规划的信息量。

1.20 室内路径点描绘

室内路径点的建立是为了在以上室内空间图的基础上，解决在各个不同的室内

结构之间移动的问题。在确定了室内的 location 最小单位室内结构之后，需要将室内

地图的路径进行确定。室内地图在去除掉 Location 点之后，剩余的部分需要进行主

干点的确定，依靠 Location 的外围点，我们可以对其余的部分以 2.2.2 中介绍的

Delaunay 三角法进行三角划分。图 3.3 右的图为经过 3.1.1 节中有限元法处理的室内

地形图，取得其内部地图如右图。

20图 3.3 进行三角划分的室内地图区域范例

以其中 location 为外围点，内部地图进行 Delaunay 三角划分。地图中共有 25 个

分散的节点，在进行三角划分后，在 GIS 中手动删除一些因为整体边界为凹而产生

的多余连接线，可以得到如图 3.4 的空间区域三角网。

图 3.4 三角划分网络

对室内空间进行三角划分之后，需要使用三角网络确定室内的路径点。室内的

路径区域已经由三角形划分成很多份，则只需要选取三角形的一个特征点就可以代

替该片区域。由计算的简便性和三角形的特性考虑，可以选择其重心作为特征点，

其坐标值为三角形三个点坐标值的均值，以上有 30 个三角形，形成了 30 个路径点。

在确定了室内的空间点之后，需要使用路径点确定室内的联通关系。室内的路

径点之间有 C302

条连接线，由于数量巨大，其中大部分都不能反映正确的室内路径

信息，是需要被删除的。由三角形的两边之和大于第三边可知，若两个路径点之间

需要添加第三个点，如图 3.5：

21图 3.5 连接性判断

若 ABC 为路径点，在添加入数据库的过程中，对 ABC 之间的关系进行判断。若设

 

(b  c) 

(b  c)

则代表的是边 a 的被取代程度。若是一个很小的值，说明 a 可以被 b

和 c 取代。根据卢伟[42]等人对三角网的取值研究，可以将边界值设为 0.05，此时在

路网连接线大幅度简化的同时，依然可以保持室内连接性的无误差。以下为 边界

值为 0.05 时的简化图，见图 3.6：

图 3.6 道路连通关系图

在简化之后，点与点之间的联通关系只保存了 80 条。虽然有了极大的简化，但

是路径还是比较多。系统为了对自动生成的网格有进一步有效的管理，在前端集成

了网络节点的增改设置页面，进一步的简化可以在前端根据需要进行删减和测试。

1.21 室内地图的存储

将地图抽象成带权有向图之后，和地图相关的问题就可以使用图论工具进行分

析。为了能在地图信息的基础上进行路径规划算法计算路线，需要将总结的室内地

图信息转化成计算机可以计算和识别的方式，同时满足整个室内路径规划系统的使

用需求。对于路径计算的需求，需要占用尽可能小的存储空间，同时有较高的计算

22效率；对于系统需求，需要便于系统扩展和移植，便于新地图的录入、读出和其它

使用。

图的数据结构常使用邻接矩阵、邻接表表示。

邻接矩阵表示法：设一个有向图有 n 个节点，则另接矩阵是将图以一个 n 阶矩

阵的形式表现在数据结构中。邻接矩阵为 A，则 A 可以定义为

 

 a

n*n

：

 (v ,  E, j 1,2,3,4n

w v ) i,

a 

ij i j



(v ,v ) E



i j

其中 w 表示的是 ij 点之间的权重，正无穷表示两点之间没有连接关系。邻接矩

阵优缺点相当明显：邻接矩阵容易判断节点与边之间的连接关系，并且便于查找节

点和变，是一种时间效率相当高的数据结构；但是其所占空间大，在路网等稀疏图

中的存储没有优势。

邻接表表示法：邻接表是一种链式存储结构，在其中每一个顶点都链有顶点的

数据和连接在点上面的相邻节点指针，以每个节点作为链表表头，在其后以链表的

形式将与其相连的节点指针链在后方。对整个图来说，需要储存的链表数量为 n。图

1.22 为对地图的领接表表示举例。

Point2

Subway

Point3

全棉时代

Point4

麦当劳

Point5

阿香米线

Point3

全棉时代

Point5

阿香米线

Point5

阿香米线

Point4

麦当劳

Point1

屈臣氏

Point2

Subway

Point1

屈臣氏

Point3

全棉时代

Point1

屈臣氏

图 3.7 某 5 个节点的邻接表表示法

从以上可以看出邻接表的优缺点很明显，其节省存储空间，但是对于有向图而

言，很难通过邻接表查询节点的入度[34]。

室内地图的组成形式是基于点的无向图，其弧和弧的权值可以从节点与节点之间的坐标进行简单运算得到并加以储存，弧的附加信息较少。邻接表在无向图的存

23储上，占用空间少，对弧的附加信息少，适合在本系统中作为室内地图的数据结构。

实际表示方法如图 3.8：

Point1

屈臣氏

Point2

Subway

ArrID:5.4.2

ArrDis:10,20,40

ArrID:3.1

ArrDis:15,40

ArrID:5.2

ArrDis:70,15

ArrID:5.1

ArrDis:44,20

ArrID:4,3,1

ArrDis:44,70,10

Point3

全棉时代

Point4

麦当劳

Point5

阿香米线

图 3.8 室内点的实际表示法

由于室内地图的存储基于数据库，需要数据结构基于数据表中储存的数据，而

链表中的指针是不利于数据库存储的数据结构。考虑到以上问题，可以将邻接表中

的指针简化为节点的 id，同时将节点从数据库提取后实例化为节点类的对象，将其

相邻的节点 id 以数组或表的方式加以储存。其相邻节点代表的是节点的弧，可以将

弧的信息一同以数组形式存储，如图 3.8，或者将相邻节点以字典或者以 id 为 key 的

hash 表存储。

室内地图的视觉图（地图背景）本身作为图片储存在数据库中，室内寻路地图

的简化图依附于视觉图为背景，其坐标位置应该与视觉图的长度和宽度一致。举例

而言，若视觉图为 800*600 像素的 jpg 图片，某一个以室内信息描绘点 v 在以视觉图

左上角为坐标原点进行染色之后，应该与该点所代表的实际点位置相同，显示在视

觉图的同一个位置上。

室内地图的主体由点组成，数据库中所有的点储存在 point 表之中。考虑到各方

的需求，将点的其主要属性进行抽象。各个字段如下：

int x；int y；为坐标点在视觉图上的坐标位置。

Long id；为坐标点的唯一标示符。

24Long connections[]；数组，记录与该点相直连的点 id。

Double Dist[]；数组，记录与点对应的 id 点的距离。

Long exit[]；数组，记录该点能通向的 topo id，若为空则说明点不是出口点。

String esname；字符串，用以说明出口的特殊名称，如电梯 1，楼梯 2 等。若为

空，则说明点不是出口点。

Long topoid；为点从属与的 topo 结构的唯一标示符。

Long location；为点从属与的 location 结构的唯一标示符。

以上各个字段需要对应的数据被转换成 json 字符串，储存在数据库的 point 表中。

其数据表需要被用于显示地图情况，对应的 location 详情，同时要被转换为数据结构

用于路径规划的计算，需要设计一系列的接口用于调用，这一部分内容将在第四章

加以详细说明。

1.23 基于单层空间的算法优化

室内地图选择 Dijkstra 作为基础算法。从 2.3.1 中算法基础过程可以得知，第一

步对带权图的遍历是算法效率的关键。当每次搜索权值最小的点的时候，需要对集

合上面的所有节点进行遍历，处理这些无序的元素需要消耗大量的时间和空间。若

图中的节点数量为 N，则该算法的时间复杂度为 o(N2)，为提高算法效率需要对算法

进行优化。

对于室内路径规划算法，首先考虑基础情况，即是路径的起点和终点在同一个

topo 结构图中。若使用基础的 Dijkatra 算法，一定可以搜寻出路径，但是需要遍历同

层的其余全部节点。本节基于路径起点终点在同一个 topo 结构图中的情况，对基础

算法进行优化。

2.9 A*算法

基础的 Dijkstra 算法是穷举方式的算法，是在所有的状态空间中进行穷举，是寻

路的通用算法，其最明显的缺点是没有使用到地图本身具有的信息，搜索是盲目顺

25序进行的。当状态空间不大时其缺点不明显，但当搜索的点数量级提高时，盲目搜

索的效率实在太低，消耗太多的时间和空间。

A*算法建立在 Dijkstra 算法的基础之上，被称为“启发式搜索”[29]。其思想为，

通过检测具体问题中具有的信息，为搜索选定合理的顺序，以减少搜索的次数。其

创新之处，为在选择下一个被检查的节点时，使用了已知的全局信息作为参考，对

于目标节点到当前节点的距离做出估计，当作评价当前节点处于最优路线的可能性

的度量，使得搜索算法考虑最有希望的节点，以此提高搜索效率。现下 A*算法已经

在很多领域取得了广泛的应用，很多的战略游戏使用这个算法进行地图路径搜索[30]。

待搜索结点的重要性需要通过一定的方式排序，通常我们采用的是估价函数

f (n) 的方式进行重要性评判。估价函数 f (n) 没有固定的函数形式，例如将其定义为

结点 n 位于最优路径上的几率：结点n 到目标点所需的路程、时长等。总体观之，以

下几点要素是评价某一结点的关键：一是该结点已经产生的消耗；二是该结点接下

来可能产生的消耗。在此基础上，我们将估价函数 f (n) 概括为初始结点在路经结点n ，

并最终到达目标结点后所需要的最小代价的估计量，可用如下表达式表达：

f (n)  g(n)  h(n)

在该表达式中 g(n) 表示初始结点路经结点n 所需要的消耗量，h(n) 表示结点n

到达目标结点时的消耗量。与此同时，g(n) 与h(n) 的内涵可分别表示为：首先，h(n)

是搜索的启发信息，这主要在于表示实际消耗量的 g(n) 是可以利用生成出的搜索树

计算出来，但是表示估计消耗量的 h(n) 只能通过估算的方式得出，估算值的准确度

很大程度上取决于问题领域中的启发信息，且估计值与希望度成反比，即具有较大

估计值的结点 n ，其希望度相反越低，该结点在扩展顺序上也会相应地靠后；其次，

g(n) 能很好的展现路径的完备程度，g(n) 在 f (n) 中占的比例越高，那么它的完备程

度也就越好。同时还需注意的是，由于从起始结点到最终结点的路径存在多种选择，

因此 h 值的不同计算方式会导致结果路径存在差异性的可能。

OPEN

队列与CLOSED队列是实现算法 A*

的两个关键因素[33]，从初始点起移动

至相近的结点，并且该路径是最优的，那么就可以将该结点根据估计值的大小，按

26照从小到大的顺序依次插入至OPEN

队列中，将相近结点中具有最小估计值的结点

插入至CLOSED队列中，以此类推依次试探。此外，插入至OPEN

队列需要具备以

下几点基本条件：一是可移动性，即在地图上是可以随意移动的；二是OPEN

队列

中本不存在该结点；三是初始点移动至该点的具体距离小于该店的历史最小距离。

算法的具体步骤可通过一个实例来体现，如图 3.9 所示，图中的 A 表示初始

点， P 表示目标点，每个字母后面的数值表示的是此结点的估计值。

图 3.9 A*算法举例

在搜索期间，OPEN

表与CLOSED表分别保存待考察的结点与已经访问的结点。

根据 f (n) 重新组合OPEN

是算法 A*

中的关键步骤，在不断循环的步骤中仅考虑

OPEN

表中具有最佳状态的结点，搜索步骤如下所示：

(1)初始：

OPED [A5];

(2)对

A5进行估算，将所得的子节点移至OPEN

表中：

OPEN  [B4,C4, D6];

(3)对

进行估算，将所得子节点移至OPEN

表中：

OPEN [C4,E5,F5,D6] ;

(4)对C4进行估算，将所得子节点移至OPEN

表中：

OPEN  [H3,G4, E5, F5, D6]; CLOSED  [C4, B4, A5]

CLOSED  [B4, A5]

CLOSED  [A5]

CLOSED []

(5)对

H3进行估算，将所得子节点移至OPEN

表中：

OPEN [O2,P3,G4,E5,F5,D6]; CLOSED  [H3,C4, B4, A5]

(6)对O2 进行估算，将所得子节点移至OPEN

表中：

OPEN  [P3,G4, E5, F5, D6] ；

27CLOSED [O2,H3,C4,B4, A5] (7)对

P3进行估算，得到最终解。

将全部结点的平均出度记做 b，从初始点到目标点的最优路径记为 d，那么算法

A 的时间复制程度可记为O(bd) 。Dijkstra 算法的时间复杂度为 o(N2)，其中 N 为节

点的个数。在实际室内地中，一个点的出度一般不会太多，平均只有 4-5 个，相比较

之下，A*算法的时间复杂度要远小于 Dijkstra 算法，因此系统采用 A*算法来进行路

径规划。

确定了使用函数以后，可以根据上文步骤写出主要算法的伪码如下：

SeearchRoad()

{

OPEN = [];

CLOSED = [];

起始节点加入到 OPEN 表中；

While(表 OPEN 不为空)

{

将 OPEN 中的第一个节点 N 取出；

If(N 是目标)

{

得到路径并返回；

}

For(N 的每一个子节点 M)

{

If(M 不在 OPEN 表和 CLOSE 表中)

{

使用估值函数求出 M 的对应值，然后将 M 插入到 OPEN 表；

}

Else if(M 在 OPEN 表中)

{

If(OPEN 表中的值比 N 大)

28{

更新 OPEN 表里面的值；

}

Else(M 在 CLOSED 表中)

{

If(CLOSED 估值大于 M 估值)

{

将点从 CLOSED 表里面移出并添加到 OPEN 表里面，然后

更新 CLOSED 表的值；

}

将处理完的 M 节点加入到 CLOSED 表中，并对 OPEN 表中的元素

进行一轮排序；

}

1.24 估值函数的确定

对于 A*算法，估值函数 f(n)的选取是其核心问题[35]。一个不合适的估值函数不

仅起不到简化算法的作用，在某些情况下，还会使得算法的性能变差。算法的中 f(n)

的选取实际上是为了能让算法在下一次选点时，选择与终点更为接近的点。因此，f(n)

需要能够起到正确的引导作用，使得其核心取值函数 f[v]=g[v]+h[v]能够在正确的引

导方向上有较小的值。合适的 f[n]可以极大的减少搜索次数，提升算法效率。这种效

率的提升，实际上是使用在每次搜索时附加一个高效率的 f[n]查询，以减少查询的次

数。当 f[0]=0 时，启发信息为 0，A*算法的效率达到最低，退化为无启发信息的 Dijkstra

算法，需要对所有节点进行遍历。因此，如何在搜索中尽可能减少搜索次数，是提

29高搜索效率的关键。

在地图路径搜索中，往往是从起点出发往终点的搜索。其最直观的想法是：如

果终点在某个方向，则向某个方向进发。下面列举几种基于方向的启发式算法，比

较并选取最适合的启发函数：

1）在估值函数中比较探查点到终点的方向夹角。对于任一起点坐标 v1(a1,a2)，

假定终点坐标为 v2(a2,b2)，正在探查点为 v3(a3,b3)，则将要移动的方向和起点终点之

间的方向矢量分别为(a2-a1,b2-b1)，(a3-a1,b3-b1)。若设矢量之间的方向夹角为θ ，可以

计算得出：

cos 

v v |  | v v |  | v v

2 2

1 2 1 3 2 3

1 3

2 | v v || v v |

1 2

其中有：

| v1v | (a  a )2

 (b  b ) ，同理可求得|

1v |

，| v

|。

2 1 2 1 2

则估值函数可以表示为：

f (n)  g(n) 

v v

1 2

| v  | v v

 v |2

1 3 2 3

1 3

2 | v v || v v |

1 2

可以看出在这个估值函数中有着大量的乘方开方运算。单次乘方和开方运算在

计算机中的开销是要比简单的加减高出一个数量级的，这种运算若是存在于循环之

中需要反复调用，会极大的降低算法效率。

2）在估值函数中使用探查点与终点的欧氏距离。对于同样的起点和终点，在探

查时计算探查点与终点的欧氏距离，可以很简单的写出估值函数：

f (n  g(n)  (a2

 a )  (b b )

)

2 3

而且，当估值函数为

h(n)  (a  a

 b b

时，可以很容易证明，若存在两个

) ( )

2 2

2 3 3

需要比较的点 v 和 v`时，若 h(v)>h(v`)，则有夹角θ >θ `。也就是说，使用欧氏距离

作为估值函数，在点的排序中对点的影响能力是绝对高于角度估值的。若将一次乘方和开放次数设为 1，则角度估值的开销为 6，欧式距离计算的开销为 3，使用欧氏

距离明显减少了计算量。

303）在估值函数中使用探查点与终点的曼哈顿距离。对于两点之间的曼哈顿距离,

写出估值函数如下：

f  g 

 a |  | b b

(n) (n) | a

3 2 3

这个函数的计算量更小，只有加减运算。在计算机中，开放和乘方运算的运算

量是同样数量加减法的 10 倍左右。和前两种估值函数相比，曼哈顿距离计算量低了

一个数量级，但是曼哈顿距离函数可以正确表示出启发算法中对距离的估值么？由

于

(

a )

a 

(b b ) | a a | | b b |

     

，曼哈顿距离的影响能力是小于欧式

2 3 2 3 2 3

距离的。如图 3.10 所示：

图 3.10 估值函数的逼近线比较

看得出以曼哈顿距离作为估值函数，在估值效果方面略差于欧氏距离。对于以

矩形网格划分的室内情况图而言，使用曼哈顿距离效果会明显差于使用欧氏距离的

估值函数。项目中室内地图并不基于矩形网格划分，路径点大体按照路网均匀分布。

基于计算的简便性和性能的损耗程度考虑，使用曼哈顿或者欧式距离作为 A*算法的

估值函数。具体到算法之中，需要以节点规模作为判断标准，若节点规模过大，比

如说超过 1000，则使用曼哈顿距离作为估值函数，而较小规模的路径点判断则使用

欧氏距离作为估值函数。 311.25 算法中的存储优化

无论是 A*算法还是 Dijkstra 算法[37]，其核心步骤都是维护 CLOSED 表和 OPEN

表，对数据进行比较插入删除操作。其中 CLOSED 表维护的是已经访问过的节点，

由 4.2.1 中的伪码表示可以看出，其主要操作是添加删除节点和查询节点。OPEN 表

维护的是已生成但是还未考察的节点，可总结其主要操作是：取得值最小的节点，

加入和删除节点，节点排序。

其中无论是 OPEN 表还是 CLOSE 表，最影响操作效率的操作是对于是否存在于

表中，因为这个操作在每一次的循环中都要调用。传统的数据结构优化方法是将两

张表构建成一个 mutiset 数据结构，这样的操作在完成查询的同时会影响其它操作的

效率。其实可以在两张表的基础上多使用一张 hash 表储存这些节点的指针，并使用

其 id 作为查询的 key。由于每个 point 的 id 都是唯一的，而且 hash 表的查询效率是

非常高的，在这个关键步骤使用 hash 表，将会极大的提高整个算法效率。在查询的

过程中，若发现节点在 hash 表中已有，则可以直接取得该节点，对其进行修改后再

进行进一步的操作。

OPEN 表中由于每次查找过后都要进行节点排序并找出值最小的节点。若每次比

较所有的节点，可以简单使用一次冒泡排序方法，遍历一遍 OPEN 表，记录其中最

小的开销值。若使用这种最简单的方法，则在循环中的每一层都需要进行一个效率

为 o(n)的操作。当节点的数量上升的时候，OPEN 表排序的开销将会非常可观，需要

对 OPEN 表的数据结构进行优化。

为解决 OPEN 表排序的问题，可以使用以数组方式维护的二叉堆数据结构[36]，

则可以将数据的排序开销降低为 O(logn)，同时数组的基础数据结构可以很容易完成

数据的插入和删除操作，还可以在插入和删除的同时对二叉堆进行排序。

2.10 基于多层空间的算法优化

传统 Dijkstra 算法和改良的 A*算法搜寻的是二维空间中的最短路径[38][39]，但是

32室内空间并不是单纯的二维空间。商场、办公室、写字楼中的空间都是分层的，每

层楼都有其不同的功能和空间划分，不同的楼层以楼梯，电梯连接在了一起。多层

空间的路径规划是我们必须解决的问题。

1.26 多层空间的算法步骤

对于多层空间的算法处理，贺昶玮在其室内导航系统中提出了一种简单策略[31]，

其策略如下：

1、起始点与目标楼层相差一层，则寻找所有楼梯节点和室内所有楼层节点，对

路径进行 A*算法规划。

2、起始点与目标楼层相差超过一层，则寻找所有电梯节点和室内所有楼层节点，

对路径进行 A*算法规划。

该算法将不同楼层和电梯楼梯节点直接拼接成大图，当楼层差别超过 1 层时，

只使用电梯寻路。该算法直观易行，但是也存在明显缺陷：每次寻路需要将所有楼

层节点加入遍历，搜寻节点规模大；若楼层之间超过 2 层，并且没有直接连接的电

梯，搜索算法会无法搜索到目的节点。

在室外地图中，为了将地图查询过程简化，常常将查询按照公路等级进行分层[32]。

比如若一个人要从武汉开车去北京，需要进行路径规划，第一步的规划是规划从现

在武汉所在地点通向出城高速路口的路径，其行走的是市内公路，只需要查询市内

的公路网络；第二步是规划从高速公路路网通向北京的道路，寻找的是高速公路网

中通向北京的最近出口；第三步是在出口下车，规划在北京市内到达目的地的路径，

查询的是北京的室内公路网络。可以看得出，以上查询是以（市内公路——高速网

络——室内公路）的方式进行的查询，每次查询的点集有限，层次清晰。在室内路

径规划中，我们能不能使用相同的方式呢？

若是一个人想要从室内的某处到达不同楼层的某个位置，其路线必定是先寻找

某个楼梯或者电梯离开当层；若没有直达电梯，需要走楼梯或者换乘电梯到达某一

楼层；最后在目的地层寻找到需要到达的位置。与室外地图相比较，室内地图的“换

乘电梯和楼梯”对应了室外地图的高速公路路网查询。以此我们提出一种算法，将

33不同楼层之间的电梯和楼梯联通情况，抽象成为室内路径规划的“高速路网”，以

此来完成不同楼层之间的转移和寻路。

基于以上思想，提出一种多层空间寻路的基本算法步骤：

1、搜寻距离起点最近的“高速公路”入口。

2、搜寻入口到目的地层次最近的路网出口。

3、从路网出口搜寻到目的地的路径。

如果起点和终点联通，按照以上步骤一定可以依靠类似的高层网络（以下称为

路网）搜寻到目的地。就以上初始想法，可以提出三点问题：这样搜索的路径是否

最优？这样搜索是否有高效率？这种搜索方式中的路网如何建立？

就路径是否最优而言，以上算法需要看到在三个步骤里面都是局部的最短路径，

但是综合考虑可能不是最好的方法。对于出发点而言，离路网最近的点可能不是最

优点，比如离起点最近出口为一处楼梯，但从更远处的电梯有更合理的路径。所以，

以上的基本算法是有缺陷的。为寻找最佳路径，作者对以上的基本算法步骤做出了

以下改变：

1、搜寻入口到本层的所有路网入口的路径。

2、搜寻目的地各路网出口到目的地的所有路径。

3、获取路网具体信息，将 1.、2 步骤所搜索到的路径距离和起点终点两点添加

到路网之中。

4、在新路网中搜索起点到终点的路径。

接下来对改进算法的性能进行说明和分析。

1.27 多层空间的改进算法分析

由于路网信息在基本步骤中，与层次之间的连通性是没有关系的，只能使用简

单策略，即寻找最近的路网入口然后寻找通向其的路径。若想要得到路径规划的最

优解，需要打破路网的“黑盒”，将起点和终点的信息加入到路网信息中加以考虑。

以上经过修改的步骤1和步骤2，其实际用意为获取需要加入路网的两个节点：起点、

终点，以及联通这两个节点与路网的边的信息。而后，将这两个新节点添加到路网

34之中，做整体的二次寻路运算。

室内的路网与室外路网相似，其电梯节点与楼梯节点在建筑中属于固定信息，

只有在室内情况大规模改变或是新地图录入时才需要重新修改。因此，室内空间的

路网可以在室内地图建立时处理好，直接保存在数据库中。在特定起点到终点的搜

索中，首先取出路网信息，等待步骤 1 和步骤 2 的寻路过程完成之后进行拼接。也

就是说，步骤 1 和步骤 2 的搜索是每一次寻路都要进行的步骤。

假设起点层有 3 台电梯，3 个楼梯可以通往其它楼层，重点层有 2 台电梯，2 个

楼梯通往其它层，是否说明对于步骤 1 和步骤 2 而言，每次寻路在对应的起点和重

点，需要进行 6 次和 4 次 A*搜索呢？

在 A*搜索中的终止条件是，搜寻到终点或者搜索完所有节点没有结果。若是同

层有 6 个点需要搜索同一起点的最短路径，其实并不需要进行 6 次搜索，只需要在

同一次搜索中对需要搜索的终点集合做维护，以所有的点都被搜索到作为搜索的终

止条件。这样的搜索量是和单次搜索离起点最远的路网节点相同，区别是需要在每

一次的节点中判断节点是否属于终点集合。与在 4.2.3 中维护 OPEN 表和 CLOSED

表类似，可以添加一个 hash 表存储需要搜索的终点集合，用以判断搜索的节点是否

在集合中，若在集合中则删除节点，以搜索节点的集合为空作为步骤 1 或者步骤 2

的结束条件。

对于多层空间的算法而言，步骤 1 和步骤 2 进行了两次以节点集合为终点的 A*

搜索，在组建新的实际路网之后进行了第三次 A*搜索。总的来说，每一次的搜索的

算法时间复杂度仍然为 O(pq)，与 A*算法的时间复杂度相当。算法在实施之前，需

要对多层 topo 结构下的所有进出口节点组成路网，并加以存储，这是在搜索之前对

数据的预处理工作。由于室内地图的单层节点数，与室外地图比如武汉地图而言，

节点数要小好几个数量级，单层的路网节点数也一般不会超过 10 个，该算法的总体

时间复杂度和预处理路网所消耗的系统资源都在可控制范围内。

1.28 路网的抽象和权值确定

从 3.3.1 可知，路网的建立是在室内地图建立之时就可以被确定的，因为室内路

35网的节点全部依附于地图，在地图储存之初，所有的路网节点就已经确定了。在室

内地图的存储之中，我们可以看到有 exit 字段用以储存特殊的联通点：电梯和楼梯。

现实生活中，不同楼层之间的连接也大多以这两种方式达成。楼梯作为联通两个楼

层的节点，其节点之间的路径开销，可以以一个固定值存储。同理，电梯联通各个

不同的楼层，其连接的节点之间的相互开销也可以以一个固定值存储。

路网作为预处理过后，用作二次路经查询的网络，同样需要确定点以及相连接的

变权值。其中点的数据内容已经在 3.2.1 中进行介绍，确定点的唯一标示符为点在数

据库中的 id 字段。需要确定的是路网之间的联通关系，以及边的权值。其中有以下

几种边的权值需要确定：上下层楼梯点之间的权值；同一个电梯上下楼层之间的权

值；同层路网节点之间的权值。

由于起点和终点到路网的入口需要和路网对接，需要在建立路网时将权值统一为

double dist，也就是坐标之间的欧氏距离。以下说明了几种权值的模型和定值。

1）电梯与楼梯权值模型。电梯在路网中是一个很特殊的连接节点，因为在通过

这个节点时人消耗时间成本，但是消耗的体力成本几乎为 0。同样的问题存在于楼梯

节点，因为很难定量估计向上走一层楼梯的路径权值。换一个说法，需要比较用户

使用一次电梯的消耗，和用户在坐标系中前进的距离的大小与区别。这样的估计困

难而且没有必要。实际上，路网节点的作用在于拓扑地图之间的切换，与在同一 topo

地图中的移动是没有比较意义的，而且上下楼的开销只有在多个路网节点集中分布

在很小的范围内时，其比较才有意义，其它时候我们只考虑到其对于不同 topo 的连

通性的影响。基于以上几点，将电梯与楼梯的权值开销，定为一个远小于平均路网

节电开销数量级的值就可以了。举例说明，若路网弧的平均长度为 50 的话，可以将

电梯的联通开销定为 2，而将单层楼梯上下的开销定为 1。

2）同层路网节点之间的权值。同层路网节点之间的权值需要在室内路网创建之

时，对同层 topo 地图的所有出入口之间进行最短路径的算法查询。若单层 topo 地图

拥有 6 个路网入口，则需要对单层地图进行 C62=15 次 A*查询，用以确定单层地图中

的路网边，可以看出其总计算量是相当大的。由于这一步骤为路网的预处理步骤，

不会影响算法在实际查询中的效率。

361.29 总结

本节 3.1 介绍了室内地图的建立以及存储过程。室内信息的描绘以有限元描述空

间结构，其中，以简化的房间轮廓图简单模拟室内最小单位 location 的空间结构；以

三角划分的方式确定地图上在房间以外的路径点。室内地图模块出于系统整体使用

考虑，以数据库的方式存储点的基本信息，并在运算中将点重组成室内地图。出于

以上考虑，将室内地图以邻接表为基础表示形式，同时在适应数据库方面做出了一

些改进优化。

2.11 和 3.3 中具体描述了室内单层路径规划的算法流程以及其优化，提出使用 A*

算法作为室内路径规划的基础算法；比较确定了其估值函数 h(n)，根据节点规模，

动态选择欧氏距离或者曼哈顿距离作为估值函数；对算法中的 OPEN 以及 CLOSED

表的数据结构和存储提出了优化，提高了算法效率。同时，依据室外公路网络的原

理，笔者在本节提出了一种基于多楼层的路径规划算法流程，并对其算法流程进行

了分析说明，每次寻路需要进行 3 次 A*搜索，其总体时间复杂度高于单层搜索，但

仍与 A*算法为相同数量级。