HERE Lanes Data Specification

HEREtile Tiling Scheme

As discussed in Geographic Partitioning, the HERE HERE Lanes Protocol Buffer format includes a tile identifier encoding scheme to optimize storage size whilst balancing computational efficiency. HEREtile tile identifiers are represented as 32-bit unsigned integer values, computed from their logical tile quad-key values.

Map Tiling

The HEREtile map tiling scheme is based on quad trees, where each higher level of detail splits parent tiles into 4 equal child tiles. The child tiles are numbered 0-3 in a fixed reverse "Z" pattern:

Figure 1. Illustration of HEREtile numbering sequence
  • Tile 0 is the south-west sub-tile
  • Tile 1 is the south-east sub-tile
  • Tile 2 is the north-west sub-tile
  • Tile 3 is the north-eastern sub-tile

The tiling is based on raw, non-projected WGS84 latitude/longitude coordinate values, so each child tile covers exactly half its parent's lat/lon range per side.

Note: Note, this scheme results in non-square tiles when viewed on a common Mercator projected 2D map, with the effect more pronounced further from the equator.

Special Root Tile

To avoid special handling of level 1 tiles, the level 0 root tile representing the entire world is a little odd.

The familiar -180° to +180° longitude and -90° to +90° latitude range of the world is augmented with a virtual counterpart north of the North Pole. This results in a base coordinate range of -180° to +180° longitude and -90° to +270° latitude, making the level 0 world tile a square with sides of 360°.

From here the root world tile is split in the standard way into four tiles at level 1, resulting in tiles 0 and 1 covering the known world and tiles 2 and 3 generally unused.

Figure 2. Level 1 tiles and the world map.

This scheme leads to the simple formula that at a given tile level, the latitude and longitude range for a tile can be calculated as:

360° / 2tile level = degrees of latitude and longitude per tile

So for level 14 HERE Lanes tiles that would be:

360° / 214 = 360° / 16384 = 0.02197265625° per tile

Tiling schemes always result in a question of which tile "own" a lat/lon location that lies on a tile boarder. For the HEREtile scheme, locations lying on the south-west border of a tile belong to that tile.

Convenience corner cases:
  • Longitude values of +180° are converted to -180°, so tile references "wrap" over the anti-meridian.
  • Latitude values of +90° are owned by their southern tiles.

HEREtile Identifiers

HEREtile tile identifiers are a packed binary representation, generally stored as 32-bit unsigned integer values. They are computed from their logical tile quad-key strings.

Tile Quad-keys

Tile quad-keys are strings of tile numbers (0-3) which capture the hierarchy of parent-child tiles from level 1 to the target tile level.

So for the level 5 tile containing San Francisco below, the logical quad-key would be "02123":

Figure 3. Sample Quadkey

It follows that the "level" of a tile quad-key can be directly inferred from the number of digits in the value. So a level 14 HERE Lanes tile quad-key will have 14 digits, using only 0, 1, 2 and 3.

Calculating Quad-keys

The tile quad-key for any lat/lon position at a given tile level can be calculated algorithmically using a version of Morton coding. Take this example for the Berlin Hauptbahnhof (central train station) at lat/lon 52.52507/13.36937.

Figure 4. Sample location for encoding

Let's calculate the level 14 HERE Lanes HEREtile id. First, we need to calculate the desired tile's X,Y coordinates in on the world map. Tile X,Y coordinates are not lat/lon values, they are the tile's integral positional coordinates, indexed from (0,0) in the southwest corner of the world map.

  1. Find the horizontal (X) tile index from the longitude value, by dividing the world map longitude range (-180° to +180°) into tile-sized ranges based on the desired zoom level. Per the Special Root Tile above, each level 14 HERE Lanes tiles cover 0.02197265625 degrees per tile:

    180° + 13.36937° = 193.36937° absolute longitude offset from south-west corner 193.36937° / 0.02197265625° = 8,800.45 = tile X: 8,800 (round down for 0-based indexing)

  2. Similarly, find the vertical (Y) tile index, making sure to use the special -90° to +270° latitude range:

    90° + 52.52507° = 142.52507° absolute latitude from the south-west corner 142.52507° / 0.02197265625° = 6,486.47 = tile Y: 6,486 (round down for 0-based indexing)

    Next, we need to convert the tile X, Y indexes (8800, 6486) and tile level (14) into a Morton code quad-key:

  3. Take the simple binary representation of the tile coordinate indexes, zero-padded to the "tile level" number of bits:

    tile X coordinate: 8800 = 100010011000002 - already 14 bits

    tile Y coordinate: 6486 = 011001010101102 - zero-padded to 14 bits

  4. Interleave the bits of the binary values, starting with the first bit of the Y-coordinate:

    interleaved Y/X = 01101000011000110110001010002

  5. Interpret the resulting binary value as a base 4 radix integer to get the quadkey string:

    01101000011000110110001010002= 122012031202204= quad-key string "12201203120220"

You should end up with a quad-key with the same number of digits as the desired tile level, containing only the digits 0-3. Here is the quad-key on the map:

Figure 5. Quad-key of tile for sample location

Now, the final step is to encode the tile's logical quad-key as a HEREtile id, for use in the HERE Native (Protobuf) payload.

HEREtile ID Binary Encoding

To encode a tile logical quadkey string into a packed HEREtile id use the following simple algorithm:

  1. Preface the quad-key with a '1':

    '1' followed by quad-key "12201203120220" = "112201203120220"

  2. Parse an integer value from the resulting string using base 4 radix and convert to base 10 radix:

    1122012031202204 = 37789444010 = HEREtile encoded Tile ID: 377894440

This results in a compact binary encoding, when tile IDs up to level 15 can be stored in a 32-bit unsigned integer, and up to level 30 in 64-bit unsigned integer value. HD Live Map tiles are published at level 14, so tile IDs are all published as 32-bit unsigned integer values. Here is the HERE Lanes content for that tile:

Figure 6. Map tile for sample location

For further insight, the above encoding results in the following 32-bit binary format at each tile level 1-15, where "1" represents the position of tile level indicator and "0/1" the binary encoded tile coordinates:

 

32

31

30

29

28

27

26

25

24

23

22

21

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

15

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

14

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

13

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

12

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

11

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

10

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

9

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

8

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

7

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

6

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

4

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

0/1

3

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

0/1

0/1

2

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

0/1

0/1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0/1

0/1

You can see that each subsequent higher-detail zoom level uses additional 2 bits for coordinates. Also, reading from the leftmost bits, the tile zoom level can be determined by the position of the first "1" with the following algorithm:


          (Total bit-length - position from left of first "1") / 2 = Tile Level
        

For example:


          (32b - p4) = 28 / 2 = level 14 tile
        

Given these rules, it should be fairly trivial to create encoding/decoding algorithms to convert from lat/lon coordinates to a target level HERE Lanes HEREtile id, similarly from a bounding box and level to a set of HEREtile ids.