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:
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:
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:
As you can see Stage 3 contains 4 copies of Stage 2.
Stage 4 contains 4 copies of Stage 3.
Here’s a drawing of Stage 5:
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:
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:
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:
Which draws our second stage.
Let’s try another one for the Sierpinski Triangle:
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:
X → X+YF
Y → FX-Y
Use 90 degree turns. Result after 10 iterations.
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:
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.
11 responses to “Fractals You Can Draw (The Hilbert Curve or What The Labyrinth Really Looked Like)”
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:
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.
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.
You’re welcome! We feature fractals from time to time on the blog and I’m glad this post helped. There might be something you’ll also find useful coming out in a couple of months 😉
Just in case you are interested, you can see my results on here: http://lustrebox.wordpress.com/
Nice! Can you send me the L-Systems or basic algorithms on the middle two (the hex flake and diamond carpet looking things)? I’m not sure I have those 🙂
Pingback: DTD: Signs of hope, New Challenges and Random Fun | Ben Trube
Pingback: Bonus Friday Post (Fractal Friday #4) | Ben Trube
Pingback: Fractal Friday (Or Sierpinski Saturday) | [BTW] : Ben Trube, Writer
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 🙂