120: Z Order
July 22, 2017
Posted by on
Z order is a map between 1-dimensional and n-dimensional space which does a decent job of preserving locality (“closeness” between points).
The calculation of Z order from 1 to 2 dimensions is extremely straightforward. Select points from a 1-dimensional interval, and index them according to order in the obvious way using binary. If working with 64 points for instance, with , they’d be labeled 000000, 000001, 000010, …, 111110, 111111. Then recursively split your 2-dimensional square into subsquares times. Again with , you’d have 64 subsquares.
Now given a binary index for a point, read 2 digits at a time, from left to right. If the two digits read are 00, direct the point into the upper-left quadrant. If 01, upper-right. If 10, lower-left. If 11, lower-right. Go on reading the index 2 digits at a time, recursively directing the point into subsquares until you reach the end of the index, and then that subsquare is where the point goes.
A picture, to make this more clear (courtesy of David Eppstein):
I recommend ignoring the stuff in the margins; just look at the labels for points and where they end up.
Here’s what the result of this map looks like for :
The inverse map from 2D to 1D is obvious.