English | Site Directory

Google Maps API

Google Maps API Premier

Same great maps plus a SLA, support, and control over ads

Encoded Polyline Algorithm Format

Encoded polylines store two types of encoded information for any given set of points: the latitude and longitudes of those points, and the maximum zoom levels to display these points. Levels are encoded using unsigned values, while point coordinates need to use signed values, so the encoding process is slightly different for each case. This process is noted below. If you only have a few static points, you may also wish to use the interactive polyline encoding utility.

Encoding Latitudes and Longitudes

The encoding process converts a binary value into a series of character codes for ASCII characters using the familiar base64 encoding scheme: to ensure proper display of these characters, encoded values are summed with 63 (the ASCII character '?') before converting them into ASCII. The algorithm also checks for additional character codes for a given point by checking the least significant bit of each byte group; if this bit is set to 1, the point is not yet fully formed and additional data must follow.

Additionally, to conserve space, points only include the offset from the previous point (except of course for the first point). All points are encoded in Base64 as signed integers, as latitudes and longitudes are signed values. The encoding format within a polyline needs to represent two coordinates representing latitude and longitude to a reasonable precision. Given a maximum longitude of +/- 180 degrees to a precision of 5 decimal places (180.00000 to -180.00000), this results in the need for a 32 bit signed binary integer value.

Note that the backslash is interpreted as an escape character within string literals. Any output of this utility should convert backslash characters to double-backslashes within string literals.

The steps for encoding such a signed value are specified below.

  1. Take the initial signed value:
    -179.9832104
  2. Take the decimal value and multiply it by 1e5, flooring the result:
    -17998321
  3. Convert the decimal value to binary. Note that a negative value must be inverted and provide padded values toward the byte boundary:
    00000001 00010010 10100001 11110001
    11111110 11101101 10100001 00001110
    11111110 11101101 01011110 00001111
  4. Shift the binary value:
    11111110 11101101 01011110 00001111 0
  5. If the original decimal value is negative, invert this encoding:
    00000001 00010010 10100001 11110000 1
  6. Break the binary value out into 5-bit chunks (starting from the right hand side):
    00001 00010 01010 10000 11111 00001
  7. Place the 5-bit chunks into reverse order:
    00001 11111 10000 01010 00010 00001
  8. OR each value with 0x20 if another bit chunk follows:
    100001 111111 110000 101010 100010 000001
  9. Convert each value to decimal:
    33 63 48 42 34 1
  10. Add 63 to each value:
    96 126 111 105 97 64
  11. Convert each value to its ASCII equivalent:
    `~oia@

The table below shows some examples of encoded points, showing the encodings as a series of offsets from previous points.

Example

Points: (38.5, -120.2), (40.7, -120.95), (43.252, -126.453)



Latitude Longitude Latitude in E5 Longitude in E5 Change In Latitude Change In Longitude Encoded Latitude Encoded Longitude Encoded Point
38.5 -120.2 3850000 -12020000 +3850000 -12020000 _p~iF ~ps|U _p~iF~ps|U
40.7 -120.95 4070000 -12095000 +220000 -75000 _ulL nnqC _ulLnnqC
43.252 -126.453 4325200 -12645300 +255200 -550300 _mqN vxq`@ _mqNvxq`@

Encoded polyline: _p~iF~ps|U_ulLnnqC_mqNvxq`@

Encoding Levels

An encoded polyline also stores information specifying the precision when drawing the polyline. This information allows the map to ignore drawing segments at zoom levels where that precision is not necessary. Each point in an encoded polyline stores this information in a levels string which is also encoded alongside the encoded points.

Note: this encoded "level" does not correspond directly to a zoom level, though they are related. More accurately, the numLevels parameter divides up the existing zoom levels (currently 18) into groups of zoom levels. For example, given a numLevels value of 4, the zoom levels are grouped together into the following levels:

Encoded Polyline Level Zoom Levels
Level 0 Zoom levels 0-5
Level 1 Zoom levels 6-10
Level 2 Zoom levels 11-14
Level 3 Zoom levels 15-18

An encoded level value of 3 in this case would ensure that a point appears in all zoom level, while a level of 0 will ignore points specified beyond zoom level 5. The endpoints of a polyline should often be set to the largest encoded level, to ensure that the endpoints will appear in all zoom levels and the line is drawn correctly.

For optimization, the zoomFactor parameter should reflect the approximate magnification between the different zoom level groups specified in numLevels. For example, given a doubling for each zoom level and about 4 zoom levels in each group, this value should be set to 16.

These level values are encoded in base64 as unsigned integers. Note that because level values are generally small, they shouldn't cross a 5-bit boundary; this results in level encodings being very simple: the value is simply added to 63. However, the encoding process below assumes you convert to a binary value and back again, and your code should perform this conversion in case the value of levels changes in an API revision.

The steps for encoding an unsigned value are specified below:

  1. Take the initial unsigned value:
    174
  2. Convert the decimal value to a binary value:
    10101110
  3. Break the binary value out into 5-bit chunks (starting from the right hand side):
    101 01110
  4. Place the 5-bit chunks into reverse order:
    01110 101
  5. OR each value with 0x20 if another bit chunk follows:
    101110 00101
  6. Convert each value to decimal:
    46 5
  7. Add 63 to each value:
    109 68
  8. Convert each value to its ASCII equivalent:
    mD