# Z Curve

The Z curve is a line which zig-zags through a space, going through all points in a particular order. It’s a nice, quick way to enumerate points in a way which sort-of preserves locality, or ‘closeness’, between points in the space and points on the resulting line. Its locality isn’t as good as the Hilbert curve’s, but the Z curve is embarassingly simple to understand:

Given a point with coordinates `(x, y)`

, we can find out
its position on the Z curve by writing `x`

and `y`

in binary, interleaving their bits, then reading back the resulting
number.

For example, the point `(`

`5`

`,`

`10`

`)`

can be written in binary as `(`

`0101`

`,`

`1010`

`)`

.
If we interleave these, we get `0`

`1`

`1`

`0`

`0`

`1`

`1`

`0`

, which converted to decimal is
`102`

.

To convert back to `(x, y)`

coordinates we just read the
even and odd bits, respectively.

The `interleave`

function will
interleave lists of `Bits`

whilst
the `outerleave`

function will
extract lists of `Bits`

from a
single list:

```
interleave :: [Bits] -> Bits
= case l of
interleave l -> [] -- No lists to interleave
[] :_ -> [] -- We abort as soon as an empty list is spotted
[] :xs):ys -> x : interleave (ys ++ [xs]) -- Extract x, send xs to the end
(x
outerleave :: Int -> Bits -> [Bits]
= let (heads, xs') = splitAt n xs -- Take one bit for each list
outerleave n xs = outerleave n xs' -- Recurse to get the rest
tails = zipWith (:) heads tails -- Prepend the heads to their tails
lists in if length xs < n
then replicate n [] -- Base case
else lists
```

For example, we can colour our Z curve with a black-to-white gradient, then zig-zag it across a 2D space:

`= adjust . fromBits $ interleave [toBits y, toBits x] f x y `

Since the interleaved number has twice as many bits, we must `adjust`

it to fit in the ```
128
```

range we’re using:

`= (`div` (2 ^ scale)) adjust `

This results in the following image:

Notice that the gradient is quite smooth: large discontinuities are rare, common discontinuities are small. That’s because the curve has good locality.

## Higher Dimensions

Since the Z curve works for any number of dimensions, we can zig-zag
it through the 3D RGB colour space, where the `(x, y, z)`

coordinates we interleave correspond to red, green and blue colour
intensities respectively.

Like before, we interleave the `x`

and `y`

coordinates of our pixels to get their position on the Z curve:

`= rgbCube $ interleave [toBits y, toBits x] f x y `

To get our red, green and blue values, we just ‘outerleave’ three numbers from this position:

```
= let [r, g, b] = outerleave 3 xs
rgbCube xs in (adjust r, adjust g, adjust b)
```

Again, we adjust the colours to fit in our range. This time it’s not strictly necessary; since they’re only using 2/3 of the allowed bits, all values will be in range, but they’ll be quite dark so we scale them up:

```
= let cubeScale = floor $ fromIntegral (scale * 2) / 3
adjust = 2 ^ (scale - cubeScale)
ratio in (* ratio) . fromBits
```

This gives us the following 2D embedding of the RGB colour cube:

This isn’t as smooth as the greyscale, since the problem is harder:
we don’t have the luxury of an *extra* dimension, like the
greyscale example. Instead, we have to *remove* a dimension from
the RGB cube. Many discontinuities follow the same pattern as the
greyscale example, eg. the image being split into quadrants. The
tartan-like banding is due to the cube’s neighbours having to rearrange
themselves in the constrained 2D space.