Cracking the Code: How QuadKeys Divide and Conquer the World Map | tb.lx Knowledge Pills
Every month we will give you a shot of knowledge about various topics, including technology, electric vehicles, engineering, business and even design. We’ve got all types of expertise in our team, and we want to share it with the world. And don’t worry, the doctors approved it, and it’s clinically proven to open your brain’s doors to amazing knowledge.
tb.lx is on its way to support Daimler Truck to revolutionize the transportation industry. For that, we need connected vehicles and services that give users — from drivers to fleet managers and dispatchers — access to live data on their trucks’ locations, allowing them to make more efficient, sustainable and cost-effective decisions. And that’s when maps come into play, being such an essential part of the software products we develop.
But, what’s the science behind maps, something everyone can access nowadays, only a click away from their phones or computers? It all starts with geospatial data,
Geospatial data usually are plentiful, whether we consider road networks, trajectory databases, or geosciences. There is always too much data, so we must use clever indexing techniques to get the information we want. To make matters a bit worse, geospatial data refers to the Earth’s surface, which usually is approximated by a sphere. Traditionally, we have mapped this sphere using spherical coordinates with a fixed radius. This scheme reduces the required number of coordinates from three to two, retaining the angles only (Latitude and Longitude). The center for this coordinate system lies where the equator intersects the Greenwich meridian in the Gulf of Guinea. Latitude measures the angle from the equator, with positive values to the North and negative values to the South. Longitude measures positive angles to the right of the Greenwich meridian and negative angles to the left of it.
We can project the Latitude and Longitude coordinates into a cartesian plane with the Longitude running along the “x” axis and the Latitude running along the “y” axis. Unfortunately, this will give the false impression of an isometric space, which is far from the truth. The Mercator projection of spherical coordinates into a plane, probably the most commonly used, causes distortions that increase towards the poles. Using this nifty online map, you can see how much the regular maps have deceived you. It is fascinating to see the actual size of Greenland when you drag its shape close to the equator.
These concepts work behind the scenes when you use an online map (a “slippy map”). Have you ever wondered how these online maps work? The most common and classic construction relies on a patchwork of square map tiles patched together to give the illusion of a continuous surface, an infinite bitmap. To display the map at a specific location and magnification (the zoom level), the underlying code must know how to retrieve the required tiles, and this is where things become interesting. For a given view of the world centered at a specified location and with a specified level of detail, what is the required set of tiles to retrieve, and how graphically organize them? The designers of these systems developed a very clever geospatial indexing system that we can use for purposes other than displaying slippy maps. Let’s see how this system works.
The picture above shows the second detail level of the quadkey hierarchy, along with the respective tile encoding. The Earth’s surface (except for a small band near the poles) maps to a single square using the Mercator projection. The top-level tile splits into four equal-sized tiles, receiving an encoding as depicted above. Each tile recursively splits into other four tiles, repeating the same encoding type but keeping the parent’s encoding first. The picture below illustrates this.
When the zoom level increases, each tile splits into four, and the encoding follows the same pattern. This encoding scheme shows the zoom level as the number of digits in the code, which is quite convenient. Another convenience of this encoding scheme is that we can easily convert it into an integer by realizing that each digit maps into two bits, much like a base-4 number. The advantage of using an integer encoding versus a string encoding is the space it occupies in memory or a database. With some minor tweaks, we can encode all quadkey codes into a sixty-four-bit integer which is excellent compaction.
On the other hand, we can also encode these tiles using their cartesian coordinates within the larger grid, as shown in the picture below at zoom level three.
Fortunately, it is pretty easy to transform quadkey tile codes into cartesian coordinates and vice-versa, so we can always have a dual view of these. The exciting perspective on this approach is that we can consider the Earth’s surface as a vast bitmap whose coordinate limits depend on the zoom level in use. For the mathematically inclined, the coordinate system divides into 2z partitions on each axis (z is the zero-based zoom level) for each zoom level. The picture above illustrates zoom level three, containing eight divisions per axis. Why is a bitmap such a cool thing? We can draw lines and polygons using a discrete cartesian coordinate system, where lines model road segments and polygons model geofences. For these use cases, testing the whereabouts of an arbitrary location is a simple process of converting it to the corresponding quadkey tile and searching the database for a match, all done with integers.
At these magnification levels, quadkeys may not be helpful for geospatial indexing. But, the situation improves significantly as we increase the detail level. For instance, at zoom level 22, a quadkey tile measures 9.55 meters on each side at the equator. Suppose you want to use quadkeys to encode an area of interest, like a car park or a fuel station. By knowing the location’s boundary geometry, you can discretize it down to these small square tiles and save the set of codes to a database. There will always be some errors when discretizing. Like in digital photography, everything boils down to small square pixels, but you can still discern plenty of detail.
Notwithstanding, as long as the square tiles fully cover the area of interest, you will be safe. Now that we have a set of quadkey codes that discretize our arbitrary geographic area, testing for inclusion, like when a car enters the fuel station, is just a matter of converting its location to the corresponding quadkey code and checking if that code belongs to the shape. This process’s simplicity amounts to transforming a place expressed as a Latitude and Longitude pair to a quadkey code and then running a high-speed set inclusion test. There is no need for specialized geospatial data storage and indexing, and a simple database index will do the trick.
This article introduced the concept of quadkeys as mathematical tools to partition the world map into a grid of arbitrarily small squares in Latitude and Longitude space. By uniquely identifying each of these square tiles with a sixty-four-bit integer, we can leverage straightforward indexing and search schemes to perform robust geospatial analysis or moving object tracking. If this subject piqued your interest, please see the references section below for more material on quadkeys.
References
Bing Maps Tile System — Bing Maps | Microsoft Learn
muety/pyquadkey2: 🌐 Python implementation of geographical tiling using QuadKeys (github.com)
Guide — HERE Traffic API — HERE Developer
Geospatial Indexing with Quadkeys | by João Paulo Figueira | Towards Data Science
Travel Time Estimation Using Quadkeys | by João Paulo Figueira | Towards Data Science
This article was written by João Paulo Figueira, Data Scientist at tb.lx, based in Lisbon, Portugal. 🚛🌿.
