In usability we trust

UX and all things web

Polylines in Google Maps [Part 2]

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"]; // 18

Note: 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);

Watch the live example.

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.

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.

Download PolylineEncoder.cs

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

39 Comments

  1. A C# implementation of the encoding algorithm can be found here.

  2. markw: Thanks a lot! Can’t wait to try it.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. markw: Sure! If you contact me through the contact page and give me your email I will mail you a trackline.

  8. The bug is found and fixed! It turned out to be a fairly trivial one having to do with escaping of strings.

  9. 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.

  10. 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

  11. 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! πŸ™‚

  12. dompie: I’m glad that you found it useful! πŸ™‚

  13. I very liked this post. Can I copy it to my site?
    Thanks in advance.

    Sincerely, Your Reader.

  14. Hi, thanks for the excellent work. How about the bug fix in #8?
    I just download the class and it is still there.
    Thanks

  15. Anan: Hi! The faulty line was still there but commented out. Now I have removed it completely.
    Cheers!

  16. 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

  17. In line 22 of your first code example, I suppose you mean to have $points rather than $point as the argument to PolylineEncoder()?

  18. Tom von Alten: You’re absolutely right! Thanks for pointing it out! I have now corrected it in the code example.

  19. 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

  20. 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!

  21. 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”];

  22. @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.

  23. 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 πŸ™

  24. 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?

  25. 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.

  26. 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

  27. Give me your ‘road.php’ file. Thks!

  28. 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…

  29. 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… πŸ™‚

  30. Michael Griffiths

    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@ygBmckBeTwmByKmoBgCkpB

    Encoded Levels:

    PCECGCFDCICECGCFDCKCECGCFDCICECGCEDCLCDECGCECICDFCGCECKCDFCGCECICDFCGCECP

    Something tells me I’m trying to do way too much with the Static Maps.

  31. 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

  32. 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.

  33. Hi, there are 1000 lines in my application (a topology graph) rather than one line with thousands of points. Any suggestions?

    Thanks,

    Dianbo

  34. 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.

  35. 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

  36. sorry just debugger was showing null instead of full string.
    niceday

  37. 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

  38. lauraine 2012

    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

Leave a Reply

Your email address will not be published.

*