10

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?

Christian
  • 27,509
  • 17
  • 111
  • 155
Dan Mandle
  • 5,608
  • 3
  • 23
  • 26

4 Answers4

9

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.

Andrew Leach
  • 12,945
  • 1
  • 40
  • 47
  • Andrew, Thanks for the info! That definitely helps me understand how it all works. Due to the amount of coordinate pairs that we're going to be working with, reencoding the whole polyline would take too long and too many resources. Since I'm also producing the appending polyline, I have the coordinate pairs. What if I were to encode just the first pair coords from 0,0 and from the last point on the existing polyline and subbed them out? Would something like that work? – Dan Mandle Feb 11 '12 at 21:52
  • In order to re-encode the last point in the line you will also need to know the previous point to work out the offset. What is "taking too long"? I have to process around 7500 points for a map of [Lundy Island](http://www.achurchnearyou.com/parishfinder.php?lundy) which takes six seconds using MySQL and PHP: but that also includes finding that polygon in the first place (point-in-polygon analysis) together with a bit of other data too. Less complex shapes are a **lot** quicker! [That's a V2 map, but we're talking about server-side processing] – Andrew Leach Feb 12 '12 at 11:40
  • Great answer, Andrew. Dan, for 7K points, I'd just decode, append and re-encode. As you said, it only takes a few seconds. If you were talking about millions of points or doing this on-the-fly, I'd go with Andrew's approach, OR just send down two separate encoded polylines to the client. It will only be a few bytes more. – Chris Broadfoot Feb 12 '12 at 13:30
  • It's also occurred to me that finding the encoded form of the last character in the first string (so you replace just the right characters) won't be particularly easy either as the number of characters representing that point is not fixed. To do that reliably you will need to encode the ante-penultimate point as well so you can match the _penultimate_ point; the characters after that must be the last point which you need to replace. The process is getting more complicated and therefore slower; and less generic -- just have a single routine that encodes a collection of line points. – Andrew Leach Feb 12 '12 at 13:54
  • Thanks Guys. I managed to get a couple computer engineers with my in front of a while board last night and worked out basically Andrew's last comment was. I'm trying to code up a prototype right now and I'll post it when it's done. Here's basically what I'm trying to do: keep last coord pair from existing polyline, $last_coord, encode just that pair (save it for later $junk), encode all new coords with coord from existing polyline at the beginning of this new encoding $newEPL. find the string, $junk, and remove it from $newEPL and stick $newEPL onto the back of the existing polyline – Dan Mandle Feb 12 '12 at 14:57
  • I'm submitted my answer. Please take a look and let me know what you think. – Dan Mandle Feb 12 '12 at 18:00
  • I think line 72 in your Pastebin won't give the desired result because you are encoding a single point, so its offset is from (0,0) and won't match anything in your original line. You need to encode the penultimate point _and_ the point before that so that the penultimate point's offset is correct. And don't forget that the last point of the first line will no longer be the end of the line, so that will also need to be re-encoded to indicate that more follows. – Andrew Leach Feb 12 '12 at 18:08
  • Please put that comment on my answer instead of continuing on this answer. – Dan Mandle Feb 12 '12 at 18:15
  • Well that's bizarre. Anyway, I see what you're saying in theory, however, in practice it doesn't seem to make a difference. – Dan Mandle Feb 12 '12 at 19:14
  • Please see my follow-up question about encoded polyline levels: http://stackoverflow.com/questions/9441088/calculating-value-of-levels-when-merging-encoded-polylines – Dan Mandle Feb 25 '12 at 04:02
6

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

Community
  • 1
  • 1
Dan Mandle
  • 5,608
  • 3
  • 23
  • 26
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.

Berry Ratliff
  • 11
  • 1
0

I am suggesting you may not have to do the concatenation on the server. Do it in the browser instead. All decoding occurs in the browser. It is very easy to splice decoded arrays together with javascript. You can use the "splice" method or you just iterate through each of the component arrays.

Berry Ratliff
  • 1
  • Berry, that's what we were doing originally but it was taking the end users a long time to download all of the pairs, that's why we had to switch to encoded polylines. – Dan Mandle Feb 12 '12 at 17:36