Encoded polylines

An encoded polyline is a string of printable ASCII characters that encodes a list of integers. Transitland and Interline Routing Platform APIs use encoded polylines to reduce the size of responses sent to browsers and other clients. The format is the encoded polyline algorithm from Google Maps. The algorithm was designed for map geometries and applies to any list of integers.

The APIs use encoded polylines for two kinds of data:

• Geographic data: lists of coordinates, such as a journey geometry from a routing engine or the shape of a trip.
• Tabular data: rows of a grid, such as the timetable grids of the route patterns endpoint, in which some cells are null.

Valhalla's shape_format parameter does not change shapes in the default json response format. It applies in two cases:

• With format: osrm, it selects polyline6 (the default), polyline5, or geojson for each route's geometry.
• The matrix endpoint returns a shape for each pair only when the request sets shape_format, in the format it names.

The algorithm encodes each integer in a list as its difference from the previous integer. The first integer is encoded as its difference from 0. Small differences encode to fewer characters, so lists of gradually changing values, such as consecutive points on a line or consecutive times in a timetable row, encode compactly.

Each difference is encoded as follows:

1. Shift the value left by one bit. If the value is negative, invert all bits, so that the lowest bit records the sign.
2. Split the result into 5-bit chunks, starting with the lowest bits.
3. Set the 0x20 bit on every chunk except the last, to indicate that another chunk follows.
4. Add 63 to each chunk, to produce a printable character from ? to ~.

A line is encoded as each point's latitude and longitude, in that order. Each latitude is encoded as its difference from the previous point's latitude, and each longitude as its difference from the previous point's longitude. The order of latitude and longitude is the reverse of GeoJSON, which puts longitude first.

Precision

Before encoding, each coordinate is multiplied by 10 to the power of the precision and rounded to an integer. Five digits of precision, also called polyline5, is 1.1 meters of latitude. Six digits, also called polyline6, is 11 centimeters of latitude.

The string does not record its precision, so the decoder must be given the precision. Decoding at the wrong precision does not return an error. It returns incorrect coordinates:

• A polyline6 string decoded at five digits returns coordinates 10 times too large. A point in San Francisco is returned as 377.95, -1223.94.
• A polyline5 string decoded at six digits returns coordinates one tenth of their correct values. The same point is returned as 3.78, -12.24.

Decoding

Most languages have a polyline library that takes the precision as an argument. In JavaScript, @mapbox/polyline:

import polyline from '@mapbox/polyline'

// A Valhalla shape, at six digits: [[lat, lon], ...]
const points = polyline.decode(shape, 6)

// The same shape as a GeoJSON LineString, in [lon, lat] order
const line = polyline.toGeoJSON(shape, 6)

In Python, polyline:

import polyline

# A Valhalla shape, at six digits: [(lat, lon), ...]
points = polyline.decode(shape, 6)

# In GeoJSON (lon, lat) order
coordinates = polyline.decode(shape, 6, geojson=True)

Route patterns timetables are grids, with a row for each stop and a column for each trip. Some cells are null, such as the shape distances of a trip without a shape. With encoding=polyline, each row is a single string that encodes one integer per cell. The integers are not scaled, and a . marks a null cell.

Polyline libraries decode coordinate pairs and cannot decode these rows. The route patterns page describes the grid format and includes a worked example and a decoder.