A description of Google's encoded polylines

Our objective is to read a sequence of latitude/longitude pairs and translate this to an encoded polyline. To do so we need to understand Google's basic representation of an encoded polyline. The API documentation describes polylines here. Google has also set up a polyline encoding utility, which you can use to encode short polylines. Unfortunately, the documentation is, at best, incomplete and the encoding utility is very clumsy. The following description of polylines has been gleaned from these references and experimentation.

First, let's look at the basic structure of an encoded polyline. The following simple polyline was generated by the form.

new GPolyline.fromEncoded({
  color: "#0000ff",
  weight: 4,
  opacity: 0.8,
  points: "_gkxEr}|vNcBwBoAoA",
  levels: "P?P",
  zoomFactor: 2,
  numLevels: 18
});

The polyline is described by 7 properties. Of these, color, weight, and opacity are simple style directives. The actual points in the polyline are represented by a string called points. This string is essentially a concatenation of the base 64 representation of the latitude and longitudes, truncated to five digits of accuracy. There's a bit more to it that this, but this part of the algorithm is explained fairly well in the documentation and the javascript for Google's encoding utilities contains code for this purpose. I will focus on the zoomFactor, numLevels, and (most importantly) the levels properties.

The idea behind an encoded polyline is that not all points need to be displayed when the zoom factor is very small, i.e. the zoom is set far out from the path. According to the API documentation, "an encoded polyline representing a drive from New York City to Chicago should not care about the line segments representing particular streets in Manhattan when the map is zoomed out to the state level". Thus, the levels string gives us control over when (i.e. at what zoom level) a vertex should be plotted. More precisely, the length of the levels string equals the number of points determining the path and the character in a particular position of the levels string tells us when the corresponding point from the points list should be plotted.

The numLevels property indicates how many different zoom levels are associated with the polyline. Note that this is related to the number of levels for the map itself, but need not be the same. For example, if your map has 18 zoom levels (like a G_NORMAL_MAP) and your encoded polyline has 9, then the level of detail in the line should change at about every other zoom step for the map. The zoomFactor property indicates the difference in magnification between zoom levels for the polyline. If our encoded polyline has 9 zoom levels and our map has 18 zoom levels with a magnification factor of 2 between levels (again, like a G_NORMAL_MAP), then it would make sense to set the zoom level of the polyline to 4.

We now assume that numLevels is 18 and we are working with a G_NORMAL_MAP, which also has 18 levels. In this case, we clearly have 18 possible choices for characters in levels string. Those characters, together with their interpretations, are (approximately) as follows:

This says, for example, that a point encoded with an "L" will appear on map level 4, while a point encoded "B" will not occur until you zoom in to map level 14. A point encoded with a "P" appears at all zoom levels.

More generally, numLevels specifies a total possible number of encoding parameters and each zoom level for the line corresponds to a group of zoom levels in the map. This is the last row in the table and, yes, they are numbered in reverse order - 0 is close and numLevels is far away. When numLevels equals the number of levels in the map, we might expect the sets to be in one to one correspondence, as in the above example. On the other hand, if we have 9 zoom levels and 18 map levels, we might expect an arrangement more like so:

When the relationship between numLevels and the number of map levels is not so simple, it can be hard to predict exactly how this grouping will be done. Even using numLevels=18, other groupings are possible and grouping seems to be browser dependent, since some browsers are better at drawing polylines than others.