Merging multiple encoded polylines into one encoded polyline

Decoding is performed by the browser. You can send individual line segments for the browser to decode & concatenate. Polylines accept a single "path" property. Polygons accept multiple "path" properties in an array of paths. The only difference between a polyline & a polygon is the absence or presence of a "fill" color & "fill" opacity. If you declare your polyline to be a polygon without "fill" properties, you will have built a multi-segment line from individual pieces.

P.S. - the "stackoverflow" editor really sucks.


Ok, so I think I figured it out. Many thanks to Andrew Leach for explaining how the algorithm actually works in plain english.

Problem: Merging a new encoded polyline with an existing encoded polyline

Solution: keep last coord pair from existing polyline, encode just that pair and save it for later, encode all new coords with coord from existing polyline at the beginning of this new encoding. find the string of the last coordinate pair, and remove it from the new encoded polyline and stick the new encoded polyline onto the back of the existing polyline

Things to know: What the encoding does is calculate the offset (distance from x,y) and converts that value to ASCII. The problem is the first coordinate is calculated from 0,0 so if you were just to put two encoded polylines together, where you added the new one wouldn't be offset from the existing, but offset from 0,0 causing a large jump in the polyline. What we need to do is find out which characters in the encoded polyline are the offset from 0,0 and remove them. Then you can append the new line to the old line, and it will be offset properly.

Click the link below to see it all written up and with good comments. Also, please let me know if you see anywhere the efficiency can be improved!

PasteBin: PHP implementation of solution


This shows the algorithm for encoding: http://code.google.com/apis/maps/documentation/utilities/polylinealgorithm.html

A decoder is available from Prof Mark McClure at http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/decode.html

Encoding uses offsets (deltas) from point to point. The offset of the first point is calculated from (0,0) so it equals the coordinates of the first point. The second point is encoded as the offset of point two from point one, and so on.

To join two lines, you first need to find the last point of the first line, and the first point of the second line.

Then, you calculate the offset of line two from the last point of line one, and substitute that offset for the first coordinate in the second line. Thus the second line does not start with an offset from (0,0), but an offset from the end of the first line.

Now, the last point of the first line will need to be re-encoded to show that there is more to follow.

Because each encoded point in each line can consist of a variable number of characters, it's not easy to find any point (even the first) without decoding the entire line.

So: to do the work you will need to do some decoding and recoding. It's probably easiest to decode each line into an array of points and then re-encode the whole thing. Encoding is quick and easy in PHP -- see McClure's site again.

This contradicts an answer given by me in the Google Maps Version 2 Group where I wrongly assumed the length of each encoded point to be strictly five characters.


UNCA reorganised their staff web presence in 2013/14 and access to Prof McClure's work is now only available via archive.org. While the description of encoded polylines is still available and relevant, examples which rely on Javascript may no longer work.