HERE Lanes Coordinate Encoding

Coordinate values for HERE HERE Lanes are relative to the WGS84 (G1674) GCS, and expressed as decimal degrees with 7 digits of precision after the decimal point. In the Protocol Buffer representation, we apply a couple of techniques to minimize their storage requirements.

Rather than using floating point values, we represent latitude and longitudes as 31 and 32-bit signed integers, respectively. We apportion the -180º to 180º degree longitude span over the available 2³² range of discrete values. For latitudes in the -90º to 90º range, we use a reduced 2³¹ integer value, as the range is half.

This results in an each sequential integer value being

360° / 2³² = 180° / 2³¹ = 0.00000008381903171539306640625 degrees apart

This corresponds to a resolution of around 1 cm at the meridian/equator. The resulting lat/lon integer values are then encoded as Morton Codes, interleaving their bits into a single 64-bit signed integer:

1. First bit is always 0, so all values are positive
2. 2^nd bit is leftmost bit of longitude (bit 32)
3. 3^rd bit is leftmost bit of latitude (bit 31)
4. Remaining 61 bits alternate between longitude and latitude, ending with bit 1 from longitude as it was one bit longer.

Here is a walk though for a sample location in Sydney, lat/lon -33.86663, 151.20578:

1. Convert the lat and lon values to their integer segment units. (Note: You should always "floor" the resulting number.)

   Lat: -33.86663 / (180°/2³¹) = -404044634.09925688888888888888889 = -404044635

   Lon: 151.20578 / (360°/2³²) = 1803955222.4060302222222222222222 = 1803955222

2. Convert the integer lat/long values to their 31 and 32-bit two-complement binary representations:

   Lat: -404044635 = 11100111 11101010 11000100 10100101 -> (strip high-bit)

   = 1100111111010101100010010100101

   Lon: 1803955222 = 01101011 10000110 00101100 00010110 -> (keep high bit)

   = 01101011100001100010110000010110

3. Interleave the lon and lat with a leading "0" to produce a 64-bit integer:

   0 (leading)

   0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 (lon)

   1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 (lat)

   => 0011110001101111111010001001110010100100011100001000100100110110

4. Convert value back to 64-bit signed integer:

   0011110001101111111010001001110010100100011100001000100100110110

   = 0x3C6FE89CA4708936= 4354955124161939766