Combine multiple encoded polylines into one encoded polyline

Question

I am trying to combine a new coded polyline with an existing polyline without decoding and transcoding the entire polyline. The new encoded polyline will be uploaded to the server (linux), where I would like to add it to the existing polyline.

The problem is that you cannot just crush them together. The following are some sample data. I hope to find / create a solution in either PHP or the shell script, but the problem is that I do not have 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 going to be more like 7,000 coordinate pairs) 

• The first 3 coordinated pairs are encoded: yir{Fnwm_MimFquRuTanK
• Last 3: s`z{Fbpb~L{qGg`FkrDkjK
• All 6: yir{Fnwm_MimFquRuTanKdLw`J{qGg`FkrDkjK

Interactive Polyline Encoder Utility
The format of the encoded polyline (you can get this through an interactive encoder)
Polyline encoder

Edit:

I also have source data that encoded polylines at both ends. Therefore, I can also save the first and last coordinate pair separately.

Useful readings:

In the end, I wrote a blog post that has a lot more information about how encoded polylines work. You can read it here: What is an encoded polyline?

Answer 1

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

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

Solution: save the last coordinate pair from the existing polyline, encode this pair and save it later, encode all new coordinates with the coordinate from the existing polyline at the beginning of this new encoding. find the line of the last coordinate pair and delete it from the new coded polyline and attach the new coded polyline to the back of the existing polyline

What you need to know: What the encoding does, calculates the offset (distance from x, y) and converts this value to ASCII. The problem is that the first coordinate is calculated from 0.0, so if you just have to put two coded polylines together, where you added a new one, it will not be offset from the existing one, but offset from 0.0, which will cause a big jump in the polyline . We need to find out which characters in the encoded polyline are offset from 0.0 and delete them. Then you can add a new line to the old line and it will be correctly offset.

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

PasteBin: PHP implementation for solution

Answer 2

The coding algorithm is shown here: http://code.google.com/apis/maps/documentation/utilities/polylinealgorithm.html

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

Coding uses offsets (delta) from point to point. The offset of the first point is calculated from (0,0), so it is equal to the coordinates of the first point. The second point is encoded as the offset of the point two of the first, etc.

To connect 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 line offset two from the last point of line 1 and replace 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 should be recoded to show what needs to be followed.

Since each encoded point in each line can consist of a variable number of characters, it is 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 transcoding. Probably the easiest way is to decode each line into an array of points, and then transcode it all. Encoding is fast and easy in PHP - visit the McClure website again.

This contradicts the answer I gave to the Google Maps Version 2 Group, where I mistakenly assumed that the length of each coded point should not exceed five characters.

Answer 3

Decoding is done by the browser. You can send separate line segments for the browser to decode and combine. Polyline take one property "path". Polygons accept several path properties in an array of paths. The only difference between a polyline and a polygon is the absence or presence of a color of "fill" and "fill" opacity. If you declare your polyline to be a polygon without the "fill" properties, you will create a multi-segment line from separate parts.

PS - the stackoverflow editor really sucks.

Answer 4

I suggest you do not have to concatenate on the server. Do it in a browser. All decoding takes place in the browser. It is very simple to combine decoded arrays with javascript. You can use the splicing method, or simply iterate over each of the composite arrays.