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

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 外其他导航数据规格中表达车道连接关系的形式各不相同。但是本文中的思路同样适用，只需要根据不同规格要求进行适当调整即可。