In part 1 I showed how to use and optimize performance on polylines in Google Maps using Javascript. In this article I will show you how to get even better performance by encoding the polylines on the server.
Encoding polylines on the fly
When dealing with dynamic data you may have to encode the polylines on the fly. In this example I will use PHP to perform the encoding. I have rewritten a php script made by Jim Hribar and built his functions into a class for more convenient use. I’ve also made some small changes to the code. The code itself is essentially a rip-off from Mark MacClure’s Javascript class.
The PolylineEncoder Class
To use the class is simple. First you need to call the constructor of the class: $polylineEncoder = new PolylineEncoder($point);
The constructor
PolylineEncoder optionally takes four other arguments. When they are left out these default settings are used:
- numLevels = 18
- zoomFactor = 2
- verySmall = 0.00001
- forceEndpoints = true
numLevels and zoomFactor controls how many zoomlevels the encoding should take account for and in which intervals the map should change the number of displayed coordinates.
verySmall controls what distance between coordinate the algorithm should regard a short enough distance for a coordinate to be removed. So if you want to decrease the number of coordinates used, you should set the verySmall argument to a higher number.
forceEndpoints is a boolean and if set to true ensures that the two ending points of the polyline are displayed at all zoom-levels. I really don’t see a reason to set this to anything but true.
I myself tend to use the default settings since they provide a good result.
Encoding the points
The $encoded_polyline = polylineEncoder->dpEncode() method returns an associative array with the following keys.
- Points
A string containing the encoded points - Levels
A string containing the encoded levels - ZoomFactor
The applied Zoom Factor (Same as passed to the constructor) - NumLevels
The applied NumLevels (Same as passed to the constructor)
A complete call to the EncodePolyline could look something like this.
// Include the file containing the class
include("PolylineEncoder.php");
// Create a nested array containing the coordinates
$points = array(
array(
59.6919,
17.8582
),
array(
59.3030,
18.0395
),
array(
58.9789,
17.5341
)
);
// Create a new instance of PolylineEncoder and supply the array
// as an argument to the constructor
$polylineEncoder = new PolylineEncoder($points);
// Encode the coordinates by calling dpEncode(), it returns an array containing the
// encoded coordinates and levels.
$encoded_points = $polylineEncoder->dpEncode();
// The resulting output
$encoded_points["Points"]; // "kqikJw|~kBr}jAclb@rh~@xuaB"
$encoded_points["Levels"]; // "PMP
$encoded_points["ZoomFactor"]; // 2
$encoded_points["NumLevels"]; // 18Note: To learn more about how to use the optional settings for tweaking the encoded polyline, read A description of Google’s encoded polylines and The encoding algorithm for the levels string.
Download the class
The PolylineEncoder class is released under GPL MIT license and may be used and changed freely.
Download PolylineEncoder.php.txt
Making use of the encoded polyline
Now that we have an encoded polyline its time to make good use of it in Google Maps. To create a GPolyline from the encoded coordinates you use the method GPolyline.fromEncoded().
// Creating an encoded GPolyline
GPolyline.fromEncoded({
color: string,
weight: number,
opacity: number,
points: string,
levels: string,
numLevels: number,
zoomFactor: number
});As you can see it takes an object literal as an argument. The first three keys are purely for how the polyline will be styled. The keys points and levels are the ones that will be fed with the encoded polyline. The last two keys, numLevels and zoomFactor should match the settings you used when encoding the coordinates. If they don’t match, the polyline will not be rendered correctly.
Documentation alert
The documentation doesn’t seem to be quite up to date on this, since it specifies the method to be used like this:
GPolyline.fromEncoded(color?, weight?, opacity?, latlngs, zoomFactor, levels, numLevels)
Stay clear from this use since it’s deprecated and probably won’t work or eventually will stop working.
Adding it to the map
So adding an encoded polyline to your map is very much like adding a normal polyline to it. The only difference is that instead of creating the polyline with the constructor of GPolyline(), you call the GPolyline.fromEncoded() method and pass the encoded points and levels to it.
// Instanciate a new map
var map = new GMap2(document.getElementById('map'));
map.setCenter(new GLatLng(59.3219, 17.6165), 8);
// Create the polyline from the encoded points
var polyline = GPolyline.fromEncoded({
color: '#FF0000',
weight: 6,
opacity: 0.6,
points: 'kqikJw|~kBr}jAclb@rh~@xuaB',
levels: 'PMP',
numLevels: 18,
zoomFactor: 2
});
// Add the polyline to the map
map.addOverlay(polyline);Even better performance
To get even better performance you have to use a pre-encode polyline to serve directly to the Javascript. This way you save the time the PHP-script takes to execute the encoding. In many cases this might not be possible, but if it is, it delivers the best performance.
Watch the pre-encoded example.
The improved load-time is pretty big. When I compare this example with the one encoding the polyline in the browser using Javascript, I get load times that’s range from 2 seconds (Safari) to over 20 seconds faster (IE).
All test scenarios
Here’s all the tested cases, from both this and the previous article.
- Simple unencoded polyline
- Complex unencoded polylines
- Complex encoded polylines, encoding done in browser with Javascript
- Complex encoded polylines, encoding done dynamically on server
- Complex pre-encoded polylines
Other resources
There are several server-side classes in different languages for encoding polylines, including Perl, Java and Ruby, available at Encoding polylines for Google Maps, a website by Mark McClure.
I have yet to find a class written in C#. If you find one or has written one yourself, I would be more than happy if you could tell me about it.
Update [2008-11-26]
I have now written a C# class to encode polylines by porting Mark Rambows Java class. I’ve also made some other modification to it to make it easier and more natural for C# coders to use.
Encouraged by this article, markw has also made a C# class, which can be download from Google Code.
My Google Maps book
If you found this article useful you might be interested in my book Beginning Google Maps API 3. It covers everything you need to know to create awesome maps on your web sites. Buy it on Amazon.com
November 21, 2008 at 10:26 am
A C# implementation of the encoding algorithm can be found here.
November 21, 2008 at 2:03 pm
markw: Thanks a lot! Can’t wait to try it.
November 21, 2008 at 3:16 pm
markw: After looking a little closer at the code I noticed that it just encodes the polyline. It’s not performing any reduction of the number of coordinates to be displayed at different zoom-levels. Thus the only performance you gain is reduced size of the data being transfered.
So, I guess I’m still on the lookout for a C# implementation.
November 24, 2008 at 4:51 pm
I’ve translated the Java implementation into C# – see http://code.google.com/p/csharp-polyline-encoder/.
Let me know what you think if you get the chance. If it’s crap I’ll take it down.
November 25, 2008 at 11:24 am
markw: Nice! I’ve also translated it but I run into a strange bug which I haven’t figured out yet. When I tried your class I see that the same error occurs in that as well. The error is that if the coordinates have more than 4 decimals the polylines get screwed up. I’ve solved it by rounding the decimals to just 4 decimals but that’s not a really good solution. Do you have any idea what might cause this?
Here’s my PolylineEncoder class.
November 25, 2008 at 1:40 pm
Thanks for the warning! I haven’t spotted the bug yet – can you give me an example trackline that causes the problem and I’ll take a look.
November 25, 2008 at 3:26 pm
markw: Sure! If you contact me through the contact page and give me your email I will mail you a trackline.
November 26, 2008 at 1:33 pm
The bug is found and fixed! It turned out to be a fairly trivial one having to do with escaping of strings.
December 10, 2008 at 5:23 am
Mark, fine work with the PHP class, but one suggestion to make it much more useful. When running storage of map objects in the mySQL/Php world, the geometric object is splendid as it allows built in functions to be run on your tables of data. For instance, run SELECT and sort by length, or area… all from SQL prompt.
While I like the ability to encode the line and improve loading speed for the client, I would of course still store the data in both a geometry object, and encoded string. If you could add an option to your class that would take a mysql geometry object, or linestring, and do the rest from there, it would make it even more useful in the server environment. If not I can still write this for my own implementation, but I think others will like it as well.
Finally, if you have nothing else to do, what better than pull out your hair and build an SQL SP to achieve encoding?
Thanks.
December 10, 2008 at 8:51 am
Joseph: That’s a good idea! I’ve actually implemented support for SqlGeometry in the C# class for a project I’m currently working on where geo data is stored on a SQL Server 2008. But it’s not a part of the class I’ve made publicly available. The reason is that in order to make it work you have to install a few dll’s and add extra references to your project, so for the sake of simplicity I left it out.
I haven’t done anything like that for the PHP-class but it’s a great idea. I will look into it when I find the time.
P.S Mark has made a C# class, I’ve refactored the PHP code. 🙂 /Gabriel
December 12, 2008 at 9:23 pm
Hello, you saved me a lot of work with your excellent polylineencoder php-class. It’s awesome fast and works perfect for me, thanks a lot for your great effort! 🙂
December 13, 2008 at 1:11 pm
dompie: I’m glad that you found it useful! 🙂
January 2, 2009 at 6:00 pm
I very liked this post. Can I copy it to my site?
Thanks in advance.
Sincerely, Your Reader.
January 3, 2009 at 4:27 pm
@Timur: I’m happy to hear that you like my post. Contact me through the contact page with a vaild e-mail adress and we can talk about it.
February 4, 2009 at 10:23 am
Hi, thanks for the excellent work. How about the bug fix in #8?
I just download the class and it is still there.
Thanks
February 4, 2009 at 10:49 am
Anan: Hi! The faulty line was still there but commented out. Now I have removed it completely.
Cheers!
February 6, 2009 at 5:52 am
Even when I used “PointsLiteral”, I still got incorrect polyline. Why? To insert correctly into MySQL database you need 4 backslashes not just 2. So I add 2 more and happy now :> Thanks
February 18, 2009 at 11:23 pm
In line 22 of your first code example, I suppose you mean to have $points rather than $point as the argument to PolylineEncoder()?
February 19, 2009 at 7:20 pm
Tom von Alten: You’re absolutely right! Thanks for pointing it out! I have now corrected it in the code example.
April 2, 2009 at 9:10 pm
I have a mysql table with around 8,000 coords representing the 80 canals and navigable rivers of the UK.
As you can see from http://www.saveourwaterways.info/test.phtml, using the polyline encoder class, the ends of each succeeding waterway joins up to the beginning of the next in sequence.
What I am planning is to draw each of the 80 waterways as a separate polyline but it concerns me that this will mean 80 overlays which suggest to me that it might be sluggish. I wondered if anyone has any ideas how I could insert a start and end point to each waterway so I can use just one layer without them merging with each other?
Cheers
Will
April 3, 2009 at 12:47 pm
Hi!
Do you have any idea what is the reason of such error:
“Parse error: syntax error, unexpected T_ARRAY, expecting ‘)’ in /home/pracus/public_html/minuta_pl/maps/polylineEncoder.php on line 69”
when trying to display this URL: http://minuta8.pl/maps/example.php ?
polylineEncoder.php file contains exactly the same source as your class file upon, no character is changed and example.php contains:
dpEncode();
header(“Status: 200”);
header(“Content-Type: text/html” );
print “Encoded points string: “.$encoded_points[“Points”];
?>
I don’t understand what’s wrong.
Thank you in advance!
April 3, 2009 at 12:48 pm
I’m sorry. It cut a part of example.php source before. It is:
// Include the file containing the class
include(“polylineEncoder.php”);
// Create a nested array containing the coordinates
$points = array(
array(
59.6919,
17.8582
),
array(
59.3030,
18.0395
),
array(
58.9789,
17.5341
)
);
// Create a new instance of PolylineEncoder and supply the array
// as an argument to the constructor
$polylineEncoder = new PolylineEncoder($points);
// Encode the coordinates by calling dpEncode(), it returns an array containing the
// encoded coordinates and levels.
$encoded_points = $polylineEncoder->dpEncode();
header(“Status: 200”);
header(“Content-Type: text/html” );
print “Encoded points string: “.$encoded_points[“Points”];
April 3, 2009 at 1:38 pm
@Will Chapman: I have no experience myself of working with spatial data in mySql but I know that it’s possible to store the data as a geometric object (read Joseph Lust’s comment) and I suppose that there are methods to merge several geometric objects.
What I do have experience of is doing that same thing on SQL Server 2008. By using the method STUnion() I’ve been able to merge several polylines into one.
@pracus: I’m sorry but i can’t reproduce your error. Are you sure you’re using the right polylineEncoder? Maybe if you can email your files I can take a look at it.
April 3, 2009 at 3:06 pm
My God!
You would not believe it!
It was the case of PHP parser version. I had early PHP5 which doesn’t support some methods and statements.
Thank you again, Gabriel,, for your help!
Almost whole day lost on searching for the case 🙁
April 14, 2009 at 2:48 am
Python port of Mark McClure’s algorithm:
http://project.bycycle.org/browser/spinoffs/glineenc.py
http://wyattbaldwin.com/2007/04/19/google-maps-encoded-polylines/
Any idea on how I can join/split several polylines into one (polycluster :-)) on different zoom levels?
April 24, 2009 at 8:39 am
we have polylines with millions of points. we split them all into encoded polylines with max 150 – 250 points. store the encoded strings in the mysql db. after zooming and moving the map we load the needed polylines. sending the data with xml to the client wastes a lot of time for parsing the xml data. create you own format for sending data in “raw mode”. its faster.
http://www.wanderservice-schwarzwald.de
Use Firefox, IE ist too slow.
Our next step are encoded and reduced polylines for each zoom level. Currently zoom ist not available, but it works on all all zoom levels.
August 10, 2009 at 10:38 pm
Thank you for this two great posts about polyline enconding : well explained with full examples and good blog desgin !
In source provided, i think there is a tiny error which seems related to bad Google Documentation.
McClure using Math.Floor for “the Step 2” (http://code.google.com/intl/fr/apis/maps/documentation/polylinealgorithm.html), but the doc says “rounding the result” and provide the exemple
-179.9832104 -> -17998321
With Math.floor, we obtain -17998322.
Another person reported the error in API documentation : http://code.google.com/p/gmaps-api-issues/issues/detail?id=670
October 26, 2009 at 5:37 am
Give me your ‘road.php’ file. Thks!
November 17, 2009 at 3:55 am
Interesting article, and nicely written. About load times, I am not so sure if polyline encoding really improves performance if you already have zip compression enabled on your server (for example using zlib.output_compression in .htaccess).
By the way, on your server there are a few things to be optimized, according to YSlow…
November 17, 2009 at 11:35 pm
Benco: The greatest benefit doesn’t come from that the file size gets smaller, I’m sure that using zip compression would probably be just as effective. The main benefit comes from not doing the encoding with JavaScript. Because processing it with JavaScript is really slow compared to processing it on the server. Especially in some browsers (read IE).
I haven’t really done any optimizing on this site, so there’s a lot of things I could do. If only I can find the time… 🙂
November 27, 2009 at 7:48 pm
Hey there Gabriel,
I’m working with encoded polygons both using your PHP port and the original Javascript version of the dpEncode utilities.
Everything works great, however am having issues using my complex polygons within Google Static Maps. I may be SOL (Sh*t out of Luck), but no hurt in seeking some advice.
http://code.google.com/apis/maps/documentation/staticmaps/#Paths
Basically when using a simple encoded polygon things work fine. However when using a complex encoded polyline (72 points used to plot a radius circle) I get nothing but problems.
Pretty sure that the underlyiing issue is that the Google Static Map API does not allow me to supply the encoded ‘zoomLevels’ like the JS API does (using GPolyline.fromEncoded).
This Works
While…
This does not
I’ve also tried passing the points to the static maps but of course the request URI is too long.
Encoded Polyline:
iuzxDrqatQfCipBxKmoBdTwmBlekBnd@wgBfl@qcBrs@q~Apz@{xAdaAorAdgAokAtlA{cApqAw{@xuAes@jyAej@h|A{`@n~AiW~_BqMt`BwCt`BbD|_B~Ml~AtWf|Afa@fyAlj@tuAls@jqA|{@nlA|cA~fApkA~`AlrAlz@xxAns@j~A`l@hcBjd@ngBhxjBbTjmBvK`oBfCzoBgC|oBwK`oBcTjmBixjBkd@ngBal@hcBos@j~Amz@xxA_aAlrA_gAnkAolA~cAkqA|{@uuAjs@gyAnj@g|Afa@m~AtW}_B|Mu`BdDu`BwC_`BqMo~AiWi|A}`@kyAcj@yuAes@qqAw{@ulA{cAegAokAeaAorAqz@{xAss@q~Agl@qcBod@ygBmckBeTwmByKmoBgCkpBEncoded Levels:
PCECGCFDCICECGCFDCKCECGCFDCICECGCEDCLCDECGCECICDFCGCECKCDFCGCECICDFCGCECPSomething tells me I’m trying to do way too much with the Static Maps.
December 28, 2009 at 8:33 pm
Hi, great articles both part I and II, I wonder if it is recommended or a good approach if I encoded the points in the server and save the encoded points into a database record, say MySQL, could this cause problems in the future? which ones?
Thanks a lot!
Regards from Mexico
December 29, 2009 at 10:46 am
Keogh: Performance wise that would be the best solutions. The drawbacks I can see is that it’s a bit more work to update the information in the database and also if you in the future want to use the data for some other purpose in a context which does not support encoded polylines.
March 23, 2010 at 10:12 am
Hi, there are 1000 lines in my application (a topology graph) rather than one line with thousands of points. Any suggestions?
Thanks,
Dianbo
September 16, 2010 at 12:22 am
I tried different tools – this is still working, THX.
I’m going to implement this class into an extension for CMS TYPO3, using rggooglemaps.
nice work.
March 26, 2011 at 5:57 pm
Hi,
I am trying to use this class, but if i insert more then 100 points in does not return return anything. Less then that it works fine… 100 is approximate number…
i would want to insert more then 2000points…
i have checked the data and it looks fine…
do you know what could be the reason?
nice day
Primoz
March 26, 2011 at 11:10 pm
sorry just debugger was showing null instead of full string.
niceday
May 9, 2012 at 4:52 pm
Fairly old blog entry. But hoping you’ll read the comment. I tried your C# class to encode polylines on the server. But if i try to decode them on the client side to use it with maps v3 i’ll get an
a is undefined (47 out of range 45)
error message from googles main script. The error message is not really helpful. Do you know if the encoder is working with maps v3?
If there are known issues with the encoder and v3 I don’t have to find out where this issue comes from. 😉
Best regards
May 18, 2012 at 12:14 pm
Thanks for sharing your info. I really appreciate your efforts and I will be waiting for your further write ups thanks once again.
html5 converter