鲁达 编者按：目前LBS应用已在智能手机中占据了主导地位，但LBS技术覆盖范围太广，很少有能深入描述LBS技术的资料。所以作者在《程序员》杂志开辟专栏来描述LBS核心技术，本文为该专栏的第三篇。
我们知道，大部分的LBS应用的一个重要功能就是其能帮助客户实现路径引导功能，比如：在团购应用中团购某商铺的服务后，来实现从目前位置到此商铺的导航。所以，本文将以LBS应用的路径引导功能为例来讲述LBS的核心技术。
路径引导（Guidance）又被简称为导航，是指在路径导航的过程，实时跟踪当前车辆（或使用者）所在的路径和状态，计算出当前车辆（或使用者）到下一引导点的距离、方向、下一道路名和目的地信息，并向自驾者发起视频和语音指令，从而不断地引导用户方便、快速地到达（POI）目的地。
在装有导航系统的汽车或手机应用内，用户可以在导航兴趣点搜索功能画面中输入想要去的旅游路线POI目的地——景点，然后导航系统会自动计算出一条最佳的行车路线。在车辆行驶的过程中，系统会对前方道路上的情况加以提示。一个典型应用的导航的界面，通常如图1所示：
图1 典型应用的导航界面
图1中的“我的导航”，就是实现从A地（通常是使用者目前所处的位置）到B地的导航功能。
总的来说，一个完整导航的功能是确保用户的轨迹保持在正确的道路上，以及当用户到达分歧路口时，导航引擎能发出正确的提示音，这种提示音包含了“向左转”，或者“向右转”，或者“直行”等角度提示。相应的，导航过程中的技术难点可以分为：
定位，即：定位用户的轨迹；
道路匹配，即：匹配用户的轨迹到某条道路；
引导点模块的设计，即：设计导航需要发出发出声音的地点，以及相应的触发原则；
引导角度的设计，即：计算用户的“向左转”等语音提示。
下文将依次介绍上述四个模块。
定位模块
在导航的过程中，由于各种原因偶尔偏离规划的路径行驶，一旦系统识别车辆（或使用者）不再行驶在给定的路径上时，系统必须做出反应，应让车（或使用者）尽力回到正确的路径上，提醒自驾者的一个简单方法是在界面上显示一个方向箭头指向预定的目的地。只有车始终偏移路径行驶时，才考虑重新路径规划，让自驾者兴趣目的地导航服务跟随无时不在。
可见，导航功能与定位以及路径规划功能（可参见《程序员》电子刊11A《LBS应用的定位与算路方法》一文）是密不可分的。
道路匹配模块
所谓的道路匹配模块是定位功能在导航功能中的应用，是指将用户目前的位置和一条道路相匹配，从而得到用户的轨迹，从而使用户导航成为可能。用户目前的位置和道路匹配的过程就是道路匹配，也称为GPS绑定。
道路匹配方案在具体实施的过程中有很多，但其根源的方法可以分为以下两种：
利用当前的GPS信号点与道路间进行逐个匹配：这种方法在本质上是一个利用当前的GPS信号点寻找最近邻道路的问题。
在具体实施时，往往是将当前的GPS信号点与周围的道路进行距离计算。距离最近的道路认为是当前的匹配道路。
具体的过程就是，先寻找到最近道路，之后进行道路绑定，GPS信号在当前绑定的道路上行驶，当到达一个路口时，GPS信号将会重新开始绑定。
利用历史轨迹点与当前道路的角度/距离差别进行绑定判断：
图2 绑定判断过程
以图2为例，具体的做法是：在灰色点的地方，对地图绑定进行重新判断，由于灰色点轨迹的方向和当前路段行驶方向的角度/距离（或者其他相似度度量）比较小，所以是当前路段的可能性比较大。
第二种做法，在本质上是一种简单聚类的方法。这种做法与第一种做法的区别就在于引入了历史轨迹点，由于引入了历史轨迹点，从而可以抵消单个轨迹点的过大误差。当导航用户从主路转到辅路时，由于主辅路的差距非常小，所以用聚类方法有助于提高提示的精度，不至于出现用户已经到了辅路，但是导航位置却一直显示在主路的情况。
引导点模块
引导点是路径引导的关键，因为在引导的过程中，最重要的就是时刻提供用户所需的路径引导信息，从而使用户能一直保持在正确的路径上。比如：导航时，发出各种语音就是当用户到达“引导点位置”时发出的。
引导点制作是制作引导点以及相关引导信息的过程。根据实际需要，引导管理线程启动进行引导点（列表）信息制作线程执行制作任务。引导信息制作线程处理具体的引导点制作。引导信息制作的主要处理过程是在路径探索完成后进行的，通过对探索路径的遍历，产生一系列控制点或行为点（Guide Point），并准备制作具体相关的引导信息，用于显示和语音播报，从而以此为自驾者提供安全、准确的导航信息和语音指令服务。
制作过程中一个关键的概念是这些turn-by-turn中的“turn”控制点（或行为点），准确地说，是转弯的衍生，即引导点（Guide Point、maneuver）信息，它好比指路向导，可以产生具体的语音指令和信息。引导信息包括路口的转弯方向、下一道路名、到达距离，以及到达目的地时间和距离，当前车所在车道信息、周围的实景、路牌指示标志（signpost）等。
由于在离前方道路不同的位置、在不同等级的道路、不同类型的引导点，引导展现的内容和语音播报的方式都不同，这些信息主要来源于turn-by-turn 列表。
一个实用的引导点的道路拓扑模型如图3所示。
图3 引导点的内部构造模型
该引导点包括的对象如下。
引导点的类型（包括行为类型、方向）；
引导点的进、出道路线；
引导点的其他交叉道路（几何构成）；
引导阶段提示点（Phase Advice Point，简称PaP）；
引导点的位置；
引导点的前继（对复合引导点）。
需要注意的是，当导航路线较长时，计算全部的Maneuver（引导点对象）耗时多，并且全部的Maneuver占用内存数量较多，因此，在设计时使用分段计算Maneuver的方式。每次只生成一定距离内的Maneuver信息，随着车辆位置的变化，动态计算后续的Maneuver信息。
图4的程序中，首次计算4条Maneuver，当行驶过第1个Maneuver后，更新一条Maneuver，以此类推，直到结束。
图4 Maneuver的计算
一种简单实用的Maneuver数据结构如下：
Class Maneuver{ ArrayList* interList; // node序列 ArrayList* drPointList; //DRPoint 序列 int length; //Maneuver长度 std::string m_pstrSpeech; //routebook int icon; //icon id int m_nRouteId; // link index bool bThen; //是否有“然后”提示 }这种Maneuver数据结构设计能计算用户的位置到引导点的距离，以及当用户到达引导点的时候，确保导航能显示正确的图标（icon），并发出提示音。
引导角度
在导航的过程中，语音提示是非常重要的，比如：左拐或者直行等语音提示。要想实现这种精确的语音提示，必须依赖使用者当前的道路定位以及当前道路与目标道路间的角度。比如：如果计算的目标道路与当前道路的角度是左侧90度，那么，导航需要发出的语音是：左拐进入某某路。由于语音转换可以由开源的文本到语音的生成器（TTS）来实现，所以实现导航精度的关键就是计算精确的引导角度。
对拓扑关系较简单的一般道路而言，只需要简单的角度计算就能算出司机的行进方向。如果是环岛、广场等复杂路口，计算方法会复杂一些，这时需要考虑的角度比较多，如图5所示。
由
图5 导航的角度计算方法
于在地图数据中一般存储了道路（Link）的进入、退出角度，所以在Maneuver计算时不但要使用数据提供的角度计算转向角，还需要结合路口的拓扑关系进行全面计算，才能让路口的提示更准确。比如图6所示的路口情况中，带箭头的粗线是导航路线，无箭头的线是路口的拓扑路线，为了使导航提示音更准确，计算转向提示需要综合考虑α、β、γ三个角度。
图6 路口角度
如上所述，一个完整的导航引擎在实现导航时，利用了定位功能来实现定位用户的位置，利用了道路匹配模块来实现用户位置和当前道路的绑定，利用了引导点模块来实现导航信息的提示功能，利用了引导角度的设计模块来实现精确提示音的自动生成。
作者简介
贾双成,阿里巴巴资深工程师，擅长于数据编译、数据挖掘的系统分析和架构设计，主持研发过多个高端车载导航及adas数据编译器。曾发表发明专利、论文四十余篇，著有《LBS核心技术揭秘》、《数据挖掘核心技术揭秘》。
本文选自程序员电子版2015年11月B刊，该期更多文章请查看这里。2000年创刊至今所有文章目录请查看程序员封面秀。欢迎订阅程序员电子版（含iPad版、Android版、PDF版）。