Cantor Tuples

Cantor pairs (and triplets, or tuples in general) are way to enumerate multi-dimensional spaces, similar to the Z curve. Unlike the Z curve, Cantor Tuples don’t preserve locality very well.

The idea is very simple: we trace a curve back and forth across the space until we’ve covered the whole thing. Here are the definitions we’ll be using below:

• type Dimensions = Int
  • How many Dimensions to work in
• type Range = Int
  • A bounded or unbounded Range of coordinates
• range n = if n == 0 then [0..] else [0..n]
  • A way to enumerate a Range
• type Point = [Int]
  • Storing lists of coordinates rather than tuples lets us use any number of Dimensions
• type Curve = [Point]
  • A Curve is a line traced through the space
• data Shape = Shape {sDim :: Dimensions, sRange :: Range, sPred :: Point -> Bool}
  • We define a Shape using a predicate, deciding whether a Point is in the Shape or not

Axis-aligned Curves

The most obvious way to trace a Curve across a Shape is to start at (0, 0) (which for our purposes will be the top left of the images) and increase, say, the x coordinate to get (1, 0), then (2, 0), etc. until we exhaust the Shape’s Range, then jump to (0, 1) and do the same thing, and so on:

aaCurve :: Range -> Dimensions -> Curve
aaCurve r 1 = [[x]  | x <- range r]
aaCurve r n = [x:xs | x <- range r, xs <- aaCurve r (n - 1)]

aaShape :: Shape -> Curve
aaShape (Shape d r p) = filter p (aaCurve r d)

If we use this to trace a black-to-white gradient across a square image, we get this:

A Finite Example

Let’s say we have a circle (where dim = 2 ^ scale = 128 is the width and height of the following images):

pythagoras' :: Int -> Int -> Int
pythagoras' a b = a ^ 2 + b ^ 2  -- There's no need to take the square root

circle :: Shape
circle = let centre = dim `div` 2
             p [x, y] = pythagoras' (x - centre) (y - centre) < (centre ^ 2)
          in Shape 2 (2 * centre) p

Here’s what we get when we use an axis-aligned curve to trace a black-to-white gradient through the circle:

circlePixels = aaPixels circle

drawCircle x y = let this = DM.lookup [x, y] circlePixels
                  in maybe 255 id this

An Unbounded Example

What happens if our Range is unbounded (ie. range 0)? For example, we might define an infinitely-repeating pattern:

checkerboard :: Shape
checkerboard = let f        = (`mod` 2) . (`div` 8)
                   g [x, y] = f x == f y
                in Shape 2 0 g

Obviously we can’t draw the whole pattern, but we can draw a small section:

drawBoard x y = sPred checkerboard [x, y]

Since the area of checkerboard is infinite, so is the length of a Curve traced through it. However, an infinite Curve returned by aaCurve will not contain every Point in the Shape.

This is because we only add a Point from the second row once we’ve reached the end of the first row; since the first row never ends, we’ll never add a Point from any other row!

Diagonal Traces

Cantor’s approach handles infinite patterns like checkerboard by tracing diagonal lines across the shape, from one coordinate axis to another:

• Each Point on the x axis is the start of a diagonal line
• To get from one Point in a line to the next, we decrement the x coordinate and increment the y
  • If we have more dimensions, we fix the first coordinate (ie. x) and recurse using the rest of the dimensions
• Once the x coordinate hits 0, we jump to the start of the next line

cantorMax [_]    = True
cantorMax (x:xs) = sum xs == 0

cantorStart n 1 = [n]
cantorStart n d = 0 : cantorStart n (d-1)

cantorNext :: Point -> Point
cantorNext (x:xs) | cantorMax (x:xs) = xs ++ [1+x]
cantorNext (x:xs) | cantorMax xs     = (x + 1) : cantorStart (sum xs - 1) (length xs)
cantorNext (x:xs) | otherwise        = x : cantorNext xs

-- A full curve
cantorCurve :: Range -> Dimensions -> Curve
cantorCurve r d = takeWhile ((<= 2 * r) . sum) (iterate cantorNext (replicate d 0))

cantorShape :: Shape -> Curve
cantorShape (Shape d r p) = filter p (cantorCurve r d)

To see how this works, we can trace a black-to-white gradient across a square, following the curve given by cantorCurve. Compare it to the axis-aligned version above:

We start in the top left corner and draw a diagonal line from the top edge to the left edge, then draw another next to it, and another next to it, and so on. Note that Cantor’s method naturally draws a triangle; to make it trace a square, we’ve had to filter out those points which extend too far to the right or the bottom.

A Finite Example

Let’s revisit our circle. If we trace a gradient across it using Cantor’s method, we get the following:

Unbounded Example

If we apply this to the checkerboard pattern, we’re now guaranteed to reach any finite coordinate in finite time:

Removing All Bounds

The checkerboard example is unbounded on the right and bottom, but does have a bound on the top and the left. Cantor’s method can exploit this to zig-zag across the pattern, but it doesn’t rely on there being any bounds. Instead of zig-zagging, we can follow a spiral, starting from any point, and be guaranteed to eventually reach all points. For example, if we treat the checkerboard as unbounded in all directions: