How Google Maps splits the world in 2^20 256x256 tiles (2006)(cfis.savagexi.com)
cfis.savagexi.com
How Google Maps splits the world in 2^20 256x256 tiles (2006)
http://cfis.savagexi.com/2006/05/03/google-maps-deconstructed
23 comments
I worked in an R&D group at FSU back in 2003 making webmaps. When google maps came around, I spent a week deconstruction its inner workings. The tiling was such an obvious solution, but no one else was doing it yet.
Our next rev of the mapping software included tiling and progressive tile loading. We started with a commercial backend for creating the tiles (ESRI ArcIMS), and eventually switched to an open source solution (UWM's MapServer). Last I heard they had an entirely open source stack (MapServer, OpenLayers, gdal, etc).
Anyways, when I realized that Google had cached each and every one of these tiles - at every zoom level - I was simply confounded. It was the first time I actually contemplated the scale of a company like Google.
Our next rev of the mapping software included tiling and progressive tile loading. We started with a commercial backend for creating the tiles (ESRI ArcIMS), and eventually switched to an open source solution (UWM's MapServer). Last I heard they had an entirely open source stack (MapServer, OpenLayers, gdal, etc).
Anyways, when I realized that Google had cached each and every one of these tiles - at every zoom level - I was simply confounded. It was the first time I actually contemplated the scale of a company like Google.
I actually implemented Tiling at Trailworks.com back in 1998 for a prototype that worked almost exactly like Google Maps, complete with drag-to-scroll and even drag-to-throw (but pre-dating mousewheels, therefore no mousewheel-zoom). In IE4/NN4, no less.
The problem back then was storage. Even for the US-only trail maps we were doing, there was no way we were going to store all those tiles at the $$$/GB that hard-drive space went for at the time. The plan was to cache only the most popular areas, and rebuild outlying tiles as necessary.
The problem back then was storage. Even for the US-only trail maps we were doing, there was no way we were going to store all those tiles at the $$$/GB that hard-drive space went for at the time. The plan was to cache only the most popular areas, and rebuild outlying tiles as necessary.
Yeah, it's 17,179,869,184 tiles for the entire earth 4^(N-1), where N is number of zoom levels, which is 18. Granted, a great deal of these redirect to their solid blue ocean tile.
EDIT: "Each tile is 256 pixels square and the number of tiles across at each zoom level is given by this formula: Math.pow(2, zoom)"; ops I missed the word "across" :)
How did you come up with that number? The sum loop that follows reports 524287 tiles total.
#include <stdio.h> #include <math.h> int main(void) { int i; double tot = 0; for(i = 0; i <= 18; ++i) tot += exp2(i); printf("tot %f\n", tot); return 0; }
How did you come up with that number? The sum loop that follows reports 524287 tiles total.
#include <stdio.h> #include <math.h> int main(void) { int i; double tot = 0; for(i = 0; i <= 18; ++i) tot += exp2(i); printf("tot %f\n", tot); return 0; }
If you've ever done any computer programming, you know that the top left of the screen is considered the origin
If you've ever done any OpenGL programming, you know that the bottom left of the screen is considered the origin
If you've ever done any OpenGL programming, you know that the bottom left of the screen is considered the origin
The reasons he states is why Miller (EPSG 54003) is a better projection. Not really a significant increase in complexity either.
http://mathworld.wolfram.com/MillerCylindricalProjection.htm...
http://mathworld.wolfram.com/MillerCylindricalProjection.htm...
Plus, the tiles are rendered once, no need for heavy calculations on-demand.
Well, there is still reprojection done on-the-fly. For instance, when you overlay a set of points or a polygon on a Google Map, these points have to be reprojected to be overlaid. This is done in JavaScript on the client side.
Not with the Google Maps Data API : http://code.google.com/intl/us/apis/maps/documentation/mapsd... Other overlay apps/mashups are using datasets for the most incomparably smaller than the base map data.
There are two things going on here. Raster images that are overlaid must be in Google's Mercator Projection, correct. However, when you provide shape data (polygons, points, etc) to Google's API to be rendered on the client, the JavaScript code transforms the points to the screen projection before being overlaid.
Nice article, I, too, hadn't noticed the change in scale just by panning around.
The Google LatLong blog (http://google-latlong.blogspot.com/) is packed with information related to Google Maps, and the maps API Google Group also is.
There's lots of talk about the Mercator projection on the list, tradeoffs, pros, cons, etc. So there really was no need to read the obfuscated code. Also, I'm not sure if "ease of implementation" was really what had them choose this projection, so it wouldn't hurt to dig around a little bit more before saying stuff like that, I think.
Still, pretty good stuff for people that want to know a bit more about how Google Maps work.
The Google LatLong blog (http://google-latlong.blogspot.com/) is packed with information related to Google Maps, and the maps API Google Group also is.
There's lots of talk about the Mercator projection on the list, tradeoffs, pros, cons, etc. So there really was no need to read the obfuscated code. Also, I'm not sure if "ease of implementation" was really what had them choose this projection, so it wouldn't hurt to dig around a little bit more before saying stuff like that, I think.
Still, pretty good stuff for people that want to know a bit more about how Google Maps work.
Please note that the article is four years old and, as far as I can tell, Maps API has been launched mostly in the same period (wikipedia:Google_Maps).
I don't know how much information was available at that time but it shouldn't be much.
I don't know how much information was available at that time but it shouldn't be much.
Projects such as OpenStreetMap make me wonder: isn't there a community-driven, open-source project that allows to do all this offline? In general, could anyone point me to offline alternatives, where you simply download all the data? In some situations using a static snapshot could prove good enough.
You can download the raw data from OSM easily. Get it here: http://planet.openstreetmap.org/ . However that's a 20GiB compressed XML file in their schema. You could download the data and pre-generate your own tiles and save them, but that would take a lot of space (i.e. Terabytes). You could download the OSM data to your computer and set up mod_tile (the render on demand server) locally and browse your own computer to see the tiles.
If you have a garmin GPS you can download the garmin map files based on OSM for your gps from this site http://download.geofabrik.de/osm/ . You can also get navit files from OSM which works on the open source navit satnav programme. Neither of those are browser based tiles though.
If you have a garmin GPS you can download the garmin map files based on OSM for your gps from this site http://download.geofabrik.de/osm/ . You can also get navit files from OSM which works on the open source navit satnav programme. Neither of those are browser based tiles though.
I guess the Cartographers for Social Equality aren’t too happy with Google Maps :)
http://www.youtube.com/watch?v=n8zBC2dvERM
http://www.youtube.com/watch?v=n8zBC2dvERM
What I like about this is that its a special case of BSP tree projected onto the sphere. If you think of the tiles as projected half-spaces...
In other words if you look through the details of projection and coordinate systems the spacial partitioning scheme used is the familiar BSP tree.
I'm going to remember this the next time someone tries to tell me they can't handle large open areas effectively... "what, you mean like THE WHOLE PLANET!!111 lolz"
:D
In other words if you look through the details of projection and coordinate systems the spacial partitioning scheme used is the familiar BSP tree.
I'm going to remember this the next time someone tries to tell me they can't handle large open areas effectively... "what, you mean like THE WHOLE PLANET!!111 lolz"
:D
I'm not sure I follow you. BSP trees are used for depth-sorting; what's being sorted here?
I had not noticed that the scale bar on Google Maps constantly changes as you scroll around (not just zoom in and out) due to the Mercator projection. Interesting article.
Interesting tidbit: the scale only changes when you go north/south. At the same latitude, the scale will remain the same as you pan east/west.
You can read why that happens in the paragraph titled "Scale".
Here's an excerpt (given that Google tiles are 256x256 and at zoom 0 one tile covers the whole world):
"Intuitively its easy to see why the scale changes. Let's think about Google Maps zoom level 0. At zoom level 0 the world is fit into a 256 pixel wide image. But we know that the earth's circumference is the largest at the equator and dwindles down to zero at the poles. So as you move north or south away from the equator, the Earth has to be "stretched" to fit into the 256 wide bitmap. Thus as you move north or south the scale gets larger and larger because the same number of pixels on the screen are showing you a larger and larger percentage of the Earth's surface."
Here's an excerpt (given that Google tiles are 256x256 and at zoom 0 one tile covers the whole world):
"Intuitively its easy to see why the scale changes. Let's think about Google Maps zoom level 0. At zoom level 0 the world is fit into a 256 pixel wide image. But we know that the earth's circumference is the largest at the equator and dwindles down to zero at the poles. So as you move north or south away from the equator, the Earth has to be "stretched" to fit into the 256 wide bitmap. Thus as you move north or south the scale gets larger and larger because the same number of pixels on the screen are showing you a larger and larger percentage of the Earth's surface."
The Mercator projection is useful to navigators on high seas, but nowadays, that's just irrelevant. De-zoom and look at the size of Groenland or Antarctica to see :)
[deleted]
http://wiki.openstreetmap.org/wiki/Slippy_map_tilenames