Fractals You Can Draw (The Hilbert Curve or What The Labyrinth Really Looked Like)

Our last fractal of the week is the Hilbert Curve, a variation of the Peano curve first described in 1891. While this is our oldest fractal of the week, its uses and derivation have implications in modern technology and modeling.

Drawing the Hilbert curve is best learned by seeing the various stages:

Initial Stage:

This is the start of our Hilbert curve or its Axiom (a term we’ll come back to late). The second stage is as follows:

Stage 2:

Each stage of the Hilbert curve is a construction of three rotations:

1) Make a mirror image of our initial stage to the right of our first stage (there’s a gap between each new section which we’ll get to in a moment).

2) Make a copy of our left object and rotate it counter-clockwise 90 degrees.

3) Make a copy of our right object and rotate it clockwise 90 degrees.

You now have four u shapes with a gap between them equal to the length of one of their line segments. Rather than leaving these objects separate, we connect the four shapes with three new lines.

This is repeated for each stage:

Stage 3:

As you can see Stage 3 contains 4 copies of Stage 2.

Stage 4:

Stage 4 contains 4 copies of Stage 3.

Here’s a drawing of Stage 5:

Hilbert Curve (Hand-Drawn)

Hilbert Curve (Hand-Drawn)

The easiest way to draw the Hilbert curve is to keep a copy of the previous stage on another sheet of paper.

The Hilbert Curve has a Fractal dimension of 2 like the Dragon Curve and has some interesting properties. At Stage 6 (below), the curve is constructed of 4095 segments of equal length contained in an area 128 lengths by 128 lengths. This means that the length of the curve is 32 times greater than one side of the square containing it.

This kind of compression is practical in antennae construction. The longer the antennae the weaker the signal you can pick up. Curves like the Hilbert curve allow for lines of incredibly long length to be confined in a small area.

Going Deeper (L-Systems):

I have a confession to make. There’s an easier way to construct the Hilbert curve (with the aid of computers) using a technique called Lindennmayer Systems (L-Systems for short). L-Systems are an algorithmic way of describing the formation of an object, and is used in plant modeling, as well as being able to make all of the fractals we’ve drawn this week.

There are three parts to an L-System, the axiom, the instructions, and the translation rules.

The axiom is a string of characters that describe the initial state of the fractal. For the Hilbert curve the axiom is the following:

Axiom: A

For each L-System there are a set of characters that provide drawing instructions. Typically ‘F’ means draw a line forward, ‘+’ means rotate left and ‘-‘ means rotate right. There are other characters that make up the Axiom and the rules that dictate the growth of the shape, but are disregarded once drawing begins.

To draw the Hilbert curve there are two rules:

A → – B F + A F A + F B –

B → + A F – B F B – F A + 

In this case we rotate 90 degrees with every turn. To use an L-System start with the axiom and apply any rules that apply. In this case we get:

– B F + A F A + F B –

If we stop here and remove all characters that are not instructions we get the following:

-F+F+F-

Which draws our initial stage:

If however we apply the translation rules one more time, the resulting string is:

+ A F – B F B – F A + F + – B F + A F A + F B – F – B F + A F A + F B – + F + A F – B F B – F A + –

If we again strip all non-instructions we get:

-+F-F-F+F+-F+F+F-F-F+F+F-+F+F-F-F+-

Which draws our second stage.

Let’s try another one for the Sierpinski Triangle:

Axiom: A

A → B−A−B

B → A+B+A

In this case we rotate 60 degrees with every turn, and A and B are both used to mean draw a line forward. Here’s what we get after 2,4,6 and 8 stages:

Koch Curve L-System:

Axiom : F++F++F

F → F−F++F−F

Use 60 degree turns. Result after 4 iterations:

Dragon Curve L-System:

Axiom: FX

X → X+YF

Y → FX-Y

Use 90 degree turns. Result after 10 iterations.

Other L-Systems:

Quadratic Fractal:

Axiom: F+F+F+F

F→ F+F-F

Use 90 degree turns. Result after 4 iterations.

Koch Curve Variant:

Axiom = F

F → F+F−F−F+F

Use 90 degree turns, result after 6 iterations:

Fractal Plant:

Axiom: X

X → F-[[X]+X]+F[+FX]-X

F → FF

Use 25 degree turns. When you encounter a ‘[‘ save the current angle and position and restore when you see ‘]’. This is an example of a recursive L-System. Result after 5 iterations:

All of the above images were generated using C++ code, rendered to SVG then converted to PNG. There are more L-Systems than I can list here, but all follow the same basic construction rules.

*Whew!* Lot to cover today, but hope it was fun. Feel free to leave any questions in the comments section. Tomorrow we’ll take a look at some non-conventional fractal construction methods.

Want some fractals you can color? You might like my new Adult Coloring Book: Fractals.

Advertisements

11 Comments

Filed under Uncategorized

11 responses to “Fractals You Can Draw (The Hilbert Curve or What The Labyrinth Really Looked Like)

  1. I love the fractal plant. Really remarkable how much it looks like an actual branch. Just goes to show how fractally nature is.

    By the way, I stumbled across yet another method for generating the Sierpinski Triangle:
    http://en.wikipedia.org/wiki/Rule_90#Sierpi.C5.84ski_triangle

    • Haven’t tried that particular method, I’ll have to give it a go. It seems the Sierpinski triangle is a little like Pi, it crops up in unexpected places.

  2. Great stuff! Your write-up helped me solve a problem I had in implementing the production rules for this in a recursive function in Python (using the turtle package). Thanks.

  3. Pingback: DTD: Signs of hope, New Challenges and Random Fun | Ben Trube

  4. Pingback: Bonus Friday Post (Fractal Friday #4) | Ben Trube

  5. Pingback: Fractal Friday (Or Sierpinski Saturday) | [BTW] : Ben Trube, Writer

  6. claire

    your website is awesome! Im in eight grade and we just learned fractals and we want to paint fractals around the school. Im definitely going to show your website to my teacher!

    • I apologize for the lateness of my reply. Thank you so much for your comments, I really appreciate it. I’m glad that you’re learning fractals in school. I’d love to see pictures of where they were painted 🙂 If you’d like, I can send you a copy of my fractal eBook. It’s a little heavy on the programming, but you might like it 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s