Morton codes (or Z-order curves) are a way to hash coordinates in 1 dimension. This is useful for problems such as “which stores are 10 miles away from me?” without searching through all the stores in existence.
Why Not Use A 2d Array?
You might ask, why not just store the information in a 2d array in C or Java? The problem is caching.
y=0 y=1 y=2 y=3 .... y=99
[1,2,3,4...99] [1,2,3,4...99] [1,2,3,4...99] [1,2,3,4...99] ....
How a 99×99 2d array could be stored in memory.
Lets say you try to find some stuff closest to x=5, y=1. The cpu then loads the nearby arrays y=0, y=1 and y=2 for speedy access, because that is how modern cpus work. The problem is when you search for a “close” coordinate such as x=5 y=20, its too far away from x=5 y=1.
To you , it looks like its only 19 units away, but in the computer its 19 x 99 units away because each y-array between y=1 and y=20 has 99 slots.
Generating Morton Codes
Generating a Morton number is easy. All you do is convert the x and y coordinate numbers into binary. Then “interleave” the bits to get the Morton number. It does not matter which goes first, but you must be consistent.
Example
-0-0-1 : 1 in binary
1-0-1- : 5 in binary
xyxyxy
100011 : 35 Your interleaved Morton number
My interleave function for python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def interleave(x, y):
result = 0
position = 0
bit = 1
while bit <= x or bit <= y:
if bit & x:
result |= 1 << (2*position+1)
if bit & y:
result |= 1 << (2*position)
position += 1
bit = 1 << position
return result |
Using Morton Codes
6 |20 22 28 30 52 54 60
5 |17 19 25 27 49 51 57
4 |16 18 24 26 48 50 56
3 |5 7 13 15 37 39 45
2 |4 6 12 14 36 38 44
1 |1 3 9 11 33 35 41
0 |0 2 8 10 32 34 40
--------------------------
0 1 2 3 4 5 6
A table of Morton codes on a 2d graph. The x coordinate is interleaved in front of the Y coordinate.
Now lets say you would like to find all the objects 1 unit away from x=1 y=1. Find the upper bound number by finding the Morton number at x=2 y=2 (12). Then do the same for the lower bound at x=0 y=0 (0). So now you will need to search for any objects from 0 to 12.
This limits the search space. But it is not perfect, so you will have to verify each one manually.
As you can see, the numbers 5, 7, 10, 11 are out of bounds, but are between 0 to 12.
Our 2d Cartesian graph, with the Morton order (Z-curve) in red from lowest to highest. As you can see here, as the Morton number grows, the space covered expands in a zig zag fashion, from the bottom left to right.
You can use Morton codes in higher dimensions as well. For example in 3d, you might interlace coordinates as xyzxyzxyz. Hilbert codes supposedly have better locality, but is harder to compute.
