Space-filling curves!

Amazing things.

Peano sat around thinking and thinking, What was he thinking? He was thinking:

I wonder, I wonder, I wonder! Can I draw a continuous line that touches every single point of the unit square, exactly once? (i.e. it never crosses itself!)

Not only did Peano discover that there was a way to do it, he was thrilled to find that the way to do it was called "The Peano curve!" (Mathematics seems to be full of these awesome coincidences)

Peano described this curve in a mathematical paper which did not include any pictures. Think about that for a minute. Let it really sink in.

I'll demonstrate a Peano curve soon, but you might be interested in the famed Hilbert Curve which is fairly similar, published one year after Peano's and achieved greater fame because he was clever enough to include pictures in his paper.

To make the Peano curve look interesting, you need to draw it with rounded corners. Otherwise it just creates a lattice-like grid. So instead of performing a sharp 90 degree lt or rt (left turn or right) I've created function called ilt and irt which perform a bevelled 90 degree turn to the left or right.

to ilt :length
 color [0 125 0]
 lt 45
 fd :length/20
 lt 45
 color [125 0 0]
end
to irt :length
 color [125 125 0]
 rt 45 
 fd :length/20
 rt 45
 color [0 0 125]
end
;...
to peano :length :limit
 ifelse :limit = 0
[ fw :length * 40]
[
;F -> F+F-F-F-F+F+F+F-F
peano :length :limit -1
ilt 90 :length
peano :length :limit -1
irt 90 :length
peano :length :limit -1
irt 90 :length
peano :length :limit -1
irt 90 :length
peano :length :limit -1
ilt 90 :length
peano :length :limit -1
ilt 90 :length
peano :length :limit -1
ilt 90 :length
peano :length :limit -1
irt 90 :length
peano :length :limit -1
]
end
;...
peano 1 1
peano 0.5 1
peano 0.25 2
peano 0.125 3
peano 0.0675 4

'Flipping' to create space-filling curves

Here's an excellent curve I first saw in the book 'Brain Filling Curves'

The 'trick' is that part of the curve is drawn 'flipped'.

Flipped means that instead of just drawing a segment, you instead: pick up the pen, move to the end of the segment, turn around 180 degrees, put the pen down.... then draw the segment, then turn around, pick up the pen, move back to the end of the segment and put the pen back down.

Flipping, it turns out, is very useful in creating space-filling curves!

Here's our basic program, with extra comments around the 'flipping' -- run with a limit of just 2.

to curve :length :limit
    ifelse :limit = 0 
    [ 
        fw :length 
    ]
    [
        lt 90
        curve :length/2 :limit - 1
        rt 45
        ; move to end of line... turn around
        pu fd :length/(2 * sqrt(2)) rt 180 pd
        curve :length/(2 * sqrt(2)) :limit - 1
        ;at start of line... move back to end!
        pu rt 180 fd :length/(2 * sqrt(2)) pd
        rt 45 curve :length/2 :limit - 1
        rt 45 
        ; move to end of line... turn around
        pu fd :length/(2 * sqrt(2)) rt 180 pd
        curve :length/(2 * sqrt(2)) :limit - 1
        ;at start of line... move back to end!
        pu rt 180 fd :length/(2 * sqrt(2)) pd
        rt 45 curve :length/2 :limit - 1
        lt 90
    ]
end
curve 240 2

Now here's the same program with less comments, running this time with limits of 2, then 3, then 4, then 5. For exponentially more space-filling fun.

to curve :length :limit
    ifelse :limit = 0
    [ 
        fw :length 
    ]
    [
        lt 90
        curve :length/2 :limit - 1
        rt 45
        pu fd :length/(2 * sqrt(2)) rt 180 pd
        curve :length/(2 * sqrt(2)) :limit - 1
        pu rt 180 fd :length/(2 * sqrt(2)) pd
        rt 45 curve :length/2 :limit - 1
        rt 45 
        pu fd :length/(2 * sqrt(2)) rt 180 pd
        curve :length/(2 * sqrt(2)) :limit - 1
        pu rt 180 fd :length/(2 * sqrt(2)) pd
        rt 45 curve :length/2 :limit - 1
        lt 90
    ]
end
setxy 50 250
curve 120 2
setxy 350 250
curve 120 3
setxy 650 250
;...
curve 120 4
setxy 950 250
curve 120 5

That flipping technique is not very satisfying, for a couple of reasons. First: the code is ugly. The "pen up, run, spin around, pen down" eventually followed by "pen up spin around, run, pen down" is just confusing.

We could hoist that into its own function, reverse_curve. But it's still awkward.

But worst is that the curve is no longer drawn as a single continuous line.

And the whole idea of space filling curves is that you never lift the pen.

'Flipping' by replacing Left Turns with Right Turns etc.

A better way of "flipping" a section is to reverse all of the angles: replace "right turns" with "left turns" and vice-versa (avv). This only works if the sections being flipped as symmetric length-ways: the first half is a mirror equivalent of the second half.

The easy way to replace "right turns" with "left turns", avv, is to turn right by a negative amount, avv.

Implementing this in the flavor of logo that i'm currently using turned out to be a little tricker than I expected. Trying to multiply by negative 1 is not something that the logo parser was familiar with. The only way I found to reliably create the number "-1" was with the expression "(0-1)". Fair enough.

So in the code below, the term ":angle" is a number that sometimes equals 1 and sometimes equals -1. Thus it can transform left turns into right, avv.

to curve :length :limit :angle
 ifelse :limit = 0
[ 
    fw :length 
]
[
    lt 90*:angle
    curve :length/2 (:limit - 1) :angle
    rt 45*:angle
    curve :length/(2 * sqrt(2)) (:limit - 1) (:angle*(0-1))
    rt 45*:angle curve :length/2 (:limit - 1) :angle
    rt 45 *:angle
    curve :length/(2 * sqrt(2)) (:limit - 1) (:angle*(0-1))
    rt 45*:angle curve :length/2 :limit - 1 :angle
    lt 90*:angle
]
end
;...
curve 240 5 1

This trick does not always work. As I mentioned, this only works if the sections being flipped are symmetric length-ways, that is: if the first half is a mirror equivalent of the second half.

The 'flow snake' is an example of a fractal curve that requires 'flipping' but where the unit-section is not symmetric length-ways.

There is a third technique we can use, which requires more code but does not involve lifting the pen.

'Flipping' by Mutual Recursion.

In this scenario we have two methods (flowsnake and flowsnake_r) which are "mutually recursive" and where one is the "reverse" of the other. (The curve we're drawing this time is the famous flowsnake (or 'Peano-Gosper curve')).

to flowsnake :count :length 
ifelse :count = 0
[
  fd :length
]
[
  flowsnake (:count-1) :length
  lt 60
  flowsnake_r (:count-1) :length
  lt 120
  flowsnake_r (:count-1) :length
  rt 60
  flowsnake (:count-1) :length
  rt 120
  flowsnake (:count-1) :length
  flowsnake (:count-1) :length
  rt 60
  flowsnake_r (:count-1) :length
  lt 60
]
end
;...
to flowsnake_r :count :length 
ifelse :count = 0
[
  fd :length
]
[
  rt 60
  flowsnake (:count-1) :length
  lt 60
  flowsnake_r (:count-1) :length
  flowsnake_r (:count-1) :length
  lt 120
  flowsnake_r (:count-1) :length
  lt 60
  flowsnake (:count-1) :length
  rt 120
  flowsnake (:count-1) :length
  rt 60
  flowsnake_r (:count-1) :length]
end
;...
flowsnake 4 10

It would be good if, instead of meticulously composing the second method to be a reverse of the first method, we could simply wrap the first function in a special 'reverse' function. It would reverse the sequence of instructions. And if they are function calls, it would wrap them in 'reverse' functions. And if they are atomic methods (such as 'left turn') it would replace them with their reversed function (e.g. convert left turns into right turns). And if they are already reversed, it would unreverse them!

At this point we're starting to wish for "meta-programming" features: instructions that act on instructions themselves, rather than just on data.

I'm sure it can be done, but I don't know enough logo to know quite how. Do you?

External Links

• Brain Filling Curves

See Also

• Hilbert Curve
• Flowsnake
• Dragon Curve
• Conga Line Mathematics