Java Google Maps polyline encoding function

In this post I'm going to detail the polyline encoding method I wrote in Java a while back.

It was originally written to graphically show the areas covered by certain UK postal sectors on Google Maps. The program converted the post codes in the postal sector into a list of points defining either a convex or concave hull and produced the URL of a Google Map showing the area. The concave hull algorithm (based on alpha shapes) doesn't work too well and takes an age to run so I haven't really used it.

It didn't actually display the map as the firewall where I work gets a little upset by multiple requests for the same address (as would happen when you test anything).

Anyway, on to the function.

The definition of the algorithm is here on the Google developers maps site. I won't go through it as I'll just be repeating what is written, with much more style, on the algorithm site.

The definition of the static map API is here, again on the Google developers maps site.

Taking the definition of the algorithm, I produced this, messy, Java code:


-----------------------------------------------------------------------------
private String encodePolyline(double latlong){
    //Google's procedure for encoding polyline data
    //This doesn't cater for backslashes in string literals i.e. the character sequence "\"
    //which should be returned as "\\". Function createPolyLine will do this.

    String poly;
    int signNum = (int) Math.signum(latlong);
    
    int b = (int) Math.round(latlong*1e5);
    ArrayList<Integer> ab = new ArrayList<>();
    
    //Left shift
    b=b<<1;
    
    //Invert if negative
    if(signNum<0){
        b=~b;
    }
    
    //Split into 5-bit chunks and reverse order
    while(b>0){
        ab.add(b % 32);
        b=b>>5;
    }
    
    //Convert to ASCII
    StringBuilder nc4 = new StringBuilder();
    for(int i=0;i<ab.size()-1;i++){
        //Or with 0x20 and add 63
        char c = (char) ((ab.get(i) | 0x20)+63);
        nc4.append(c);
    }
    //Add 63 to last chunk
    nc4.append((char) (ab.get(ab.size()-1)+63));
    poly=nc4.toString();
    
    return poly;
}
-----------------------------------------------------------------------------

This function takes a latitude or longitude as a double. It then produces the string that corresponds to the string literal for that point. If you want to show an area, then you need to convert a list of points and string them together.

As it says on the polyline site, every point after the first should be the difference from the previous point.

Therefore to produce an area we will need another function. This one is called createPolyline and calls the encodePolyline function for every point.


-----------------------------------------------------------------------------
private String createPolyLine(ArrayList<LatLon> hp){
    double oldlat=0;
    double oldlon=0;
    StringBuilder nb = new StringBuilder();
    for(int i=0;i<hp.size();i++){
        latlon temp = hp.get(i);

        double p1 = temp.getLat();
        double p2 = temp.getLon();
        
        if(Math.abs(p1-oldlat)>=0.00001){
            String temp2 = encodePolyline(p1-oldlat);
            nb.append(temp2);
        } else {
            nb.append("?");
        }
        if(Math.abs(p2-oldlon)>=0.00001){
            String temp2 = encodePolyline(p2-oldlon);
            nb.append(temp2);
        } else {
            nb.append("?");
        }
        oldlat = p1;
        oldlon = p2;
    }
    
    String temp = nb.toString();
    
    //Check temp for "*\*" pattern
    Pattern pattern = Pattern.compile("\".*\\.*\"");
    Matcher matcher = pattern.matcher(temp);
    
    while (matcher.find()) {
        //Use matcher.start() and .end() to replace "\" with "\\"
        temp = temp.substring(0, matcher.start()) + temp.substring(matcher.start(),matcher.end()).replaceAll("\\\\", "\\\\\\\\") + temp.substring(matcher.end());
    }
    
    return temp;
}
------------------------------------------------------------------------------

The function takes an arraylist of latitude and longitude objects. These are essentially just Points and the function can be modified to use Points instead, if that's what is required.

The last bit of the function doubles any back slash characters in the polyline string. This is done because the back slash is an escape character in URLs.

One more piece is needed for the puzzle to be finally finished. A function to produce the final URL:


private String produceGoogleURL(String polyline){
    return "http://maps.googleapis.com/maps/api/staticmap?size=512x512&maptype=roadmap&sensor=false&path=fillcolor:0xAA000033%7Ccolor:0xFFFFFF00%7Cenc:" + polyline;
}

This produces a 512*512 map of the area around the String polyline with the area defined by the polyline filled in red.

As an example I ran the full program for the post codes in the B postal sector. These are all around Birmingham. The output from the program gives this:


Type=Convex Hull of B sector
Process took 13 seconds
Number of non-zero postcodes=41839
Google maps address=http://maps.googleapis.com/maps/api/staticmap?size=512x512&maptype=roadmap&sensor=false&path=fillcolor:0xAA000033%7Ccolor:0xFFFFFF00%7Cenc:qgj~Hdi`L|wFwtFfoJ_dK|dNqs`@~|@kmCkiVekV}xm@moTeqb@sxHcjGbiSfFxuBjkAl`Fvm_@fez@dhDt`F|dHdbGvFrEhzZz~E
Point;x;y
0;390686;269448
1;393360;265014
2;397602;258457
3;409383;249818
4;410944;248718
5;419085;262024
6;426459;288715
7;429742;308990
8;422688;313706
9;421405;313571
10;418974;312202
11;398493;293680
12;396042;290671
13;393221;285443
14;393149;285305
15;390686;269448

and the map produced from Google is this:

If you have any suggestions on how to improve this then please do comment.

Of course there are now websites that can do the same and look quite impressive. However if you need to do something in Java then hopefully this will help.