本文从地图显示、地图定位、地图检索、地图导航、地图数据采集等几个方面介绍地图团队涉及到的技术细节。
地图显示
我们首先要把地图渲染出来，然后才能在其基础上做检索和导航。地图显示包括数据预处理和客户端地图引擎两部分。
地图渲染引擎
地图渲染引擎从上到下包括，Overlay渲染、手势动画、标注渲染、底图渲染、数据加载等模块。地图渲染引擎一般是C++写的，对外提供的地图SDK是Android和iOS/ObjC的简单接口封装。
渲染一般是用OpenGL ES，所以比较耗电。其中标注渲染是比较复杂的模块，需要在POI的上下左右四个位置中选择最优位置，还要相互避让。由于道路的位置选择比较耗时，一般放在服务端预处理。
地图数据只有一份，但对应多套样式，一般地图都支持样式切换。地图数据通过瓦片为单位进行下载和缓存。
数据编译
地图数据预处理称做数据编译。地图数据量比较大，我们一般是分层、分块的方式来处理。分层是指不同比例尺的地图综合，就是不同的层次细节。分块是每一层分成很多格子，称作瓦片。像下图这样：
地图自动综合也是业界难点:
1.点的分层，通过POI点击率等特征预测他们的重要程度，把重要的点提前显示。
2.道路分层比较复杂，主要是在link基础上合并，双线变单线、中心线提取、形状点抽稀等。
3.面的综合更难处理，想要效果好还得人工处理。
地图定位
定位分为GPS定位和网络定位两种。
GPS定位
GPS是通过天上24颗卫星来确定位置的。GPS卫星像电台一样会一直向往广播自己的位置信息。手机上的GPS接受模块收到4颗以上的卫星信息就能确定自己的位置。
大概原理是通过时间差估计和卫星的距离，通过距离交汇解算出坐标。手机本地时间不是很准，肯定和卫星时间有偏差。但是不要紧，我们假设这个时间差是△t，四个卫星就可以把这个未知数解出来。
GPS的缺点是冷启动慢，室内没信号，高楼或者水面会影响精度。这些问题需要配合网络定位来弥补。
网络定位
网络定位是指用wifi、基站、IP地址等方式确定用户位置。我们以wifi为例来说明。用户手机可以扫描到附近wifi的列表和信号强度，这些wifi列表是不需要连接就能扫到的。定位SDK会把这些扫描到的wifi列表发送给服务端，服务端根据已有的wifi数据库估算出用户的位置。
wifi数据库是怎么来的呢，有GPS的时候也跑网络定位，实际上是为了收集训练数据。
服务端根据wifi数据建立倒排索引，召回候选位置。再通过模型对候选位置打分，输出概率最大的位置。可以把wifi当成特征，位置当成类别，这实际上是一个分类问题。
wifi数据由于有wifi ID重复、搬家wifi、移动wifi、操作系统缓存的过期wifi等，会有很多这样的错误样本干扰。所以要花很多精力进行wifi数据的清理。
逆地理编码
一般定位SDK除了给出经纬度坐标外，还可选的给出地址描述和附近的POI，这是通过调用逆地理服务实现的。逆地理编码是通过坐标查询附近的地物。这个原理就是一个空间索引，空间索引可以使用网格索引、R-tree索引、四叉树索引等。
地图检索
地图检索主要指POI搜索。和一般搜索引擎不同的地方主要是，POI名称和query都是超短文本。query里面会有whereWhat和路径规划等模式。
搜索引擎
搜索中AS负责主要的搜索调度逻辑。QP负责实体识别、query纠错、丢词省略、模式识别等。引擎负责倒排文档索引和空间索引。
引擎对召回结果按照rank和文本相关性进行粗排序，在AS模块通过机器学习的方式进行精排序。排序的特征很多，包括文本相关性、POI rank、距离因素、类别因素等。
路径规划
如果query分析模块识别出是路径规划模式，则分别搜索起终点后转给路径规划服务。
WhereWhat
whereWhat指用户query是“天安门附近的酒店”这种，一般使用序列标注的方式识别那部分是where，那部分是what。然后先查询where部分，再通过空间索引查what部分。
泛查询识别
地图POI检索分为泛查询和实体查询两种。泛查询的排序策略也和实体查询不同，例如距离因素更强等。
Suggestion
检索用户输入的时候，要想输入法一样提示补全，这个功能叫做suggestion。这个一般是用一个巨大的Trie树来实现。
地图POI数据融合
一般会有多个数据源，两家数据的POI名称和坐标会有很多不一致。多家数据的融合是个难点，一般使用名相似度、距离、类别相似度等特征的模型来判断两个POI是否是同一个。但是不可避免会出现绑定错误和没有绑定导致数据重复两种情况。由于景区的面积比较大，两家的点位置差别比较大，所以经常会有badcase。
地图导航
路径规划
《数学之美》这本书说路径规划使用动态规划算法，事实上根本不是这样。动态规划的时间复杂度一般都不低，不能满足要求。我们应该在课堂上学过dijkstra最短路径算法，实际工业上使用的也是dijkstra算法的变体。
dijkstra算法可以采用双向搜索的方式优化，而A* 算法是通过估算指导搜索方向。但一般路网的边和结点都是千万级别的，用啥算法实时请求都得跪，关键是要预处理。
假设起终点相隔很远，人类的想法就是先找两个城市间的高速公路，通过小路连接到最近的高速入口。所以我们有两个想法：1.要是我们能对路网分层，在高层找就能节省很多时间。2.两两城市之间的路径预计算后存储起来。
路网分层，主要是删除结点和删除边：1.删点：删除点时为了拓扑不变性，我们给增加很多虚拟边。2.删边：当发现一条边的起终点有更短的路径时删除当前边。删点和删边交替进行很多轮，我们就能得到很多层的路网图。
高层的路网图与原图的结点有对应关系，我们可以把对应的结点连起来，这条边赋代价为0。最终这个多层图用于最短路径搜索，这时候就能用双向dijkstra或者A*算法了。
当然实际上使用的算法更加的复杂。常用的有：
CH：http://algo2.iti.kit.edu/schultes/hwy/contract.pdf HH：http://algo2.iti.kit.edu/documents/routeplanning/esa06HwyHierarchies.pdf CRP：http://research.microsoft.com/pubs/145688/crp-sea.pdf
客户端导航
路径规划一般是服务端进行，在客户端拿到路径规划的结果后进行要对用户进行驾驶引导。
导航模块根据当前GPS的位置，匹配到路径线上，这个过程叫做地图匹配。地图匹配一般要参考当前运动的方向和道路的一致性、与道路的距离、历史轨迹的连通性。有路径线的匹配其实比较简单，没路径线更加复杂。主辅路距离比较近，方向也差不多，经常匹配错。很多采用概率模型的方式判断从那条路到那条路转移的概率比较大。
当GPS位置匹配到路径规划线上以后，判断前方路线的形状是朝左还是朝右，一般是分成几个预定方向。将要提示的信息拼成文字，然后调用语音合成引擎来播放。
地图数据采集
地图数据一般从有测绘资质的公司购买，一般公司是没有测绘资质的。国界水系等基础数据一般来源于测绘部门。
道路数据采集
道路数据通过街景车在道路上采集GPS和视频图片信息。外业获取数据后，传回给内业人员制作地图。
内业人员结合GPS轨迹、视图图片、卫星影像等数据，用鼠标绘制道路。道路的数据除了形状外还有车道信息、限高、限时、禁止左转等交通规则。在复杂的路口视频图片看不清的情况下还需要使用语音描述路口状况给内业人员参考。
POI数据采集
部分POI数据可以从街景图片中采集到。但是那些不在沿路的POI，或者被树木遮挡的POI则要使用步采的方式，作业人员步行或者骑车采集街景。当然这么做成本比较高，现在可能会想办法抓取某外卖平台的数据。
当然现在有些公司会用图形识别的方法识别街景中的招牌名称，不用再人工制作POI数据。
路况数据采集
绿色表示畅通，红色表示拥堵。每个开车导航的用户会实时上报行驶位置和速度，服务的通过这些数据推断道路的拥挤程度。当然这中间可能要排除是在等红绿灯而不是真的拥堵了。
原创文章，禁止转载。
