*What Links Here?*

*Outbound Links*

# Space Filling Curves

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?