Hilbert Curve vs Morton Order in Binary Systems

Space-filling curves map multidimensional data into a one-dimensional sequence, serving as a cornerstone for spatial indexing, image processing, and database architectures. While both the Hilbert curve and Morton ordering (Z-order curve) project higher-dimensional coordinates into a single binary index, they differ significantly in their mathematical construction, computational complexity, and spatial locality preservation. This article explains how the Hilbert curve operates and compares its spatial clustering performance against Morton ordering in binary systems.

What is a Hilbert Curve?

A Hilbert curve is a continuous, fractal space-filling curve that passes through every point in an \(N\)-dimensional grid of size \(2^k \times 2^k \dots \times 2^k\). Introduced by David Hilbert, this curve is constructed recursively by rotating and reflecting smaller sub-units of the curve as grid resolution increases.

When mapping a multi-dimensional coordinate \((x, y)\) to a single one-dimensional scalar index \(h\), the Hilbert curve ensures that the traversal moves continuously from one neighboring cell to an adjacent cell without diagonal cuts or sudden jumps.

What is Morton Ordering (Z-Order)?

Morton ordering, or Z-order, is a space-filling curve constructed through bit-interleaving. To calculate the 1D Morton code \(z\) for a coordinate pair \((x, y)\), the binary representations of \(x\) and \(y\) are interleaved bit by bit.

For example, given binary coordinates \(x = x_2x_1x_0\) and \(y = y_2y_1y_0\), the resulting Morton code is:

\[z = y_2x_2y_1x_1y_0x_0\]

This interleaving creates a repeating “Z” pattern across quadrants at every recursive subdivision level.

Locality-Preserving Mapping: Hilbert vs. Morton

Locality preservation measures how well a 1D mapping keeps points that are close in multi-dimensional space close to each other on the 1D line.

Discontinuities and Spatial Jumps

• Morton Ordering: The primary drawback of Morton ordering is the presence of major spatial discontinuities. When the curve finishes traversing one sub-quadrant, it must jump across the space to begin the next “Z” stroke. This creates large numerical gaps between points that are physically adjacent across partition boundaries.
• Hilbert Curve: The Hilbert curve avoids these large jumps by altering the orientation of the curve at each recursive step. Because adjacent cells in the 1D sequence always share an edge in the multi-dimensional grid, the Hilbert curve exhibits superior locality preservation and minimizes the maximum distance between spatially adjacent cells.

Bounding Box and Range Query Efficiency

In spatial databases and bounding volume hierarchies (BVHs), contiguous 1D index ranges are retrieved to query multidimensional areas: * Hilbert index ranges generally correspond to compact, contiguous spatial clusters, leading to fewer distinct range queries and fewer false-positive disk or cache reads. * Morton index ranges often fragment a compact spatial region into multiple disconnected 1D segments due to quadrant boundary jumps, requiring more sub-queries to scan the same spatial region.

Binary Computation and Performance Trade-offs

Morton ordering is computationally cheap because standard CPU instructions (such as BMI2 PEXT and PDEP) can compute Z-order values in a few clock cycles. In contrast, calculating a Hilbert index requires Gray code transformations, parity checks, and bit rotations to handle the changing orientations of sub-quadrants.

Summary

The choice between a Hilbert curve and Morton ordering represents a fundamental trade-off between computational cost and spatial locality. Morton ordering is preferred when fast coordinate-to-index encoding and decoding are the main bottlenecks. The Hilbert curve is preferred when optimizing spatial clustering, minimizing cache misses, and reducing I/O operations in high-dimensional spatial indexing.