Understanding Z-order Curves and Morton Coding for Multidimensional Data
In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space-filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. This means that two points close together in multidimensions with high probability lie also close together in Morton order.
Historical Background
The concept is named in France after Henri Lebesgue, who studied it in 1904, and named in the United States after Guy Macdonald Morton, who first applied the order to file sequencing in 1966. Later, the BIGMIN problem related to these curves was first stated and its solution shown by Tropf and Herzog in 1981.
Mechanism of Z-Value Calculation
The z-value of a point in multidimensions is simply calculated by bit interleaving the binary representations of its coordinate values. Interleaving the binary coordinate values (starting to the right with the x-bit and alternating to the left with the y-bit) yields the binary z-values. Connecting the z-values in their numerical order produces the recursively Z-shaped curve. Two-dimensional Z-values are also known as quadkey values.
For example, the following table illustrates how binary coordinate values are interleaved to form a Z-value:
| X Coordinate (Binary) | Y Coordinate (Binary) | Interleaved Z-Value (Binary) | Decimal Z-Value |
|---|---|---|---|
| 00 (0) | 00 (0) | 0000 | 0 |
| 01 (1) | 00 (0) | 0001 | 1 |
| 00 (0) | 01 (1) | 0010 | 2 |
| 01 (1) | 01 (1) | 0011 | 3 |
Use with One-Dimensional Data Structures for Range Searching
Once the data are sorted by bit interleaving, any one-dimensional data structure can be used to manage the information. These include:
- Simple one dimensional arrays
- Binary search trees
- B-trees
- Skip lists
- Hash tables (with low significant bits truncated)
However, when querying a multidimensional search range in these data, using binary search is not really efficient. It is necessary for calculating, from a point encountered in the data structure, the next possible Z-value which is in the multidimensional search range, called BIGMIN.
Efficiently Building Quadtrees and Octrees
The Z-ordering can be used to efficiently build a quadtree (2D) or octree (3D) for a set of points. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree or octree. The basic idea is to sort the input set according to Z-order. Once sorted, the points can either be stored in a binary search tree and used directly, which is called a linear quadtree, or they can be used to build a pointer based quadtree.
The interleaving of bits from the x and y components of each point is called the shuffle of x and y, and can be extended to higher dimensions. This property can be used to offset a Z-value using bitwise operations to find neighboring coordinates such as top, bottom, left, and right from the current Z-value.
