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

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.