1. 导读

在高精度导航数据中，车道级数据，取代了原来标精数据中的道路级数据。从原来的道路A连接道路B，变为车道A连接车道B。高精数据，极大的提高了导航的精确度，是自动驾驶不可缺少的一个模块。

本文着重介绍基于NDS的高精导航数据中，车道连接关系是如何制作的。

2. 如何定义“车道连接关系”

2.1 定义

个人认为，在高精数据中，车道是导航数据中的最小单元。每一个车道等同于标精数据中的每一根道路。而车道连接关系表达了车道之间的连通性。导航应用通过数据中存储的车道连接关系，可以知道当前车道的前序和后继车道有哪些，从而利用这些信息完成车道引导、车道计算等功能。

2.2 NDS中表达方法

NDS规格中定义了LANE BuildingBlock（以下简称为Lane BB），是用于表达高精的车道级数据。Lane BB中Lane Group的定义是：一组位置平行或属性相同的车道组合。在Lane Group中，定义了很多的属性，比如：车道数、车道类型、车道边线类型、车道中心线形点、车道连接关系等等。

而NDS中是使用connector ID 来表达车道连接关系的。我们可以这样理解connector ID：一个车道在入口处和出口处各有一个ID，如果两个车道是相互连接的，那么它们连接处的connector ID必须要相同。

如下图LaneGroup 1的Lane1-1和LaneGroup 2的Lane2-1是连通的，所以Lane1-1出口的connector ID和Lane2-1的入口的connector ID 都等于4。这就表达了两个车道的相互连接关系。

connector ID的取值分为NDS 2.5.2和NDS2.5.4：

NDS 2.5.2：

定义：connector ID是一个varuint16类型的变量，范围是0~32639。Tile内唯一，但是Tile边界的connector ID必须在周围9 tile内唯一。如果不唯一会引发车道连接错误的bug。

缺点：可用范围小。
NDS 2.5.4：

定义：connector ID是一个varuint32类型的变量，范围是0~536870911。周围9 Tile内唯一。

3. 基于NDS的制作方案

3.1 基本思路

基于原有的代码逻辑，connector ID的制作思路分为三步：

读取原始数据的车道连接关系
构建Lane group graph，根据Tiling的结果，更新Lane group graph
遍历Lane group graph中每个节点，计算connector ID

3.2 两个难点及解决方案

3.2.1 如何快速找到Lane Group和Lane的连接关系？

采用图（十字链表）的方式解决
采用图的优点：

i.图可以快速的找出当前节点的前序和后继节点，便于后续的connector ID的计算。

ii.相比其他数据结构，图可以快速的更新图中的拓扑，适用于车道数据更新后连接关系的维护。

3.2.2 如何计算可用的connector ID？

在不同的NDS版本中，使用了不同的解决方案：

NDS 2.5.2：
问题：由于可用的ID区间（0~32639）有限，如何既保证Tile内ID唯一，又保证Tile边界处 9 Tile唯一？
思路：最简单的保证唯一值的方案就是获取最大值，但是可用的ID区间很小，如果单纯的获取最大值，很容易出现越界的情况，所以此方案不可行。对于NDS252来说，我认为规格设计是存在缺陷的。connector id的可用范围设计的太小了。日后该版本的NDS数据肯定会被淘汰，所以此处的解法仅供参考。
解法：将varuint16划分为2个区间

i.Tile内的ID区间（目前分配 0~19999）

ii.Tile边界处的ID区间（20000~32639）

Tile内ID采用自增的逻辑分配，Tile边界处采用9 Tile内垂直比较方法获取可分配的ID（如下图）。

NDS 2.5.4：
问题：ID可用空间扩充，如果还采用2.5.2的垂直比较方法，内存撑不住。
思路：到了NDS254，从规格上补足了252设计的缺陷，扩充了connector ID的可用范围。所以我们要寻求一种新的方案来分为9 Tile内唯一ID。如果我们能保证在任意位置，可以给以当前位置为中心的9宫格，分配1~9不同的索引号，这样就能保证任意位置的9宫格内都是唯一ID了（有点类似数独）。顺着这样的思路便有了下面的解法。
解法：根据Tile ID划分不同的connector ID可用区间。

i.NDS中Tile ID是一个int变量。虽然它只是一个数，但是是根据一定的规则计算出来的。

如下图，Tile 实际就是把地球按照2的n次方分割下去。如果把Tile ID转换为2进制，我们可以发现，其偶数位是所在的行号，奇数位是所在的列号。我们有了行列号，就可以把其转为9宫格内的唯一编号了（行列号余3）。

ii.将connector ID划分为9个区间，目前一个区间分配了100000个connector ID，如果后续不够可以修改区间范围。根据上面计算出的Tile的唯一编号，乘以对应的区间ID，即是当前Tile可用的connector ID区间。

iii.Connector ID在区间中采用自增的逻辑即可。

4. 小结

以上就是基于NDS的车道连接关系的制作方案。NDS外其他导航数据规格中表达车道连接关系的形式各不相同。但是本文中的思路同样适用，只需要根据不同规格要求进行适当调整即可。

创作场景

NDS 中车道连接关系的制作方法