Today I Learned

Some of the things I've learned every day since Oct 10, 2016

121: Another Description of Z Order

Another clear description of Z Order, equivalent to the binary description, comes from depth-first traversal of a quadtree.

Say we have a 2-dimensional square with a grid of $4^k$ points on it, and that we organize these points into a complete quadtree of depth $k$. To do this, we start with the complete square as the root of the tree, then assign the 4 subsquares to the 4 child nodes of the root as upper-left $\rightarrow$ child 1, upper-right $\rightarrow$ child 2, lower-left $\rightarrow$ child 3, lower-right $\rightarrow$ child 4. For each subsquare we do this recursively, until we arrive at the smallest subsquares which will become leaf nodes. Then the Z order of the points on the square will just be the order that their associated nodes are visited by depth-first traversal of this quadtree.