Merging multiple encoded polylines into one encoded polyline

Question

I'm trying to merge a new encoded polyline with an existing polyline without decoding and reencoding the whole polyline. The new encoded polyline will be uploaded to a (linux) server where I would like to append it to the existing polyline.

The problem is, you can't just mash them together. Below is some sample data to play with. My hope is to find/create a solution in either PHP or a shell script but the problem is, I have no where near enough technical understanding to interpret the encoded polyline algorithm.

41.386692,-73.475912
41.424822,-73.375027
41.428292,-73.311173
41.426183,-73.254577
41.470168,-73.218532
41.498865,-73.155278
(Yes, 6 points are easy, but it's going to be more like 7,000 coordinate pairs)

• First 3 Coordinate Pairs Encoded: yir{Fnwm_MimFquRuTanK
• Last 3: s`z{Fbpb~L{qGg`FkrDkjK
• All 6: yir{Fnwm_MimFquRuTanKdLw`J{qGg`FkrDkjK

Interactive Polyline Encoder Utility
Encoded Polyline Algorithm Format (you can get to this via Interactive Encoder)
Polyline Encoder

Edit:

I also have the original data that encoded the polylines on both ends. So I can also save the first and last coordinate pair separately.

Helpful Reads:

I ended up writing a blog post that has a lot more detail about how encoded polylines work. You can read it here: What is an Encoded Polyline?

Answer 1

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.

Answer 2

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.

Answer 3

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