Exploring Google Polylines algorithm in Ruby
We start this post with a definition from wikipedia of what is a polyline, also known as a polygonal line:
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.
So with a picture, we are now talking about polygonal lines given by GPS coordinates.
Google Polylines are a little more than just polygonal lines. It’s a GPS polygonal path encoded as a character string made only of ASCII symbols that can be passed as is through URLs, allowing their usage in REST APIs. Here is an example of the resulting encoding: _p~iF~ps|U_ulLnnqC_mqNvxq`@.
At Klaxit, we use polylines at divers steps of our process. Indeed, we required to encode and decode polylines at a reasonable speed in order to maintain the quality of service we provide to our costumers.
Since our servers are developed with the ruby language, we were first using the ruby gem polylines. But this gem appeared to be quite slow, and the team rewrote it to the open source gem fast-polylines. As the more tech addict of you could see by looking at the source code¹ from the google-map-services gem documentation, our implementation is quite close to google’s one although we allow arbitrary precision as a parameter.
Through the remaining paragraphs of this article, I would like to go a bit deeper on polylines by explaining with simple words the idea behind the algorithm and how we can tweak it to handle spatio-temporal polylines², that is polylines from timed GPS coordinates.
The polyline algorithm have to reconcile two goals:
- We want our polygonal path usable in an url as a simple string, without further encoding.
- We need to compress our polygonal line, so that the number of byte required to store it remains small.
As explained by google themselves, the algorithm consist of the following steps:
- Take a list of GPS coordinates [(Latitude, Longitude)], where Latitude and longitude a floating values.
- Convert each number to an integer by multiplying by 10⁵ (this is the precision you want on your coordinates) and rounding it³.
- For each number, do some bit shifting and shuffling magic, then split this long string of 0 and 1 in chunks.
- Convert each chunk into a decimal number and add to it the ASCII code of
?. You end up with a string representation of your number. - Concatenate all this little string together, in the order
Lat1, Lng1, Lat2, Lng2, ... LatN,LngNso that you end-up with a unique string.
There is one more detail I omitted for simplification purpose. Although the previous algorithm could works, you would end up with really long strings, since the bigger the integer is (Think of 48.12345 being represented with 4812345 while 0.00000 is represented only with the symbol 0) the more characters it will takes to write it in the polyline. There is a simple trick that solve our problem. Instead of writing the list of coordinates Lat1,Lng1,Lat2,Lng2,Lat3,Lng3 … we write the difference between the previous coordinate (something of the form Lat3-Lat2, Lng3-Lng2) and the current one. Let me give you an example:
Instead of encoding the 3 coordinates [48.101, 27.103, 48.123, 27.143, 48.120, 27.125, 48.117, 27.129] directly, we will encode[48.101, 27.203, 0.012, 0.040, -0.003, -0.018, -0.003, 0.004] which is much smaller.
Now that you can encode a list of GPS coordinates into a polyline, you may be asking how can you decode them and recover the data. Thanks to the bit shifting magic⁴, all the character but the last one of the encoding string coming from a single number will have its ASCII value strictly below _ . This allows us to split the string back into little strings and reverse the whole process. Here is the code that split the string back into smaller chunks:
We did it! Know you know everything you need to have a high level understanding of the algorithm. You can convert a list of coordinates (Lat, Lng) into a polyline and revert the polyline back to this list of number.
But what if we want to encode a list of triplet (Lat, Lng, Timestamp)?
We now have all the tools to answer the question. Remember that we encode a pair (Lat, Lng) by converting Lat and Lng to integers. But a Timestamp is already an integer. So all we can basically skip this step. 🙂
Then, we can just encode into a string Lat1 , Lng1 and Timestamp1 . For the next step we compute Lat2-Lat1 , Lng2-Lng1 and Timestamp2-Timestamp1 . We encode each of this three number, and repeat this process. Once we have processed all our triplets, we glue all this strings together in this order. We end up with a free dimensional polylines. We could generalize this process to 4 dimensions (4-uplets) or even n (n-uplets).
To finish, here is the code for encoding the spacio-temporal polylines. I leave you the decoding as an exercise. Have fun!
¹ You can access the code by clicking the View Source link.
² I love how this name sounds like coming out from a science fiction book. Please forgive me the naming.
³ This means we have a location with a precision to 5 digits after the dot, which is enough two differentiate two points one meter apart.
⁴ It’s the OR 0x20 part of the algorithm described by google.
