# 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:

- 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.

## 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.

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° / 2^{tile level} = degrees of latitude and longitude per tile

So for level 14 HERE Lanes tiles that would be:

360° / 2^{14} = 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.

- 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":

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.

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.

- 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) - 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:

- Take the simple binary representation of the tile coordinate indexes, zero-padded to the "tile level" number of bits:
tile X coordinate: 8800 = 10001001100000

_{2}- already 14 bitstile Y coordinate: 6486 = 01100101010110

_{2}- zero-padded to 14 bits - Interleave the bits of the binary values, starting with the first bit of the Y-coordinate:
interleaved Y/X = 0110100001100011011000101000

_{2} - Interpret the resulting binary value as a base 4 radix integer to get the quadkey string:
0110100001100011011000101000

_{2}= 12201203120220_{4}= 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:

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:

- Preface the quad-key with a '1':
'1' followed by quad-key "12201203120220" = "112201203120220"

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

_{4}= 377894440_{10}= 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:

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.