The Dragon Curve is a famous fractal. I first saw it on the cover of a (French) book I was reading as a teenager. I then started to draw beautiful dragons, my hand. Later, I decided to write a program to draw the curve. The program was written in Pascal. It worked and drew nice dragons. Unfortunately, I’ve lost the source code for it. I would be curious to look at it today, because the program did not use recursion! I know that for sure because recursion didn’t make any sense to me at that time. (The Towers of Hanoi was the real eye-opener for me, but it came later.) I vaguely remember that the program was doing repeated iterations over a large array, but I don’t remember the details. It must have been an ugly piece of code…
Years later, I found on the web a PostScript program that could draw the Dragon Curve. It intrigued me enough to actually make me learn PostScript just to understand the program. I had then some fun with PostScript and prime numbers.
But I couldn’t understand the algorithm used in the PostScript program. It seemed to rely on two mutually-recursive functions and rotations of 45 degrees (even though all angles in a Dragon Curve are right angles). Once you clean up the code (which was pretty terrible, with global variables shared between recursive calls), it seemed to boil down to this:
X -> -FX++FY- Y -> +FX--FY+ F ->
where a form or “turtle graphics” is used and
- represents a clockwise 45 degrees rotation,
+ is an anticlockwise 45 degrees rotation and
F draws a line forward.
I thought this algorithm was remarkable, certainly too good to have been invented by a guy who uses global variables between mutually recursive functions. After searching for more Dragon Curve programs on the web, I found somewhere that exact formulation. It was part of a list of Lindenmayer systems (L-systems) that drew everything from classic fractals (Hilbert, Koch) to various plant-like pictures.
L-systems were invented by Aristid Lindenmayer, a Swedish biologist who used them to model the growth of plants and end up publishing about them in both biology and computer science journals. L-systems have been extended to 3D and widely used in plant biology and computer graphics. The reference book seems to be The Algorithmic Beauty of Plants, by Przemyslaw Prusinkiewicz and Aristid Lindenmayer. Although all the equations that are used in this page were found on the web, I strongly suspect they originated from this book. (All I can say is that they are definitely not mine.)
Using the set of rewriting rules above (starting from
X) and applying them iteratively, here is what you get (read a curve from left to right, starting horizontally):
If you “round the corners”, you better see how the curve is drawn. Here it is, at order 7:
If it still looks more like a French poodle than a dragon to you, it’s because you have no imagination.
Now, here’s the PostScript program that does the job.
First, tell the printer it’s a PostScript file:
Then, specify the order (number of iterations). Beyond 20, it may take forever to draw and print, of course:
Here is the core of the computation, functions
Y. The order value (or depth) in on the stack and is decreased by one and duplicated 4 times for the 4 function calls. When the order is zero, stop; otherwise, do the recursive calls according to the equation:
F does nothing and just disappears, except at the end, when order is 0, it draws a piece of line:
+ do right and left 45 degree rotations, as expected:
Make sure that pieces of lines are joined nicely:
Finally, decide where to start and scale the drawing according to the order value so that it’s always the same size, no matter what the order is:
Rotate the drawing to landscape, and start:
And proudly show the resulting page:
The whole PostScript program can be downloaded here.
On my way to understand the mysteries of this Dragon Curve program I had found, I encountered a number of L-system equations. Some of them are classic fractals, like Hilbert’s curve:
or Koch’s snowflake:
But the ones I like best are plant-like pictures. (After all, Lindenmayer was a biologist.) What I find interesting about them is how different they are from each other while based on similar sets of equations. Some of my favorites are below:
I have not mentioned
] which are used for branching. Basically,
] brings you back in the drawing at the point where the corresponding
[ was issued. They are easily implemented in PostScript using
grestore, used to push and pop the graphics context on and off the stack.
The plants on this page were all rendered using this PostScript program by simply modifying the equations (
] are called
E because the square brackets are part of PostScript’s syntax). This program is a little more complicated than the Dragon Curve before, but it’s mostly because of multiple color schemes and because it’s made generic to work with many different equations.
For reasons that were never clear (and probably involve cosmic forces beyond our comprehension), this experiment in programming L-systems in PostScript was published by the Zpravodaj Československého sdružení uživatelů TeXu (2012, vol. 1) under the title Programujeme L-systémy v PostScriptu. The paper contains a few more technical details and, in spite of its Czech title, is written in English.