Z-order curve

A Z-order curve (also called the Morton order or Morton curve) is a space-filling curve that maps multi-dimensional coordinates to a one-dimensional index by interleaving the bits of each coordinate. The Z-order index of a point is formed by interleaving the binary representations of its coordinates, producing a single integer that preserves some spatial locality.

The Z-order curve is less locality-preserving than the Hilbert curve but computationally cheaper, requiring only bit manipulation rather than the recursive geometric construction of the Hilbert curve. This tradeoff makes it the preferred index in many spatial database and geographic information system implementations, where the cost of computing the curve must be weighed against the benefit of better spatial clustering.

The curve is named for its Z-shaped pattern at each level of recursion: each quadrant is visited in a Z pattern, and the overall curve is the recursive refinement of that pattern. It is used in quadtree-based spatial indexing, N-body simulation load balancing, and GPU texture memory layouts.