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:

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



Another thing we can do with circle is to approximate pi:

  • pi * r^2 is the area of any circle
    • r = dim `div` 2 in our example
  • sRange s ^ sDim s is the area of the bounding box of s :: Shape
    • sRange circle = dim = 2 * r
    • sDim circle = 2
    • boxArea = (2 * r)^2 = 4 * r^2 for circle
  • circleArea / boxArea = (pi * r^2) / (4 * r^2) = pi / 4 follows from simple algebra
    • Therefore pi = 4 * circleArea / boxArea
  • Since each Point is an uniform distance from its neighbours, counting how many are in a Shape is a measure of the Shape's area
    • aaArea = length . aaShape gives us the area inside a Shape
    • circleArea = fromIntegral $ aaArea circle
    • boxArea = fromIntegral $ aaArea (Shape (sDim circle) (sRange circle) (const True))
  • Plugging these values into our definition of pi gives 3.088516315125293
    • Increasing the radius decreases the error, since the sampling gives a less 'jagged' approximation of our circle

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:

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: