# 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
interleave l = case l of
[] -> [] -- No lists to interleave
[] :_ -> [] -- We abort as soon as an empty list is spotted
(x:xs):ys -> x : interleave (ys ++ [xs]) -- Extract x, send xs to the end
outerleave :: Int -> Bits -> [Bits]
outerleave n xs = let (heads, xs') = splitAt n xs -- Take one bit for each list
tails = outerleave n xs' -- Recurse to get the rest
lists = zipWith (:) heads tails -- Prepend the heads to their tails
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:

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

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

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

range we're using:

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

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:

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

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

```
rgbCube xs = let [r, g, b] = outerleave 3 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:

```
adjust = let cubeScale = floor $ fromIntegral (scale * 2) / 3
ratio = 2 ^ (scale - cubeScale)
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.