## Motivation

We are strong believers in the benefits of Free Software. Unfortunately, the What3Words company does not publish open-source code to implement the geocoding. It is quite obvious that if What3Words is to be adopted as the piece of public infrastructure that the What3Words company try to present it as, that it must be available freely for all to use.

For open-source projects to benefit from the What3Words geocoding, we needed an open-source library to implement the geocoding. For this reason we took it upon ourselves to create WhatFreeWords, the open-source geocoding library for What3Words.

## Contributing

If you want to contribute to the development of WhatFreeWords by reporting bugs, porting it to a new language, or so on, please contact us and we will help you.

## Encoding scheme

A lat,lon coordinate is converted into 3 words through a 5 step process.

1. Convert lat,lon to (X,Y) of the 1/24° cell, and (x,y) of the approximately 3m * 3m grid square within that cell.
2. Convert (X,Y,x,y) to a value n representing the location of the grid square.
3. Convert n to a different value m by randomly permuting the n values within large blocks of possible values.
4. Convert m to 3 numeric values i,j,k.
5. Convert each of the numbers i,j,k to a word by looking up in a word list.

### 1. Convert lat,lon to X,Y,x,y

The Earth is divided up into 37,324,800 cells made up of 4,320 Y coordinates and 8,640 X coordinates. Each cell is divided into 1546 y coordinates and a number of x coordinates varying from 1 to 1546 depending on the latitude. Map from lat,lon to X,Y,x,y like this:

X = floor((lon+180) * 24)
Y = floor((lat+90) * 24)
x = floor(W(Y) * frac((lon+180) * 24))
y = floor(1546 * frac((lat+90) * 24))

W(Y) is a function that tells how many horizontal grid squares there are within a single cell at a given Y coordinate. This is because more squares are needed at the equator than at the poles.

W(Y) = max(1, floor(1546 * sin(deg2rad((Y+0.5) / 24))))

(lat,lon)=(37.234328,-115.806657) becomes (X,Y,x,y)=(1540,3053,787,964).

### 2. Convert X,Y,x,y to n

Each cell (X,Y) has a value q which sets the range for the n values. For example the cell (1540,3053) has n values which start at 982,480,441,370. This means for the cell (1540,3035), q=982480441370.

An efficient data structure is used to find the q values. The 4320*8640 map is divided up into regions of areas that are associated together. The q values within each region are automatically calculated based on making consecutive n values. For (1540,3053), W(3053) = 1230, so there are 1243 * 1564 = 1901580 grid squares in the cell, which means the next q value up = 982480441370 + 1901580, and so on.

The regions are grouped by Y coordinate and then sorted by X coordinate, and the q value is found by binary searching within the regions for the given Y coordinate.

Once the q value is found, simply calculate n like this:

n = q + 1546 * x + y

The reason that regions are grouped like this is so that locations on Earth with higher population density can be assigned lower n values, which result in shorter words at the final step, and locations on Earth with less people can be assigned higher n values, which result in longer words at the final step.

(X,Y,x,y)=(1540,3053,787,964) becomes n=982481659036.

### 3. Convert n to m

The n values are not converted directly to words because this would result in locations that are close together being assigned What3Words addresses that are also close together, for example differing by only 1 word. The step that converts n to m scrambles the values in a reversible way such that low values of n get low values of m, but close values of n do not remain close when converted to m.

The range of possible numbers is split into 16 different blocks. The first block is for numbers from 0 to 25003-1. The next block is for numbers from 25003 to 50003-1, and so on.

Locating the block that the n value is in tells the block start value, block size, and multiplication factor. The n value is then converted to m by subtracting the block start value, multiplying by the factor, taking the result mod block size, and then adding back the block start value. The multiplication results in very large numbers so this step requires use of bigint libraries.

m = blockstart + ((n - blockstart) * F_i) % blocksize

F_i is the multiplication factor for block i in the Forward direction. There is additionally a factor R_i which accomplishes the same computation but in the Reverse direction. R_i is the multiplicative inverse of F_i mod blocksize.

n=982481659036 is in the block from 75003 to 100003-1. The block starts at 421,875,000,000, the size is 578,125,000,000, and F_i is 525,026,181,441.

n=982481659036 becomes m=474008150876.

### 4. Convert m to i,j,k

This is achieved by breaking the value m down into the integer part of its cube root and 2 other values such that the 3 values can be recombined later to find m.

l = floor(cuberoot(m))
if l3 <= m < l3 + l2 + 2l + 1:
r = m - l3, i = l, j = floor(r / (l+1)), k = r % (l+1)
else if l3 + l2 + 2l + 1 <= m < l3 + 2l2 + 3l + 1:
r = m - (l3 + l2 + 2l + 1), i = floor(r / (l+1)), j = l, k = r % (l+1)
else:
r = m - (l3 + 2l2 + 3l + 1), i = floor(r / l), j = r % l, k = l

m=474008150876 becomes (i,j,k)=(7797,448,6799).

### 5. Convert i,j,k to words

There is a list of 40,000 words. For each value i,j,k, just lookup the ith, jth, or kth word in the list and then join the three together with dots.

(i,j,k)=(7797,448,6799) becomes words=joyful.nail.harmonica.

To convert back from words to latitude and longitude, the entire process is reversed.