The L64 Coordinate System

One day browsing the internet I stumbled upon what3words, a website promising to simplify the way we use coordinates. Instead of using two numbers for latitude and longitude they use 3 words. They do this by using a grid of 57 trillion 3x3m squares and an proprietary algorithm to map every square to a unique 3 word address.

As much as I like the vision of making coordinates easier to handle, I have a few issues with it:

1. Their convert algorithm is proprietary
2. It has a fixed resolution of 3 meters
3. In order to convert coordinates you need an arbitrary wordlist of at least 40 000 words
4. They patented the idea of converting coordinates into words

So I decided to invent my own coordinate system that simplifies coordinates into a single string. However, instead of using 3 random words I wanted my system to be logical and also easy to implement. Also I wanted a system where your coordinates could be as accurate as you want. A system like decimal numbers came to my mind, where adding a digit at the end improves the accuracy of the number.¹

As I want my coordinates to be a string that is easy to handle nevertheless compact in information I decided to use Base64. (Actually base64url for easier handling.) In order to use a Base64 string as a location I use an 8x8 grid on top of a map in equirectangular projection (because it is the easiest projection to use with latitude/longitude coordinates). Every cell in the grid corresponds to a single Base64 character.

The L64 grid on a world map. (Source for the map: Wikimedia)

This is the first letter of the L64 coordinate. With a single letter you can give a very broad location. It might not be useful for the most things, but the first letter can distinguish between East Coast (m) and West Coast (j) or Mediterranean regions (y) and northern Europe (4).

In order to get more accuracy we scale the grid down by a factor of 8 and put it in one of the cells of the first level grid. This second level grid tells us the second letter of the L64 coordinate.

If we repeat this scaling and inserting of the grid we can construct a L64 coordinate with as much precision as we need. However only 8 characters are needed to get an accuracy of about 2m. With only 2 characters more the accuracy in the order of centimetres.

You see that this system is relatively simple. Implementing it is even easier, because of the used order of the letters. There are actually two different convert algorithms:

Converting via quadkeys

This is the algorithm I implemented first. It uses quadkeys to convert a location. Quadkeys are a base 4 number that corresponds to a square on the map. They work by dividing the map into four quarters, numbering them from 0 to 3. The dividing is repeated until the level of detail required.

How quadkeys work. (Source: MSDN)

It is important to note that the Bing Maps quadkey uses the Mercator projection, whereas L64 uses the equirectangular projection. The specific projection used in L64 also has the (0, 0) coordinate at the bottom left, instead of the top left.

Therefore the used numbering of the quadkeys is \(\begin{matrix} 2&3 \\ 0&1 \end{matrix}\) instead of \(\begin{matrix} 0&1 \\ 2&3 \end{matrix}\).

The L64 convert algorithm functions the following way:

1. Convert the coordinates into a quadkey with as much accuracy as you want. Mind the projection!
2. Trim the quadkey to a length of \(3x\), where \(x\) is the wished length of the L64 coordinate.
3. Convert the base 4 quadkey to Base64 using basic math. The beauty of this is the fact that \(4^3=64\) which means that 3 characters in a quadkey correspond to a single base 64 character.

That’s it. This is all the conversion algorithm. Converting a L64 coordinate back is as easy as reversing the upper algorithm. The only thing to note is that a quadkey resolves to an area and not a single point. Therefore you might have to calculate the centre of the quadkey square.

Converting via binary fractions

After thinking about my implemented algorithm a bit I realized it could be simplified. If you look at a quadkey (or a L64 coordinate, as they are the same thing in different bases) in binary it has an interesting property. The first digit indicates if you are in the northern or southern hemisphere. The second digit reveals if you are east or west of greenwich. The third digit specifies the north-south position established in the first digit further. And so on and so forth.

So this is the simplified algorithm after that realization:

1. Project the latitude and longitude to numbers between 0 and 1 according to the right projection.
2. Convert the numbers to binary fractions
3. Drop the 0. at the beginning
4. Interlink those numbers by alternating their digits starting with the latitude so that abc and xyz would become axbycz.
5. Trim the result to a length of \(6x\), where \(x\) is the desired length of the L64 coordinate.
6. Convert the resulting binary number to Base64. While doing that 6 binary digits correspond to a single Base64 char. (\(2^6=64\))

The reverse is also as simple as doing every step backwards.

While this algorithm has more steps than the previous one it is still simpler. This is so because most of the complexity of the first algorithm is hidden inside the first step: Calculating the quadkey

With the second algorithm it is as easy as looking at a binary representation of the coordinates and combining them by alternating.

This makes L64 coordinates especially useful on machines with limited power like a microprocessor that is connected to a GPS module. L64 could for example be used to transmit coordinates from a GPS tracker via GSM or an other type of radio with limited bandwidth. And if human readability is not required L64 coordinates can be sent directly as binary, allowing them to be as compact as coordinates can ever be.

You can play with an implementation of L64 with the Google Maps API here.

1. I later learned of Open Location Code’s plus codes which are probably easier to use for end-users and better thought out than my system. However L64 has a higher information density and a simpler convert algorithm. ↩