Google Mapping and Conversion

Posted: February 2, 2012 in Android Dev

Disclaimer: This is for informational purposes only. Google owns the map tiles. So don’t try to profit from them. Besides, Google might (and probably will) change their algorithms some day.

This page describes how to harness the beautiful map data provided publicly on google maps. These C# routines were created by analyzing Google’s own obfuscated javascript libraries.

Google maps tiles are stored simply by X,Y coordinates, together with a zoom level. Zoom levels range from 17 (most area) to 0 (most detailed). As of now, the tiles are each 256×256 pixels. Each successive zoom level has 4 times as many map tiles (2x in the X direction, and 2x in the Y direction) as the previous level. The number of map tiles for each zoom level are given by this simple formula:

x = 0 to 2^(17-zoom)
y = 0 to 2^(17-zoom)

Of course, the number of pixels is 256 times this number, since the tiles are each 256 pixels to a side.

Converting (lat, lng, zoom) to (x, y, zoom)

Mapping a sphere (earth) onto a rectangle cannot be done without distortion. One of the most generally accepted methods, and the one the Google engineers have chosen is called Mercator’s projection. There’s some calculus involved, but the end result is fairly simple. Here is a function that I’ve written to convert a latitude, longitude, and zoom level to google map tile x and y:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class gmaps {
    ...
    public Point tile(double lat, double lng, int zoom)
    {
        return new System.Drawing.Point(Xpixel(lng, zoom) / 256, Ypixel(lat, zoom));
    }
    public int Xpixel(double lng, int zoom)
    {
        // Instead of -180 to +180, we want 0 to 360
        double dlng = this.lng.Value + 180.0;
        // 256 = tile Width
        double dxpixel = dlng / 360.0 * 256 * Math.Pow(2, 17 - zoom);
        int xpixel = Convert.ToInt32(Math.Floor(dxpixel));
        return xpixel;
    }
    public int Ypixel(double lat, int zoom)
    {
        // The 25 comes from 17 + (256=>2^8=>8) 17+8 = 25
        // ypixelcenter = the middle y pixel (the equator) at this zoom level
        double ypixelcenter = Math.Pow(2, 25 - zoom - 1);
        // PI/360 == degrees -> radians
        // The trig functions are done with radians
        double dypixel = ypixelcenter - Math.Log(Math.Tan(lat * Math.PI / 360 + Math.PI / 4)) * ypixelcenter / Math.PI;
        int ypixel = Convert.ToInt32(Math.Floor(dypixel));
        return ypixel;
    }
    ...
}

Downloading map tiles

This is the part that my Google friends like to keep changing on me. The URL should be simple, if you know the x,y, and zoom. The “v” parameter is probably “version”, which when I wrote this function was at w2.5, and now it seems to be at w2.6, although 2.5 seems to still work. How long version 2.5 will keep working for is anybody’s guess!

1
2
3
4
5
6
7
8
class gmaps {
    ...
    String tileURL(int x, int y, int zoom)
    {
        return "http://mt.google.com/mt?v=w2.5&x=" + x + "&y=" + y + "&zoom=" + zoom;
    }
    ...
}

Well, that wasn’t so bad! Now, for the super cool satellite images. They are encoded so that only people with the secret decoder ring can download them. I borrowed the algorithm from the original Google javascript and converted it to C#:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class gmaps {
    ...
    String satURL(int x, int y, int zoom)
    {
        String url = "http://kh.google.com/kh?v=3&";
        int e = Convert.ToInt32(Math.Pow(2, 17 - zoom));
        String f = "t";
        for (int h = 16; h >= zoom; h--) {
            e = e / 2;
             if (y < e) {
                if (x < e) {
                    f += "q";
                } else {
                    f += "r";
                    x -= e;
                }
            } else {
                if (x < e) {
                    f += "t";
                    y -= e;
                } else {
                    f += "s";
                    x -= e;
                    y -= e;
                }
            }
        }
        url += "t=" + f;
        return url;
    }
    ...
}

Working with polylines

Polylines are those cool blue semi-transparent lines that show you how to get from point A to point B. They are stored in an ingenious coded string that compresses the data into a normal ASCII string with no weird characters. This string stores a series of numbers as the starting longitude,latitude, followed by lat&lng offsets from the previous:

([lng0], [lat0], [lng1-lng0], [lat1-lat0], [lng2-lng1], [lat2-lat1], ...)

I hope that makes sense. Maybe an example will help. I will use simple numbers that are probably in the middle of some ocean in the arctic, but you will get the picture. Say I wanted to draw a square box using the following 4 longitude, latitude pairs:

(50,50)
(50,60)
(60,60)
(60,50)
(and back to 50,50)

The following would be my polyline pair:

(50,50); (50-50=0, 60-50=10); (60-50=10, 60-60=0); (60-60=0, 50-60=-10); (50-60=-10, 50-50=0)
=>
(50,50, 0,10, 10,0, 0,-10, -10,0)

Here’s the ingenious part: the numbers are stored as ascii coded decimal, which saves mucho space and bandwidth. The coding is such that the decoding and encoding algorithm is straightforward, and has good compression. It also does not have to deal with a special case for the first longitude,latitude pair.

To find a polyline of directions, you have to look inside a result returned by google maps. What I use it for is to find from my current location (lat, lng) to an address (my destination), but you can use any query that you would normally give to google maps (i.e. “1600 Pennsylvania Ave NW, Washington, DC 20006 to 38.870788, -77.055788″ which will take you from the white house to the pentagon). Just URL encode your query, and stick it in this url:

http://maps.google.com/maps?q=1600+Pennsylvania+Ave+NW,+Washington,+DC+20006+to+38.870788,+-77.055788&z=13&output=js

What that returns is a lot of stuff, but the polyline is the part from <point>…….</point>. The string is HTML encoded, so watch out for HTML identites (&#xxx;). You must convert those to the proper ascii values. Here’s a C# function that will convert that polyline to a series of latitudes and longitudes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
using System.Collections;
class gmaps {
    ...
    // uses google's decodePolyline algorithm
    double[] decodePolyline(string polyline)
    {
        if (polyline == null || polyline == "") return null;
        char[] polylinechars = polyline.ToCharArray();
        int index = 0;
        ArrayList points = new ArrayList();
        int currentLat = 0;
        int currentLng = 0;
        int next5bits;
        int sum;
        int shifter;
        while (index &lt; polylinechars.Length)
        {
            // calculate next latitude
            sum = 0;
            shifter = 0;
            do
            {
                next5bits = (int)polylinechars[index++] - 63;
                sum |= (next5bits &amp; 31) &lt;&lt; shifter;
                shifter += 5;
            } while (next5bits &gt;= 32 &amp;&amp; index &lt; polylinechars.Length);
            if (index &gt;= polylinechars.Length)
                break;
            currentLat += (sum &amp; 1) == 1 ? ~(sum &gt;&gt; 1) : (sum &gt;&gt; 1);
            //calculate next longitude
            sum = 0;
            shifter = 0;
            do
            {
                next5bits = (int)polylinechars[index++] - 63;
                //next5bits = Convert.ToInt32(polylinechars[index++]) - 63;
                sum |= (next5bits &amp; 31) &lt;&lt; shifter;
                shifter += 5;
            } while (next5bits &gt;= 32 &amp;&amp; index &lt; polylinechars.Length);
            if (index &gt;= polylinechars.Length &amp;&amp; next5bits &gt;= 32)
                break;
            currentLng += (sum &amp; 1) == 1 ? ~(sum &gt;&gt; 1) : (sum &gt;&gt; 1);
            points.Add(Convert.ToDouble(currentLat) / 100000.0);
            points.Add(Convert.ToDouble(currentLng) / 100000.0);
        }
        return (double[])points.ToArray(typeof(Double));
    }
    // Please note: untested function!
    string encodePolyline(double[] pairs)
    {
        String polyline = updatePolyline("", 0, 0, pairs[0], pairs[1]);
        for (int i = 2; i+1 &lt; pairs.Length; i+=2)
        {
            polyline = updatePolyline(polyline, pairs[i-2], pairs[i-1], pairs[i], pairs[i+1];
        }
        return polyline;
    }
    //this adds one point to a polyline string
    String updatePolyline(String currentPolyline, double currentLat, double currentLng, double newLat, double newLng)
    {
        // Calculate what to add to polyline
        string polyline = "";
        int tmp;
        int lat1 = Convert.ToInt32(Math.Floor(currentLat * 100000));
        int lat2 = Convert.ToInt32(Math.Floor(newLat * 100000));
        int deltalat = Math.Abs(lat2 - lat1) &lt;&lt; 1;
        if (lat2 &lt; lat1) deltalat--;
        do
        {
            tmp = deltalat &amp; 31;
            deltalat &amp;= ~tmp;
            deltalat &gt;&gt;= 5;
            if (deltalat &gt; 0) tmp |= 32;
            tmp += 63;
            polyline += new string((char)tmp, 1);
        } while (deltalat &gt; 0);
        int lng1 = Convert.ToInt32(Math.Floor(currentLng * 100000));
        int lng2 = Convert.ToInt32(Math.Floor(newLng * 100000));
        int deltalng = Math.Abs(lng2 - lng1) &lt;&lt; 1;
        if (lng2 &lt; lng1) deltalng--;
        do
        {
            tmp = deltalng &amp; 31;
            deltalng &amp;= ~tmp;
            deltalng &gt;&gt;= 5;
            if (deltalng &gt; 0) tmp |= 32;
            tmp += 63;
            polyline += new string((char)tmp, 1);
        } while (deltalng &gt; 0);
        return currentPolyline + polyline;
    }
    ...

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s