Lane-Level Connection Relationship in High‑Precision Navigation Data Based on NDS

High‑precision navigation data replaces road‑level information with lane‑level data, where each lane becomes the smallest navigation unit. This granularity greatly improves navigation accuracy and is essential for autonomous driving.

The article focuses on how lane connection relationships are created within the Navigation Data Standard (NDS) framework.

Definition of Lane Connection Relationship

In high‑precision data, a lane is the minimal navigation element, analogous to a road in traditional data. The lane connection relationship expresses the connectivity between lanes, allowing navigation applications to determine predecessor and successor lanes for lane guidance and calculation.

NDS Representation

NDS defines a LANE BuildingBlock (Lane BB) to represent lane‑level data. A Lane Group groups parallel or attribute‑identical lanes and includes attributes such as lane count, type, edge line type, center line points, and lane connection relationships.

Lane connections are expressed using a connector ID . Each lane has an entrance and exit connector ID; two lanes are connected when their corresponding connector IDs match.

Connector ID Variants

Two NDS versions define connector IDs differently:

NDS 2.5.2: connector ID is a varuint16 ranging from 0 to 32 639. It must be unique within a tile and also unique across the surrounding 9‑tile neighborhood.

NDS 2.5.4: connector ID is a varuint32 ranging from 0 to 536 870 911, with uniqueness required within the 9‑tile neighborhood.

Production Scheme Based on NDS

The proposed workflow consists of three steps:

Read the original lane connection data.

Construct and update a lane‑group graph according to tiling results.

Traverse each node in the lane‑group graph to compute connector IDs.

To address two main challenges, the article suggests:

Using a graph (cross‑linked list) to quickly locate predecessor and successor lanes, facilitating connector ID calculation and topological updates after lane data changes.

Allocating connector IDs uniquely across tiles. For NDS 2.5.2, the ID space (0‑32 639) is split into two intervals: 0‑19 999 for intra‑tile IDs and 20 000‑32 639 for border IDs, with border IDs selected via a vertical comparison across the 9‑tile neighborhood.

For NDS 2.5.4, the larger ID space allows partitioning into nine intervals (one per position in a 3×3 tile grid). Tile IDs, derived from binary row/column bits, are used to compute a unique index (row % 3, column % 3) that selects the interval, ensuring uniqueness within any 9‑tile block. IDs within each interval are assigned incrementally.

The solution demonstrates how to generate lane connection relationships that satisfy both intra‑tile and inter‑tile uniqueness constraints, and it can be adapted to other navigation data specifications with appropriate adjustments.