导航的基本操作是用户设定一个起点和一个终点，系统自动的规划出来一条路线。为了规划出来起点到终点的路线，我们将世界虚拟成一张图，图中的每条边对应真实世界中的道路，图中的每个节点对应真实世界中的道路路口，然后设定起点和终点后可以使用dijkstra算法去寻找起点到终点的最短路径。
但是往往我们在发起导航的时候，起点可能并不在道路上，这时候就需要将用户设置的起点映射到图中的道路上，才可以继续使用dijkstra算法进行路径规划。一种最朴素的想法是将起点绑定到距离图中最近的道路上，那么需要解决的第一个问题就是如何找到起点附近的道路？显而易见，空间索引可以解决这个问题。常用的空间索引有：
- GeoHash：将每个方格划分为四个小方格(00,01,10,11)，迭代一直到真正的位置。然后将连起来的二进制转成每5位以字母和数字表示的字符串格式，最长可以有12个字符。但是GeoHash有个问题，它是Z字形的，虽然有局部保序性，但是它也有突变性。在每个Z字母的拐角，都有可能出现顺序的突变。
- Google S2：Geohash使用Z字形来将二维变为一维，S2使用希尔伯特曲线将二维变为一维。它首先使用一个正方体包含地球，使用映射的方法将经纬度投影到正方体的某个面，然后再在这个面上使用希尔伯特曲线转换成一维的二进制，精度最多为30阶，所以使用64位整型就可以表示S2最后生成的cellid（前3位表示哪个面，后面60位表示希尔伯特曲线的一维表示，cell表示一个小方格）。S2和GeoHash的本质不同就是希尔伯特和Z字形的顺序不同。cellid数值离的越近说明它们实际距离越近。
- Uber H3：考虑到Geohash和S2的方法使得周围矩形到中心矩形的距离不一致，并且由于投射的方式使得Geohash和S2中的不同矩形代表的实际面积不一致。Uber提出了H3空间索引。它将地球看做一个20面体，每一个面都是球面三角形，在球面上分成110个6个六边形（使用7bit编码），然后在每个六边形内又可以迭代的每次划分成7个六边形（使用3bit编码），H3最多支持15层迭代。
有了空间索引，我们就可以找到起点的周围道路。那么如何从这些道路中选择哪条道路呢？距离最近是最一般的策略，但是由于定位有误差，有时候距离最近的道路并不准确。一些常用的绑路策略：
- 人工规则。一般使用最近距离法，结合角度、速度等特征，寻找最佳道路。
- 隐马尔科夫算法。如果有用户的之前轨迹，可使用隐马尔科夫算法来寻找用户的最佳道路。
- 机器学习算法。一些通用特征为道路特征（方向角、道路级别、道路类型、起始点等）+ 定位特征（精度、速度等），正样本为根据用户轨迹得到的用户导航时候的真实道路，负样本为其他道路。更进一步，可以使用pairwise或者listwise等模型来预测，高德使用的是ListWise的模型。
至此，我们将起点映射到了图的道路上。但是有时候会遇见封路的情况，比如一个小区封了门，那么如果将用户起点绑定到小区里面的道路上，则路径规划肯定会失败。所以就需要一些检测机制能将这些被封道路检测出来，图算法中的强连通向量可以解决这个问题，如果能找到图的所有强连通向量，一旦某条割边被封，则该连通向量中的所有道路都需要设置为被封标志，可以使用Tarjan算法。
另外绑路时候也可以试着将起点映射到多条道路上，防止单条道路被封无法进行路径规划。