复旦大学本科毕业设计

摘

要

随着定位技术的发展，定位服务、导航服务已经越来越为人们所熟悉。人们 开始逐渐抛弃纸质地图，使用电子地图。车载导航仪、手机导航软件的应用越来 越广泛，使用电子导航逐渐成为了出行的习惯。而在有些情况下，导航仪的用户 需要沿着特殊的自定义路线进行行进，而沿着路线行走本身便是其目的。在这种 情况下，则需要自定义路线导航。 本次设计基于 Android 平台，编写了自定义路线的手机导航软件，以实现自 定义路线导航功能。通过显示地图、显示定位位置、错路提醒、关键点提醒等功 能，帮助用户在自定义路线行进的情况下，找到正确的方向，顺利到达终点。 一个鸡蛋的暴走活动是自定义路线导航软件的一个典型应用。针对此活动， 我对软件进行了优化。导航软件在活动中取得了非常好的效果。 关键词：定位服务；自定义路线；导航软件；百度地图 API

1

复旦大学本科毕业设计

Abstract
With the development of positioning technic, LBS applications are widely used in our life. The traditional maps are gradually disappeared and electronic maps are used instead. The electronic maps like vehicle navigators and navigation apps makes a new style of navigation. However, these won’t work in special conditions, such as custom routine. That’s the reason the custom route navigator is needed. I designed a custom route navigator application on cell phone based on Android OS. It can display the map view and current location, alarm when the user arrive some given places or go wrong. This application will help the user arrive the terminus as soon as possible and keep them in the right ways. This application is used in a charity activity “the rampage of an egg”. I optimized this application so that it can be more suitable for this activity. Finally, it got a big success. Keywords : LBS, custom route, e-navigator, Baidu Map API

2

复旦大学本科毕业设计

目录
摘 要............................................................................................................................ 1 Abstract .......................................................................................................................... 2 1.绪论............................................................................................................................. 5 1.1 论文选题的背景及意义 ..................................................................................... 5 1.2 研究的目标及研究内容 ..................................................................................... 6 1.2.1 研究目标 ...................................................................................................... 6 1.2.2 研究内容 ...................................................................................................... 6 1.3 文章的组织结构 .................................................................................................. 9 2.理论基础................................................................................................................... 10 2.1 定位技术概述................................................................................................ 10 自律的定位技术 ...................................................................................... 10 基于地球表面的定位技术 ...................................................................... 10 基于卫星的定位技术 .............................................................................. 10

2.1.1 2.1.2 2.1.3

2.2 手机导航定位的原理 ....................................................................................... 11 2.2.1 GPS ........................................................................................................... 11 2.2.2 AGPS ........................................................................................................ 14 2.2.3 CELLID .................................................................................................... 15 2.3 百度地图 API ................................................................................................... 15 2.3.1 地图 API ..................................................................................................... 16 2.3.2 定位 API ..................................................................................................... 17 3. 总体设计方案 ...................................................................................................... 18 3.1 需求分析 ........................................................................................................... 18 3.1.1 基本功能 .................................................................................................... 18 3.1.2 后台功能 .................................................................................................... 18 3.1.3 软件性质 .................................................................................................... 19 3.2 系统整体构架 .................................................................................................... 20 3.2.1 软件结构 .................................................................................................... 20 3.2.2 数据流程图 ................................................................................................ 22 3.2.3 功能模块图 ................................................................................................ 24 4. 详细设计 .............................................................................................................. 26
3

复旦大学本科毕业设计

4.1 主体程序详细设计 ........................................................................................... 26 4.1.1 MainActivity 详细设计 ............................................................................... 26 4.1.2 MainService 详细设计 ................................................................................ 32 4.1.3 Activity 与 Service 的绑定关系 ................................................................. 33 4.2 程序权限 ........................................................................................................... 36 4.3 路径记录 ........................................................................................................... 36 4.4 错路判断 ........................................................................................................... 38 4.4.1 点到点距离、点到直线距离 .................................................................... 38 4.4.2 偏离点、偏离线段判定 ............................................................................ 39 4.4.3 点、线交替 ................................................................................................ 42 4.4.4 “交替算法”小结 ...................................................................................... 45 5. 针对某一活动的优化............................................................................................. 46 5.1 “一个鸡蛋的暴走” ......................................................................................... 46 5.1.1 “一个鸡蛋的暴走”活动简介 .................................................................. 46 5.1.2 暴走活动参与情况 .................................................................................... 48 5.2 针对“暴走”活动的优化 ................................................................................... 49 5.2.1 距离计算 .................................................................................................... 49 5.2.2 时间预测 .................................................................................................... 51 5.2.3 采样间隔 .................................................................................................... 52 5.3 数据采集........................................................................................................ 53

6.总结与展望............................................................................................................... 56 6.1 总结 ................................................................................................................... 56 6.2 对拓展系统的展望 ........................................................................................... 56 参考文献...................................................................................................................... 58 致谢词.......................................................................................................................... 60

4

复旦大学本科毕业设计

1.绪论
1.1 论文选题的背景及意义
随着 GPS 定位技术的日益增强，民用 GPS 定位的精度已经越来越高。通过 GPS 来实现的各种导航软件也从路径规划算法和用户体验等各方面日益改进。 车载 GPS 等导航设备、手机上的百度地图、谷歌地图等导航软件使用率也越来 越高。许多人都会使用导航软件来帮助自己到达自己的目的地。 导航软件首先通过 GPS 定位等技术得到用户当前所在的位置，通过用户的 指令得到用户需要达到的目的地， 然后通过一系列算法得到两点间交通的最优路 径。 在用户行驶、 行走过程中， 软件还会提供指示， 以帮助用户快速到达目的地。 然而在在有一些情况下，用户需要沿着某些“自定义路线”来行走，这种情 况常见于体育活动中。例如在定向越野、暴走劝募、马拉松、固定路线观赏等活 动中，导航软件的用户会沿着活动主办方所规定的“自定义路线”行进。 “自定义路线”有如下特点： 1. 非最优 在各种活动中“自定义路线”往往不是由“起始点”通向“目的地”的最优路 线。 例如在马拉松比赛中，“自定义路线”对起终点要求不高，然而对其总长度要 求非常严格，必须为 42195 米。其路线在大部分情况下都不是由“起始点”到 “目的地”的最优路线，而是一个不规则的环形。 2. 可能有重叠 “自定义路线”往往由于活动的某种目的而不止一次经过同一段路线。 例如在暴走劝募活动中， 为了满足总路线公里数的要求可能会重复同一段路 线。在定向越野活动中，可能只有一条道路通向某一必须经过的“中间点”，因此 必须折返行进。

3. 部分路线不包含在数据库中 “自定义路线”往往是组织者在实地考察时所规划， 部分线路可能是数据库没 有记录的小路。
5

复旦大学本科毕业设计

这些路线在地图上没有显示，一般导航软件在进行路线规划时也不会考虑这 些路线。因此需要人工将此类路线的定位信息加入导航软件。 4. 有关键地点 在“自定义路线”上，往往有一些点具有特殊的意义。 例如在马拉松、暴走等活动中补水点都是非常重要的一个路线上的节点。在 定向越野等活动中，参与者可能需要到某一特定地点寻找一些物品。在固定 路线的游览活动中，著名景点被特殊标注也是必不可少的一个功能。 本项目即是针对这种“自定义路线”而设计一种特殊的导航软件。针对以上所 提到的“自定义路线”特点本项目采用了完全不同的导航思路，以解决“自定义路 线”导航问题。

1.2 研究的目标及研究内容
1.2.1 研究目标
本项目的研究目标是开发一个基于 Android 平台的自定义路线导航软件，即 一个拥有自定义路线导航功能的手机 app。 首先作为一个手机 app，这个软件应该做到不占用太多内存、界面简洁、设 计人性化易上手，以创造更加良好的用户体验。 另一方面， 这个基于 Android 平台的 “自定义路线导航软件”设计是希望面向 所有同类型的“自定义路线”情况而设计一个具有普适性的程序框架， 已解决对各 种不同自定义路线导航的需求。 对于不同的路线，其路线数据当然不同，使用者或者活动使用者只需要将路 线数据进行更新，则可对新的、完全不同的“自定义路线”进行导航；若软件功能 有所更新，即程序有所改变，也应该不影响其对数据功能的读取、解析。

1.2.2 研究内容
在这个项目中，我的研究内容主要为以下几方面。
6

复旦大学本科毕业设计

框架结构设计 由于研究目的是适用于各种不同的自定义导航情景，因此要将软件设计为主 题程序、路径数据相分离的结构。在这样的情况下，只要保证程序中读取数据的 类不变，即可得到灵活的程序结构。 路径数据以文件的形式存储在软件中。当主题程序运行时，首先从该指定文 件中将路径数据读取出来，缓存到程序内存，接下来实现程序功能。 这也就是说，当主题程序进行更新时，例如增加了功能、变换界面、增加动 画的时候， 主题程序的代码会有所改变。然而只要读取路径数据的关键类读取数 据方式不更改，则可以使用不同版本的主题程序对相同自定义路线进行导航。 当自定义路线导航程序应用到不同路线情况的时候，只需要按照已经定义好 的数据格式将路线转换成标准的“路径数据”，则可以对不同路线进行导航。 定义数据 路径数据主要由三部分构成：自定义路线、关键点位置、关键点信息。 其中自定义路线由多个经纬度坐标点组成。 每一个坐标点由有序数对 （经度， 纬度）组成。而自定义路线数据则是由坐标点组成的二维数组。二维数组的每一 行为一段路程。 每一行的第一个坐标点会以不同的方式显示出来，并且可以进行 点击响应。 关键点位置为单个经纬度坐标点。每一个关键点位置与一组关键点信息一一 对应。 关键点信息为到达对应关键点时软件所给出的包括文字、图像等提示信息。 其中包括： 关键点地理名称 到达该关键点的提示信息 该地点的照片或指示标志等图片 主题程序结构设计 主题程序由两个主要部分组成：Activity 和 Service。

7

复旦大学本科毕业设计

Activity 为显示界面， 主要承担显示功能， 并不进行核心功能的实现。 其主要 承担的作用为： 显示地图、 显示当前用户位置、 显示自定义路线、 用户操作界面。 由于 Activity 在前台显示，因此用户通过它对导航软件进行操作。然而 Activity 只负责接收用户的操作信息，而并不对其进行处理。 Service 为核心模块，实现除显示外的程序大部分主题功能。功能包括：接收 GPS 定位信息，对定位信息进行分析以进行错路判断、关键点判断，当判断为有 效时发出不同形式的提醒信息， 对前台 Activity 的操作信息进行接收并处理等等。 由于 Service 为功能模块，没有显示界面，因此其信息只能交由前台 Activity 进 行处理。 Activity 显示模块与 Service 功能模块并行运行，程序互不干扰。而他们又绑 定（Bind）在一起，可以互相对对方的方法进行调用，并且以这种方式进行信息 的传递。例如当 Service 得到 GPS 定位信息后，调用 Activity 的.setLocation()方 法，将位置信息以自变量的形式传递过去，这样用户的当前位置就可以显示在 Activity 界面上了。 错路判断算法 自定义路线导航软件拥有错路提醒功能。为了实现这个功能，我设计了错路 判断算法。该算法可以使用非常小的运算量对极其复杂的路线进行错路判断。 变量 r 为错路判断阈值， 若当前用户位置距离自定义路线的最短距离超过 r， 则判定用户当前已经偏离自定义路径。 r 为可以随意改变的变量，在这次的项目中，我通过自己的判断来赋予 r 的 值。而在自定义导航软件未来的拓展中，可以将其改为由用户设定。 其他功能 自定义导航软件还包括：路径记录功能，关键点提醒功能，错路提醒功能等 等。 路径记录功能可以将用户行走的录像记录下来，并在地图上相应位置显示出 来。 当用户走到关键点时，软件会通过弹出对话框或者发出通知的方式来提醒用 户已经到达该地点，并且根据情况还可能对正确行进方向进行指示。

8

复旦大学本科毕业设计

当用户偏离正确路径时，软件也会通过弹出对话框或者发出通知的方式来提 醒用户已经偏离路线，以帮助软件用户尽快回到正确的路线上。

1.3 文章的组织结构
本片文章的第二章介绍了手机导航的 GPS、A-GPS、CELLID 三种方法、百 度地图 API、Android 平台开发等此次项目的基础理论；第三章从需求分析、整 体框架两个方面描述了软件的整体设计方案； 第四章记录了软件中的一些细节设 计；第五章是“自定义路线”导航的一个应用实例；第六章对软件的总体设计进行 总结并对未来的拓展进行展望。

9

复旦大学本科毕业设计

2.理论基础
2.1 定位技术概述
位置业务(LBS)是通过移动网络获取移动终端用户的位置信息, 再结合一些 电子地图、 资讯等信息为终端用户提供附加服务的一种增值业务。位置业务经过 长足的发展, 已经越来越被广大用户所接受。 在行业上的应用也使位置业务在经 济生活中起到了非常重要的作用。 定位技术是位置业务的基础, 位置业务的长足发展也促使了定位技术日新 月异的发展。 目前的定位技术主要分为自律的定位技术、基于地球表面的定位技 术和基于卫星的定位技术三大类。

2.1.1 自律的定位技术
自律的定位技术是基于移动物体本身的一些能力来计算位置, 例如通过采 集移动物体的运动的方向、 速度等信息来确定物体的位置, 这就是所谓的“Dead Reckoning”技术, 即“航位推算技术”也叫“盲定位”。自律定位另一项技术 是基于电脑的人工智能的视觉模式识别来确定移动物体在环境中的位置。 自律定 位技术在移动位置业务中的使用较少。

2.1.2 基于地球表面的定位技术
基于地球表面的定位技术, 顾名思义, 是通过架设在地球表面的一些测量 设备来确定移动物体位置的技术。其中包括角度到达技术(AOA),时间到达技术 (TOA),到达时间差技术(TDOA)。 应用到移动定位上是基于移动网络的定位。更常 用的是基于移动网络的 CELLID 以及 CELLID 和 TA 的技术,即通过小区识别码来 估算手机的位置,加入时间提前量 TA 是用以改进定位精度。

2.1.3 基于卫星的定位技术
基于卫星的定位技术是目前定位精度最高, 定位最准确的定位技术。目前, 卫星定位技术在使用方式上又分为 GPS,GLONASS 以及 Galleo 三种技术。

10

复旦大学本科毕业设计

全球定位系统（GPS）是美国从 20 世纪 70 年代开始研制, 历时 20 年, 耗 资 20 亿美元,于 1994 年全面建成,具有在海、陆、空进行全方位实时三维导航与 定位能力的新一代卫星导航与定位系统。 民用上, 目前使用的最多的也是这种定 位技术。 全球导航卫星系统(GLONASS)是前苏联从 20 世纪 80 年代初开始建设的与美 国 G PS 系统相类似的卫星定位系统,也由卫星星座、地面监测控制站和用户设 备三部分组成,功能上比较相似。与美国的 GPS 系统不同的是 GLONASS 系统采用 频分多址(FDMA)方式,根据载波频率来区分不同卫星(GPS 是码分多址根据调制 码来区分卫星)。 欧洲为了打破目前美国全球定位系统在这一领域的垄断,欧洲决定启动伽利 略计划, 建立自主的民用全球卫星定位系统(Galileo)。 将在 2002 年达到初始运 行能力,2005 年达到全球运行能力,正式商用为 2008 年。

2.2 手机导航定位的原理
手机导航 （Mobile Navigation） 就是通过导航手机的导航功能， 把你从目前所 在的地方带到另一个你想要到达的地方。手机导航就是卫星手机导航，它与手机 电子地图的区别就在于， 它能够告诉你在地图中所在的位置，以及你要去的那个 地方在地图中的位置， 并且能够在你所在位置和目的地之间选择最佳路线，并在 行进过程中的为你提示左转还是右转，这就是所谓的导航。 现在市面上的手机导航还分为三类，第一类是真正的通过太空中的卫星进行 GPS 导航，精度在 3-5 米，如天将军 T60 手机的导航；第二类是通过基站网络进 行粗略的导航的，称为 CELLID 导航，这种导航没有真正的通过卫星 GPS 导航 的精确， 一般定位误差为 100 米，如中国移动手机导航在室内定位时使用的就是 该技术；第三类是 AGPS+CELLID+GPS 定位，这种导航最为精确，在室内默认 是 CELLID 定位，在室外先利用 AGPS 搜到星图，达到快速定位，然后自动切换 到 GPS 高精度定位并进行导航，如中国移动手机导航利用的就是这种技术。

2.2.1 GPS
GPS（Global Positioning System）即全球卫星定位系统，是根据卫星所提供的
11

复旦大学本科毕业设计

时间、位置信息来进行导航的定位系统。一个 GPS 定位仪在搜索到四颗（或以 上）卫星的信息之后即可精确地确定自己所在的位置。GPS 定位系统在军事、民 用、商业领域都提供了非常大的帮助。

图 2-1 GPS 定位原理图示

GPS 接收机通过接收空中的 GPS 卫星发出的信号来确定自己的位置。 GPS 不 断发出信息，内容包含如下两点： 1. 此条信息发出的时间 2. 此条信息发出时卫星所在的位置 GPS 接收机在接收到这条信息后，首先通过信息传输所用的时间与光速来计 算自己与该卫星的距离。 GPS 接收机接收各个卫星的信息并计算每一段距离。 从 每一个卫星所得到的“卫星位置”与“距离”两条信息都可以确定一个球面。这些球 面的交点即 GPS 接收机的位置。这个位置信息可以直观地显示在地图上或转换 称为经纬度坐标。有时 GPS 接收机也可得到海拔高度信息。

12

复旦大学本科毕业设计

图 2-2 GPS 定位计算方法

最简单的 GPS 系统只能得到位置信息。而现在的 GPS 接收机也可以得到其 “移动方向”与“速度”信息。GPS 接收机通过先后两次的位置信息对方向、速度进 行判断。然而这样的判断方法有很大的不足。首先，得到方向、位置信息会有延 迟。更重要的是，当移动的速度很小时，即当先后两次的位置很接近（接近卫星 定位的误差）时，会对方向、速度的判断造成很大误差。因此一些 GPS 接收机 通过卫星信号的多普勒效应来进行这两条信息的判断。而一些更高端的 GPS 接 收机结合指南针、惯性导航系统来判断方向与速度。 一般来说，GPS 接收机需要接收到至少 4 颗卫星的信号才能够确定其位置， 其中包括经度、纬度、海拔高度三条信息。然而当其中的某一个变量已知时，即 可以只需要 3 颗卫星提供的数据。例如正在航海的船只、正在飞行的飞行器都知 道自己的高度信息。在这种情况下，如果不能够得到 4 颗卫星的信息也可以进行 定位。

13

复旦大学本科毕业设计

由上述原理可知，当我们在使用手机进行 GPS 定位时，首先需要进行搜星。 当搜索到 4 颗卫星之后，手机才能够精确地确定自己的位置。根据天气、地理位 置、当前卫星位置的不同，搜星所用的时间也不尽相同。

2.2.2 AGPS
A-GPS 技术即辅助全球卫星定位系统，是适用于手机 GPS 定位的一种辅助 方法。手机先与基站通信，获得有关卫星的信息。A-GPS 具有启动速度快（不需 冷启动） 、抗干扰能力强等特点。 A-GPS 则利用手机基站的信号，辅以连接远程服务器的方式下载卫星星历 (Orbital Data)，可再配合传统的 GPS 卫星接受器，让定位的速度更快。通过卫星 星历，手机可以知道当前空中 GPS 定位卫星的位置，并更快地进行搜星。 另一方面，普通的 GPS 系统是由 GPS 卫星和 GPS 接收器组成，与普通的 GPS 不同，A-GPS 在系统中还有一个辅助服务器。 在普通 GPS 网络中， 系统第一次给出位置大约需要 30~40 秒时间。 因为根据 卫星信号进行 GPS 定位需要卫星星历数据，而从卫星上下载星历数据非常慢， 其传输速度大概只有 50bit/s，下载信息需要很长的时间。而在数据传输期间，如 果由于天气等原因导致数据传输中断，则传输需要重新开始。 在 A-GPS 网络中， 接收器可通过与辅助服务器的通信而获得定位辅助。 在蜂 窝移动通信系统中， AGPS 系统通过手机定位服务器作为辅助服务器来协助 GPS 接收手机完成测距和定位服务， 辅助定位服务器有比 GPS 接收器强大得多的 GPS 信号接收环境和能力， 在这种情况下， 辅助定位服务器通过网络与手机的 GPS 接 收器通信而提供定位协助。 通常情况下，一个标准的 GPS 接收器需要至少 4 颗 GPS 卫星才能进行 2D 定位。另外，还需要有足够的处理能力来把卫星的数据转换成坐标，使用 AGPS 定位方式，定位的计算任务都由辅助定位服务器完成。

14

复旦大学本科毕业设计

2.2.3 CELLID
CELLID 即 Cell Identity（蜂窝识别） ，是蜂窝网络基站的编号。在 CDMA 网 络中， 将地理区域划分成若干个小区， 每一个小区拥有其自己的 ID， CELL ID。 即 CELL ID 由 16 位二进制位组成，在同一个城市中的不同位置，基站的 CELL ID 是不相同的，因此通过 CELL ID 就可以定位到具体的服务小区。 若小区为全向小区，则定位的范围为圆心为基站半径为小区半径的一个圆内。 若小区分扇区,则可更精确地定位。 基于 CELLID 的定位技术是一种最基本的定位方法,适用于所有的蜂窝网络。 它不需要移动台提供任何定位测量信息,也无须对现网进行改动,只要在网络侧 增加简单的定位流程处理即可, 因而最容易实现。 目前这种定位技术已经在各移 动网络中广泛使用。 这种定位方法的精度完全取决于移动台所处小区的大小,从几百米到几十公 里不等。在乡村地区,小区的覆盖范围很大,所以 CELLID 的定位精度很差。 而城区环境的小区覆盖范围较小,一般小区半径在 1～2km,对于繁华的城区, 有可能采用微蜂窝,小区半径可能到几百米,此时 CELLID 的定位精度将相应提 高为几百米。 由于 CELLID 定位不需要移动台的定位测量, 并且空中接口的定位信令传输 很少, 所以定位响应时间较短, 一般在 3s 以内。

2.3 百度地图 API
当今手机导航软件处于三足鼎立的局面，百度地图、高德地图、谷歌地图各 有优劣。 首先，从用户的角度来讲，百度地图、高德地图对于国内的地理信息收集的 比较完整，而谷歌地图的优势在于全球地理信息的完善，主要为境外。首先从这 一点上考虑，我放弃了使用谷歌地图 API 的想法。 其次，从网上众多地图 app 开发者的反馈来看，高德地图的兼容性比较差，
15

复旦大学本科毕业设计

尤其是在使用 JavaScript 开发网页 app 时，经常出现兼容性问题。考虑到自定义 路线导航软件的未来拓展方向，即跨平台 本项目中使用百度 Android API 来实现导航软件所需要的“显示地图”以及“定 位”两大功能。

2.3.1 地图 API
本项目中使用百度地图完成的显示地图功能包括：地图显示、路线绘制、位 置标注、关键点标注等等。 首先通过百度地图 API 来进行地图显示、路径绘制、关键点标注等与地图界 面相关的软件功能。 通过百度地图 API 可以访问百度地图数据， 并将数据显示在 软件中。 国际经纬度坐标标准为 WGS-84,国内必须至少使用国测局制定的 GCJ-02,对 地理位置进行首次加密。百度坐标在此基础上，进行了 BD-09 二次加密措施,更 加保护了个人隐私。百度对外接口的坐标系并不是 GPS 采集的真实经纬度，需 要通过坐标转换接口进行转换。 在进行路线绘制时，需要得到路口等节点的经纬度，并使用线段将节点连接 在一起。为了得到百度地图 API 所能接受的 BD-09 经纬度坐标，需要使用“百 度地图坐标拾取系统”来进行经纬度坐标查询。该系统地址如下： http://api.map.baidu.com/lbsapi/getpoint/index.html 百度地图坐标拾取系统还支持“坐标反查”功能， 可以将 BD-09 百度经纬度坐 标显示在地图相应的位置上。 在显示用户的定位位置时，使用的坐标同样是百度经纬度。若使用百度定位 提供的 BD-09 二次加密之后的 GPS 坐标，则可以与百度地图 API 相配合，无偏 差地显示将用户位置显示在地图上，而不需要进行接口转换。 当绘制关键节点例如“打卡点”等的时候，也通过百度地图坐标拾取系统来查 找该点 BD-09 坐标，并将其无偏差显示在百度地图上。
16

复旦大学本科毕业设计

2.3.2 定位 API
通过百度定位 API 来进行定位服务， 通过百度定位 API 可以由百度处得到经 纬度信息。然而百度所得到的信息并非原始 GPS 定位信息。 百度 Android 定位 SDK 使用了 GPS+基站+Wi-Fi 混合定位的方法。 在百度官网上，对其混合定位精度描述如下： 1、GPS 定位： 根据设备 GPS 芯片和 GPS 卫星实现定位， GPS 定位在室内是 不可以使用的。GPS 定位精度和芯片本身以及实际使用环境有关，一般 情况下，GPS 定位精度在 10m 左右。 2、基站定位： 根据设备获取的基站信息实现定位， 基站定位精度一般不受使 用环境影响， 主要和基站的覆盖半径有关。 百度的基站定位服务精度目前 在 200m 左右。 3、Wi-Fi 定位：根据设备获取的 Wi-Fi 的信息进行定位，Wi-Fi 定位精度一 般不受使用环境影响，主要和 Wi-Fi 半径，密度有关。百度的 Wi-Fi 定位 精度目前在 20m 左右

而如果需要正常使用该导航软件，则需要定位处于“GPS 定位”的模式下。 百度地图的混合定位方式虽然是一种优化， 然而其不精确的“基站模式”有时会干 扰导航软件的正常运行。因此在程序中对其进行“模式判断”。 一般在室外，不考虑 Wi-Fi 定位方式，因此只有基站定位与 GPS 定位两种模 式。在软件刚刚打开时，由于手机处于搜星阶段，尚未接到 GPS 卫星信号，因 此处于基站模式。当搜索到 GPS 卫星信号时，会自动切换到 GPS 定位模式。由 于基站模式的定位精度（200m）与 GPS 定位模式的精度（10m）差别非常大， 因此简单地使用一个中间阈值进行判断即可过滤掉基站定位模式。 我在程序中采 用了 15m 的阈值，当精度小于 15m 时正常工作；当精度大于 15m 时，软件不工 作，等待搜星成功。

17

复旦大学本科毕业设计

3. 总体设计方案
3.1 需求分析
3.1.1 基本功能
一个最简单的手机定位“自定义路线”导航软件应当具有如下功能 1. 显示地图 2. 显示“自定义”路线、关键点信息 3. 显示手机软件用户的当前位置 如果用户在行走过程中，使用“自定义路线”手机导航软件，能够看到地理信 息（如街道名称，标志性建筑的名称） 、准确路线、用户当前的准确位置（精度 大约 10m 左右） ，则用户即可以根据周围的建筑、路牌以及从软件中得到的有效 信息对正确方向、正确路线进行判断。

3.1.2 后台功能
这样的基础功能可以实现“导航”功能。然而我们需要考虑到，如果一个“GPS 导航仪”具有这些功能是完全可以的。 而手机软件一方面具有便于携带、 成本低、 便于传播等的优势， 另一方面也有许多劣势。比如手机导航软件不能像导航仪一 样，一直处于前台。 原因主要有两条。一方面手机的其他功能无法使用。例如很多人喜欢一边行 进一边听歌、拍照上传，同时软件也不能妨碍用户电话、短信、微信等手机基本 功能。另一方面对于现在的大屏幕 Android 手机来说，屏幕常亮对电量的消耗非 常大。因此，此导航软件应该具有后台运行的功能。 功能如下： 4. 可以后台运行，后台接收 GPS 定位信息 但当暴走小能手处于后台运行时，用户无法看到路线和关键点信息。因此软件应 当再增加下述两个功能。 5. 错路判断提醒（无论前后台工作） 6. 关键点监听提醒（无论前后台工作）
18

复旦大学本科毕业设计

当自定义路线导航软件在前台运行时，对用户进行 5、6 中的提醒十分容易， 可以利用 dialog Activity，即弹出一个对话框，来提醒用户“您已走错路”或者“您 已到达某关键位置”。但当“暴走小能手”在后台运行时，则需要通过 Android 系 统的 Notification 机制来对用户进行提醒。 就像微信等软件接收到消息时一样，当用户走错路、走到关键点时，会发出 一条通知来通知用户， 通知产生式有系统所设置的铃声。通知在消息栏中会有显 示，用户看到消息后，点击该消息可以回到自定义路线导航软件界面。 7. 发出通知进行提醒。通知有响铃，驻留在消息栏中，点击消息可以回到软 件。

3.1.3 软件性质
在“自定义路线”导航设计过程中，我对软件的定位进行了简单的考虑。一方 面这种特殊的导航软件功能比较单一，仅仅具有导航功能；另一方面，这种导航 所应用的范围又十分有限， 对于大部分用户来说，这个软件可能仅仅只为参加一 个活动使用，在其他时候对这个软件没有需求。因此基于上述两点，我认为“自 定义路线”导航软件应该是一个“小软件”。 我所谓的“小软件”小在三个方面：存储空间、内存占用、耗电量。 首先，软件所需存储空间应该非常小，方便用户快速安装与卸载。在参加活 动前安装，活动结束后即可轻松卸载。 其次，由于软件拥有的功能不多，因此占用的手机内存也应该比较少。这涉 及到错路判断等算法的优化级别问题。应当将软件中涉及到的算法尽可能简化。 最后，在固定时间内，软件进行的 GPS 定位次数越少，耗电量越少。另一方 面， 可是让程序在后台运行而不需要一直打开软件界面导致屏幕常亮，也是一种 省电的好方法。

19

复旦大学本科毕业设计

3.2 系统整体构架
3.2.1 软件结构

图 3-1 自定义路线导航软件结构

软件结构主要由两大部分构成。一部分是负责软件功能实现的程序，另一部 分则是存储“自定义路线”、关键节点等信息的数据部分 主题程序： 主题程序由两个主要部分组成：MainActivity 和 MainService。 其中，MainActivity 为前台，主要负责前台显示、用户交互。 在“自定义路线”导航软件中，绝大部分信息都是通过前台 MainActivity 传递给 用户。这些信息包括：地图、路线、位置信息、关键节点、提醒信息、路径记录 信息。这些信息以图片、文字等各种形式在 Activity 中显示，以尽最大可能帮助 用户找到正确的自定义路线。 在软件的使用过程中，用户也需要与软件进行交互，这其中包括：地图手势 操作、地图复位操作、开始结束记录路径、切换程序等等。这些用户操作信息的 读取也都由前台 MainActivity 来实现。然而 MainActivity 并不负责对这些操作进 行响应，它只是将数据传递给后台的 MainService，再由 MainService 进行处理。
20

复旦大学本科毕业设计

MainService 为后台核心模块程序，主要负责数据处理、记录等，也有少量的 用户交互作用。MainService 主要实现的功能是接收 GPS 定位数据，对数据进行 分析、判断，触发关键点提醒、错路提醒等功能。 路线数据： 路线数据由三部分构成：路径数据、关键点数据、关键点信息。 在百度地图 API 中，坐标点由 GeoPoint 类标识。GeoPoint 由有序的经度、纬 度数对组成。它包含两个整形变量，分别是经度、纬度乘以 1e6 并强制转换为整 数得到的结果。这也就是说，使用百度地图 API 中 GeoPoint 表示坐标点，最多 精确到小数点后六位。

图 3-2 数据存储示意图

路径数据是由 GeoPoint 二维数组组成。数组的每一行可以看做一个一维数 组。 每一个一维数组中各个坐标点依次连接起来组成一段路线。每一个一维数组 首位相连组成整个自定义路线的路径。每行第一个坐标点标记不同，并且点击可 以触发事件。复写 RouteOverlay 图层的 onPatch()方法可以修改所触发的事件。 在这里暂时没有用到这个功能。 关键点数据为一个 GeoPoint 对象，标识着关键点位置。 关键点信息与关键点一一对应，其中包括关键的地理名称（字符串） 、信息 （字符串） 、附带图片指示。
21

复旦大学本科毕业设计

例如： 30.725925, 121.364067 隆安东路杭州湾大道路口 请左转

图 3-3 隆安东路杭州湾大道路口对应图片

3.2.2 数据流程图
在软件运行时，其主要数据流为 GPS 定位信息的传递。 信息传递的流程如下图所示：

22

复旦大学本科毕业设计

图 3-4 软件数据流向图

首先， MainService 中的位置监听器在不断运行， 每相隔固定时间即获取 GPS 定位信息。 该信息的格式为百度的位置封装 BDLocation，其中包括经度、纬度、 方向、精度四个信息。 接着， LocationListenner 得到 GPS 信息后， 触发其 onReceivedLocation 方法。 在该方法中，调用 MainActivity 的 setLocation 方法，在调用是，将得到的 BDLocation 作 为 自 变 量 。 MainService 通 过 这 种 方 法 将 得 到 的 信 息 传 递 给 MainActivity。 最后， MainActivity 的 setLocation 方法将其自变量输入 LocationData。 其中， LocationData 已经在程序中被嵌入 LocationOverlay 之中，亦即 LocationOverlay 显示的是 LocationData 中的数据。当 LocationData 中的数据改变后，显示的位置 信息也会随之改变。接下来刷新地图，新的位置信息便显示在了位置图层上。 完整的流向为： MainService.LocationListenner MainActivity.setLocation MainActivity.LocationOverlay 从卫星中得到的 GPS 定位信息经过这三步之后，便可显示在地图上。   MainService  MainActivity   MainActivity.LocationData

23

复旦大学本科毕业设计

3.2.3 功能模块图

图 3-5 软件功能模块图

自定义路线导航软件从整体功能设计上，可以将功能分为四大模块：显示模 块、交互模块，提醒功能模块、记录模块。 显示模块中包括地图显示、用户当前位置显示、自定义路线显示、记录路径 显示等功能。用户位置、自定义路线、所记录的路径都会根据坐标无偏差地显示 在地图上。对于一个导航软件来说，其显示功能模块是最重要的功能模块。地图 位置、路线的精确显示胜过其他所有的附加功能。 交互模块包括居中按钮、记录按钮、缩放按钮、手势操作。在使用软件的过 程中，用户点击位置居中按钮，地图会进行平移，直到用户的当前位置处于屏幕 的正中央。 用户点击记录按钮可以控制开始、 结束路径记录并显示所记录的路径。 使用地图上的缩放按钮盒手势操作都可以对地图进行缩放， 同时手势操作还可以 对地图进行平移、旋转、改变俯仰角等等操作。 提醒模块包括错路提醒、关键点提醒两项功能。当用户的位置接近关键点， 或者当用户的位置离开自定义路径一段距离以后会触发提醒。 提醒的方式有两种： 当用户正在使用这个软件时， 弹出一个对话框以提醒用户；当用户正在使用其他 软件或手机黑屏时，发送一条通知以提醒用户。

24

复旦大学本科毕业设计

记录模块包括路径记录和日志记录两项功能。其中日志记录是在程序编写过 程中进行调试使用的， 对用户并没有什么帮助。路径记录功能可以记录用户走过 的路径，并将其显示在地图上。 显示模块的功能由 MainActivity 实现； 提醒模块与记录模块由 MainService 实 现；交互模块的功能由两方共同实现。

25

复旦大学本科毕业设计

4. 详细设计
4.1 主体程序详细设计
导航软件主要由两个部分构成，前台主要起显示、交互作用的 Acticity，以及 后台起位置信息收集、信息处理功能的 Service。 Activity 和 Service 同时运行，互不干预，而又相互关联绑定在一起。他们的 工作方式并非线程并行，或者进程并行方式，而是其独有的并行运行方式。 Activity 和 Service 处于同一进程的同一线程中。如图 4-1：

图 4-1 主题程序结构

4.1.1 MainActivity 详细设计

图 4-2 MainActivity 结构

类名为 MainActivity.class，主要包含地图图层、位置图层、路线图层、自定 义图像图层。
26

复旦大学本科毕业设计

地图图层（MapView） 地图图层类名为 MapView， 显示地图信息， 如街道、 房屋以及地理名称等等。 与我们平时所看到的地图一样。 下图为地图图层信息的示意图：

图 4-3 地图图层

位置图层、路线图层、自定义图像图层叠加在地图图层之上。从视觉效果上 来看， 其图案遮盖住地图； 从程序编写角度来看， 四个图层相互独立， 互不影响。 地图图层提供有关地图的各类按键、手势操作，包括：缩放、旋转、改变俯 角等。 缩放： 使用地图右下角的缩放按键， 或通过两个手指点击地图图层后进行“分 离”、“聚合”手势可以分别进行放大、缩小。双击屏幕时，会以双击点为中心点放 大地图。 旋转：以两个手指点击地图图层后的旋转手势可以旋转地图图层。地图图层 本身显示的地图方向为正北（上）正南（下） 。地图图层旋转之后，方向改变， 屏幕左上角会出现一个指南针来指示防线。单击指南针图标可以重置地图方向 （回到正北正南） 。

27

复旦大学本科毕业设计

在图中可以看到左上角的指南针图标 图 4-4 地图图层旋转示意图

改变俯仰角： 使用两个手指点击地图图层，之后手指向上或向下平移可以改变地图俯仰角。 在地图到达一定放大级别之后，可以看到 3D 地图效果。鸟瞰角度的 3D 地图效 果如下图 4-5 所示：

图中所示高楼为我校光华楼 图 4-5 地图图层俯视示意图
28

复旦大学本科毕业设计

路线图层（RouteOverlay） 路线图层记录了这次“暴走”活动的行走路线、起终点、关键节点信息。 由于活动的路线十分繁琐，因此路线图层的代码也十分冗长。在软件中，这次活 动的路线由约 150 个点先后连接而成。 代码中记录了这 150 个点的百度经纬度坐 标。 路线图层+地图图层示意图如下图 4-6：

图中蓝色路线为此次“暴走”活动规定路线 图 4-6 路线图层

29

复旦大学本科毕业设计

位置图层（LocationOverlay） 位置图层中包含软件用户的位置、方向、GPS 定位精度等信息。位置图层叠 加在地图图层之上，将用户的位置准确的显示在地图之上。 位置图层+地图图层示意图如下图 4-7：

图中所示地点为复旦大学南区 37 号楼楼下 图 4-7 位置图层

将图示放大：

图 4-8 位置图层放大
30

复旦大学本科毕业设计

可以看到，地图图层的显示由一个箭头和一个小圆圈组成。 箭头所在的位置为手机用户的位置；箭头所指示的方向为用户移动的方向； 圆圈代表此次 GPS 定位的精度范围。 自定义图像图层（GraphicsOverlay） 暴走小能手软件包含路径记录功能。而自定义图像图层显示用户所行走过的 路线。 自定义图像图层将用户行走过程中记录下来的坐标点先后相连，并显示在地 图上。 自定义路线图层+效果如下图所示

图 4-9 自定义路线

31

复旦大学本科毕业设计

4.1.2 MainService 详细设计
类名为 MainService.class，主要由位置监听器（LocationListenner）和关键点 监听器（NotifyListenner）组成。

图 4-10 MainService 结构

其中，位置监听器负责接收 GPS 定位信息，包括经度、纬度、方向、经度。 关键点监听器负责监听手机用户是否到达某一些关键的位置，例如打卡点、补水 点等。 位置监听器 位置监听器为百度地图 API 所提供的最重要的接口之一。 开发者可以通过复 写“位置监听函数（onReceiceLocation） ”来完成所需要的功能。从函数名称也可 以知道，该位置监听函数的触发是“接收到 GPS 定位信息”。 在建立位置监听器时， 可以通过 LocationClientOption 类来对该监听器进行设 置。 LocationClientOption 中可以设置如下三点： GPS 方式是否打开、 经纬度类型、 采集 GPS 位置信息的时间间隔。 在程序中，我们将其设置为： option = new LocationClientOption(); option.setOpenGps(true);//打开gps
32

复旦大学本科毕业设计

option.setCoorType("bd09ll"); option.setScanSpan(5000);

//设置坐标类型 //间隔5000ms

即 GPS 打开、bd09ll（bd-09 坐标） 、5000（5 秒） 。 而在 onReciveLocation 位置监听函数中，我们将得到的 GPS 位置信息，通过 调用 MainActivity 实例中方法的方式， 传递给 MainActivity 并显示在前台界面上。 关键点监听器 在声明一个关键点监听器之后，需要对其中 4 个成员变量进行设置：经度、 纬度、半径、坐标类型。 其中经纬度代表该监听器所监听的关键点的位置；半径代表这个关键点的敏 感度，即距离该点有多远时触发其监听函数；坐标类型同样为百度经纬度坐标。 例如： public MyNotifyListenner myNoListener = new MyNotifyListenner(); myNoListener.SetNotifyLocation(31.304607, 121.51313, 30, "bd09ll");

上述代码中，首先声明了一个关键点监听器“myNoListener”。接着，将经度 设置为 31.304607，纬度设置为 121.51313，半径设置为 30（30 米） ，坐标类型设 置为“bd09ll”（百度经纬度） 。 当符合特定条件时，触发关键点监听器中的 onNotify 函数。 关键点监听器 onNotify 函数的触发条件为： 位置监听器收到 GPS 定位信息， 并且位置在以关键点为圆心、以设置长度为半径的圆形区域内。 在程序中，我复写了 onNotify 函数，使其完成 “弹出 Dialog Activity 提示” 或“发送 Notification 提示”的功能。 在程序编写时，需要为活动中所规划的每一个关键点设定一个关键点监听器。

4.1.3 Activity 与 Service 的绑定关系
由上述功能和结构关系，Activity 和 Service 之间需要进行通信。最主要的信 息流即 Service 将位置监听器得到的 GPS 定位信息传递给 Activity， 并在 Activity 上显示。
33

复旦大学本科毕业设计

在 Android 系统中，经常将 Activity 和 Service 进行绑定。绑定之后，Activity 和 Service 可以互相调用对方的函数，并且通过这种方式进行通信。 Service 与 Activity 建立连接的流程与 TCP 连接中“三次握手”建立连接的方式 非常相似。流程如下： 1. Activity 向 Service 发出绑定申请 2. Service 将“自己”（MainService 实例本身）返回给 Activity 3. Activity 将“自己”（MainActivity 实例本身）返回给 Service 为了完成上述流程，需要完成如下步骤：

首先，在 Activity 中声明全局变量 MainService，以将 MainService 的一个实 例对象存储在 Activity 里而相同的， Service 中也声明 MainActivity 全局变量， 在 将 MainActivity 实例存储在 Service 里。 接下来，在 Service 中复写被 Activity 所主动要求绑定时触发的函数 IBinder onBind。 代码如下所示： @Override public IBinder onBind(Intent arg0) { return new ServiceBinder(); } public class ServiceBinder extends Binder { public MainService getService(){ return MainService.this; } public void SetOnActivity(MainActivity mainActivity){ this.mainActivity = mainActivity; } 上述代码主要完成如下功能： 1. 当 Service 收到 Activity 主动要求绑定的信息时，返回 ServiceBinder 方法 2. ServiceBinder 方法的功能是返回 MainService 实例本身 3. 构造一个方法能够将一个 MainActivity 实例存储在自己之前声明的变量中， 供 Activity 调用
34

复旦大学本科毕业设计

在 Activity 中编写如下代码： conn = new ServiceConnection(){ @Override public void onServiceConnected(ComponentName name, IBinder service) { mainService = ((MainService.ServiceBinder)service).getService(); mainService.SetOnActivity(MainActivity.this); } @Override public void onServiceDisconnected(ComponentName name) {} }; 上述代码主要完成如下功能： 1. 创建 ServiceConnection 实例 conn。 2. 复写 conn 中的 onServiceConnected 函数。 该函数在 Activity 向 Service 主动发 出请求信息的时候触发。onServiceConnected 函数首先通过 Service 中的 IBinder 方法得到 Service 中的 ServiceBinder 方法，再把 ServiceBinder 方法的 返回值（MainService 实例）存储在之前声明的 MainService 变量中。 3. 现在的 Activity 有了 MainService 实例，则可以调用 MainService 实例中的方 法。于是 Activity 调用 Service 中的 SetOnActivity 方法，将 MainActivity 实例 自己存储在 Service 之前声明的 MainActivity 变量中。 最后，Activity 向 Service 主动发出绑定申请，然后触发两边实例中的一连串 方法： bindService(si, conn, Context.BIND_AUTO_CREATE); 经过了这一行指令后，当前程序中的 MainActivity 实例和 MainService 实例 已经成功绑定在一起。他们可以互相调用对方实例中的方法，并将自己实例中的 一些变量通过调用对法方法的方式传递给对方。 我在 MainActivity 中构造了方法 setLocation(BDLocation)。该方法的自变量 即是从百度定位 API 中直接得到的 GPS 定位信息包 BDLocation，包括经度、纬 度、方向、精度 4 个变量。setLocation 方法的主要作用是将 BDLocation 中的信 息显示在 Activity 中的 LocationDemo 位置图层上。
35

复旦大学本科毕业设计

Activity 和 Service 绑定之后，Service 可以调用 Activity 中的方法。因此每当 Service 中的位置监听器得到新的 GPS 定位信息之后， 就调用.setLocation()方法， 将 GPS 定位信息传递给 Activity 并显示在界面上。使用相同的方法，Activity 也 可以告知 Service 自己是否处于活跃状态。

4.2 程序权限
在软件编写时，为此“自定义导航”开放如下主要权限：

自定义导航软件有“打开 GPS 定位”、“获得 GPS 精确信息”两项权限。

自定义导航软件 app 有“不被系统清除”的权限。 Android 系统有一种优化，为了保持手机内存充裕，系统时常自动清除长时 间在后台处于休眠状态、而程序状态存储在手机内存中的程序。 “自定义路线”导航软件由于功能模块 MainService 在后台运行，当前台 MainActivity 显示模块处于休眠状态时，系统认为此程序处于休眠状态。若用户 长时间不回到程序界面，系统可能会将程序清除内存。在这样的情况发生之后， 用户再次回到程序中（操作为打开 MainActivity 前台模块）时，软件会出现闪退 现象。这是由于 MainService 被系统关闭，其中的 Binder 异常断开连接导致的。 因此我为此应用程序开放了 persistent 权限，这样系统不会由于其优化功能 而将 MainService 关闭，软件可以长时间后台运行，并且不会出现闪退 bug。

4.3 路径记录
在软件中，我利用 GraphicOverlay 来对所记录的路径进行显示。
36

复旦大学本科毕业设计

GraphicOverlay 是百度地图的绘图图层，它只能够在地图上显示由坐标点 GeoPoint 组成的一维数组，即这些坐标点依次相连组成的一条线。 然而在执行路径记录功能的时候，程序并不知道用户何时开始记录，何时停 止记录，因此也就不知道路径记录的时间、所记下数据点的个数。由于数组的声 明是需要常量 int 值作为数组长度，因此我利用了 Java 特有的 ArrayList()类实现 了数据记录功能。 首先在程序中声明一个 List PointList 和一个 GeoPoint 数组 route。
List PointList = null; GeoPoint route[] = null;

当用户点击开始记录按钮时，程序将 PointList 声明为 ArrayList。
PointList = new ArrayList();

之后，每得到一次 GPS 定位信息，都会将这次得到的信息存入 PointList。而 信息的存入使用的是 ArrayList.add()方法。
GeoPoint comp = new GeoPoint((int)(Location.getLatitude()* 1E6), (int)(Location.getLongitude()* 1E6)); PointList.add(comp);

最后当用户按下停止记录按钮时，首先根据当前 PointList 的长度声明数组 route 的长度，然后将 PointList 中的 GeoPoint 数据一个个存入数组 route 中，最 后将数组 route 显示在地图上。 route = new GeoPoint[PointList.size()]; for(int i = 0 ; i < PointList.size() ; i++){ route[i] = (GeoPoint) PointList.get(i);} Line.setPolyLine(route);

然而这样的设计是有很大缺陷的。当所需记录的路径很长时，用户按下停止 记录之后可能会有很长时间程序都没有能够将路线显示出来， 这是由于程序正在 一个个的将 GeoPoint 数据存入数组中，而数据越多所需时间就越长。

37

复旦大学本科毕业设计

4.4 错路判断
4.4.1 点到点距离、点到直线距离
在使用百度地图 API 时，表示坐标点的类为 GeoPoint，其中包含百度经度、 纬度两条信息。 通过百度 API 所提供的 getDistance(GeoPoint , GeoPoint)方法可以 获取两个点之间的距离。通过这种方法可以理论上无偏差地实现错路判断算法。 以下用方法 D 来表示获取距离，例如： D (A,B) D (AB, C) 表示 A、B 两点之间的距离 表示点 C 到直线 A、B 的距离

图 4-11 点 P 到直线距离 D(MN, P)

如图所示情况 设 a = D(M , P)，b = D(N , P)，c = D(M , N) 由海伦公式，∆MNP 的面积为：

S∆MNP = √������(������ − ������)(������ − ������)(������ − ������)
（4-1） 其中������

= (������ + ������ + ������)/2

将 p 带入公式，得

������∆MNP =

√(������ + ������ + ������)(������ + ������ − ������)(������ + ������ − ������)(������ + ������ − ������) 4
（4-2）

将线段 MN 视为∆MNP 的底， 则点 P 到直线距离 h = D(MN , P)视为∆MNP 的
38

复旦大学本科毕业设计

高。由此可得，点到直线距离可以表示为：

������(������������, ������) = ℎ =

√(������ + ������ + ������)(������ + ������ − ������)(������ + ������ − ������)(������ + ������ − ������) 2������
（4-3）

其中 a = D(M , P)，b = D(N , P)，c = D(M , N)。

4.4.2 偏离点、偏离线段判定
在推算算法时，使用字母 r 来表示阈值，即偏离路线多远之后算是走错路。 r 为浮点数，单位是“米” 。 在程序中， 路径数据由许多坐标点组成， 将坐标点依次相连之后形成了路线。 在接下来的叙述过程中， 我将相邻点所连接形成的线段称为“路径线段”简称 “线” 。 将坐标点简称“点”。 因此，可以将将路径数据视为为点、线的交替连接，并分别判断当前位置是 否偏离了路径数据中所包含的点、线，并根据是否偏离所有点、线来判断是否偏 离了路线。 易得： 若当前位置偏离所有点、线，则判定偏离自定义路线。 若当前位置未偏离至少一个点或至少一根线，则判定未偏离自定义路线。

偏离点： 若：当前位置 P 与某路径点 N 距离超过 r 时，我们认为，用户偏离了点 N。 偏离条件：

������(������, ������) ≥ ������
（4-4） 因此点 N 的未偏离范围如下图所示：

39

复旦大学本科毕业设计

图 4-12 点 N 的未偏离范围

偏离直线： 若：当前位置 P 与某路径线段 MN 距离超过 r 时，我们认为，用户偏离了路 径线段 MN。 偏离条件：

������(������������, ������) ≥ ������
（4-5）

当然，当位置与路径满足 D(MN,P) < r 时，也并不意味着当前位置 P 不偏离 路径线段 MN。 例如下图所示这种状况：

图 4-13 点 P 满足公式（4-5）但偏离的情况

在这种情况下，及时满足 D(MN,P) < r，也算作点 P 偏离路径线段 MN。在 这种情况下，∆MNP 中∠������或∠������成为了钝角。

40

复旦大学本科毕业设计

以∠������为钝角为例：

cos ∢������ < 0
（4-6）

亦即

������(������, ������)2 + ������(������, ������)2 − ������(������, ������)2 cos ∢������ = √������(������, ������)2 + ������(������, ������)2
（4-9）

而同理，当∠������为钝角时

������(������, ������) > √������(������, ������)2 + ������(������, ������)2
（4-10）

因此，点 P 未偏离路径线段 MN 的条件又以下三个条件组成。

������(������������, ������) < ������ ������(������, ������) < √������(������, ������)������ + ������(������, ������)������ ������(������, ������) < √������(������, ������)������ + ������(������, ������)������
（4-11）

因此，路径线段 MN 的未偏离范围如下图 4-14 所示

图 4-14 路径线段 MN 的未偏离范围
41

复旦大学本科毕业设计

结论： 若当前位置点 P 同时满足这三个条件， 则当前位置点 P 未偏离路径线段 MN 若当前位置点 P 不满足至少一个条件，则当前位置点 P 偏离路径线段 MN

4.4.3 点、线交替
在每得到一次 GPS 定位信息后，都与所有点、路径线段进行判断是否偏离， 从理论上是可行的错路判断方法。 然而在实际应用过程中，路径点可能数量很大。例如一个路径数据包含 100 个点，则会产生 99 个路径线段。在每接收一次 GPS 信息之后，都要进行 199 此 计算判断，其中 99 此对路径线段的判断复杂度非常高。因此考虑到手机内存问 题后，我对算法进行了优化。我将优化的结果称为“交替算法” 。 若当前位置未偏离某路径点 M，则我们视为其在路径点 M 范围内。 若当前位置未偏离某路径线段 MN，则我们视为其在路径线段 MN 范围内。 无论如何，当前程序都会暂存一个状态：当前位置在某点或某线段范围内。 当导航开始时，视为处于起始点的范围内。我称这个状态为“范围状态”。 每接收到一次数据后， 根据下面的流程判断是否错路， 并更新 “范围状态” 。 范围状态有可能为：在某点范围内，在某线段范围内，错路。

42

复旦大学本科毕业设计

若当前范围状态为“在某点范围内”，且受到 GPS 定位信息，执行如下判断：
接收到GPS信息

N
仍在该点 范围内

Y

N

Y

在下一线段 范围内

N
Y
在上一线段 范围内

N
进入下一段路径 进入上一段路劲 错路提醒 在点范围内

图 4-15 某点范围内的判断树

其中的下一段路径指的是：包含该点的两段路径中按照路线方向应该后进入 的一段。而上一段路径指的是包含该点的两段路径中的另外一段。 如下图 4-16 所示：

图 4-16 某点相邻新线段示意图

43

复旦大学本科毕业设计

如果当前范围状态为：在某线段范围内，执行如下判断：
接收到GPS信息

仍在该线段 范围内

Y

N Y
在下一点 范围内

N
在上一点 范围内

Y

N Y
在下一线段 范围内

N
在上一线段 范围内

Y

N
进入下一点范围 进入下一线段范围 错路提醒 进入上一线段范围 进入上一点范围 仍在该线段范围

图 4-17 某线段范围内判断树

其中的下一点指的是：该线段包含的两端点中按照路线方向应该后经过的一 点。而上一点指的是：该线段包含的两端点中的另一点。 下一段路径指的是：与该线段有交点的两线段中，按照正确路线方向应该后 经过的一段。而上一段路径指的是：与改线段有交点的两段线段中的另一段。

图 4-18 某线段相邻点、线示意图
44

复旦大学本科毕业设计

4.4.4 “交替算法”小结
在使用这个错路判断“交替算法”时，假设了一个前提，那便是用户自觉地沿 着路线向前或向前走，并默认用户向前走的意愿比较强力。 如果用户有意识的“抄近路”，即不按照规定自定义路线进行行走，会出现位 置状态从某一个范围跳转到不相邻范围的情况。在这种情况下，算法会进行错路 提醒。这是活动组织者希望看到的，因此这样可以帮助位置活动秩序。 然而使用交替算法进行错路判断也有一定缺陷。当错路提醒被触发之后，用 户只能通过刚才的范围状态所在的路径点或者路径线段回到路径上， 错路提醒功 能才可以继续工作。 而用户如果从其他位置回到路径上则不能再启动错路提醒功 能了。

45

复旦大学本科毕业设计

5. 应用实例：“一个鸡蛋的暴走”活动
5.1 “一个鸡蛋的暴走”

在导师的推荐下，我选取了“一个鸡蛋的暴走”公益活动作为此次自定义路线 导航软件设计的一个实例。

5.1.1 “一个鸡蛋的暴走”活动简介

“一个鸡蛋的暴走”项目是由上海公益事业发展基金会主办的一个平台性的 公众筹款活动。该项目旨在为多个儿童领域的的民间公益组织筹款。 “暴走”活动的参与者，需要沿着指定路线步行 50 公里，称为“暴走”。参与者 在“暴走”前与亲朋好友打赌筹集善款：“如果我为孩子们暴走 50km，你是否愿意 为他们捐款？” 由下述原因可以看出，2014 年“一个鸡蛋的暴走项目”非常符合“自定义路线” 的特征。 我为这次 “暴走” 活动的参与者们设计的暴走软件“暴走小能手”是“自定 义路线导航软件”的一个恰当的具体实现。 在“一个鸡蛋的暴走”活动中，活动组织者首先确定长度为 50km 的路线，并 在路线上确定一些关键节点，例如“打卡点”、“补水点”等等。

46

复旦大学本科毕业设计

2014 年的暴走路线选在金山区。 活动组织者在官网上发布的路线图如下图 51 所示：

图 5-1 2014 一个鸡蛋的暴走路线

从路线图中我们可以看到： 1. 活动组织者所规划的路线由金山卫火车站出发， 在金山地区折返一圈后在 金山卫火车站结束，符合“自定义路线”的非最优性质。 2. 在金山卫火车站站附近，路线有少量重叠。 3. 在“金山小渔村”中的部分路线在地图数据库中不包含。从地图上很明显 的可以看出， 最右侧的路线并非画在地图上所标注的道路上，而是根据实 测绘制的路线形状。右上角的小地图即表示这一段路线。

47

复旦大学本科毕业设计

5.1.2 暴走活动参与情况
2014 年一个鸡蛋的暴走活动有约 2000 人参加， 在参与者自己的坚持与努力、 工作人员的帮助下，有一半左右的人成功走完了 50 公里全程，并为灾区孩子筹 得了善款。 为了能够更加顺利的拿到资料，同时也为需要帮助的孩子贡献一份力量，导 师任老师与我都主动报名参加了这次“暴走”活动的自行车义工。在活动当天，我 与其他自行车义工一起，在活动路线上巡航，以维持秩序；并携带急救包帮助暴 走过程中受伤的参与者。所有自行车义工全程陪伴参与者，从第一个出发的暴走 队员开始，直到最后一个参与者走到终点。 暴走活动的义工主要分为自行车义工、自驾车义工、摄影义工、指路义工等 等。摄影义工主要负责摄影，自行车义工、自驾车义工在路线上巡航，自行车义 工负责维持秩序，帮助受伤人员进行急救；自驾车义工帮助伤员、放弃继续行走 的参与者，将他们护送到终点。指路义工站在各个关键路口、打卡点、补水点， 帮助活动参与者走向正确路线、打卡、发放食物饮料。 当然，对本次项目帮助最大的并不是活动当天，而是之前进行的义工培训等 等活动。在义工培训的过程中，活动主办方对整体活动进行了介绍，并介绍了路 线。义工培训当天，我拿到了详细的路线地图资料（以及工作衫、工作证等等其 他资料） ，这份地图资料对我将路线转换为坐标数据提供了很大的帮助。我根据 地图资料以及百度地图坐标拾取工具，将大部分路线的百度经纬度坐标点转换、 记录下来。 路线中的一部分穿过了金山著名景点小渔村，而渔村中的路线在百度地图的 数据库中并没有记录。因此我之后又参加了自行车义工自己组织的“探路”活动。 探路活动旨在帮助义工熟悉路线，我在参与探路活动时，使用我测试用的 demo 软件，在路线上直接取得路口的百度经纬度坐标，之后加入程序中，最后形成了 完整的路线数据。

48

复旦大学本科毕业设计

5.2 针对“暴走”活动的优化

为了使暴走小能手更加人性化，获得更加良好的用户体验，软件应该具有一 些“非基本”的功能。 考虑到用户在参与 “一个鸡蛋的暴走”活动时， 需要在连续的 大约 10 小时时间内行走约 50 公里，对耐力、体力都是一种极大的考验，因此可 以考虑增加功能对用户进行一些激励。 例如，增加距离计算功能，告诉用户截止至当前位置，已经步行了多少公里 或者离终点还有多少公里；增加时间预测功能，根据之前的行走速度，告诉用户 距离走到下一个打卡点、补水点（可以休息的地方）还需多长时间、距离走到终 点还需多长时间。因此在对这次活动设计软件时，我们另外附加了两个功能：距 离计算与时间预测。

5.2.1 距离计算
距离计算的算法在很大程度上利用了错路算法。这样做的好处是可以在程序 中将这两种算法相同的部分合并，减少运算量，这样可以占用更少的内存。 设路径上的点的集合为

{������������ , ������������ , ������������ , …, ������������ }
（5-1）

由于可能在路径规划、将路径转换为坐标点的过程中产生误差有可能出现
������−������

∑ ������(������������ , ������������+������ ) ≠ ������������������������
������

（5-2）

的情况，因此我们在计算过程中要对路程进行归一化。以保证当用户最终走 到终点时，在软件上显示的都为总里程 50km。 具体的距离计算方法如下： 首先根据当前的范围状态进行判断。设当前位置为 P 点。

49

复旦大学本科毕业设计

(1)若当前在某一点������ 范围内，则当前所行走的真实距离为 ������
������−������

������(������������ , ������) + ∑ ������(������������ , ������������+������ )
������

（5-3）

而其归一化距离 S 应为

������(������������ , ������) + ∑������−������ ������(������������ , ������������+������ ) ������ ������ = × ������������������������ ������−������ ∑������ ������(������������ , ������������+������ )
（5-4）

其中公式中部分变量如下图所示

图 5-2 在点范围内图示

(2)若当前位置在某一路径线段������ ������������+1 范围内，则用户在此线段上走过的真 ������ 实距离为

������ = √������(������������ , ������)������ − ������(������������ ������������+������ , ������)������
（5-5）

此用户总共走过的真实距离为
������−������

√������(������������ , ������)������ − ������(������������ ������������+������ , ������)������ + ∑ ������(������������ , ������������+������ )
������

（5-6）

因此，该用户走过的归一化距离 S 为

√������(������������ , ������)������ − ������(������������ ������������+������ , ������)������ + ∑������−������ ������(������������ , ������������+������ ) ������ ������ = × ������������������������ ������−������ ∑������ ������(������������ , ������������+������ )
50

复旦大学本科毕业设计

（5-7）

公式中部分变量如下图 5-3 所示

图 5-3 在线段范围内图示

使用“交替算法”计算已经走过的距离在这次的暴走活动中有它的优势。因为 这次的路线带有部分重叠，而使用这样的算法并不会被重叠的路线所影响。 然而，由于距离计算使用了错路判断的交替算法，因此他依赖于错路判断功 能。因此当判断为错路时，即使用户继续行走，所得到的距离也不会再增加。

5.2.2 时间预测
根据 5.2.1 中结论，我们可以得到当前已行走距离与总距离的比值。设这个 比值为 k（k