Dragon curve

Fig. 1. A forest...? a whirlpool...? a blaze? of Dragons. What do you think a collective noun for these should be?

You fold a paper strip absent-mindedly and a wondrous creature emerges...

If you read The Jurassic Park by M. Crichton (and I’m sure you did), you sure have noticed how each of the chapters started with a page featuring an interesting drawing. It began at first with a simple set of lines, but as you progressed in the book, it got more and more convoluted. I couldn’t figure out the rule behind it at the time, and I found the explanation only years later.

Fig. 2. Dragon curve animation by 碳酸鈣 (available at  this
 Wiki page under CC license).

The lines form a fractal, which is also called Heighway dragon, the Jurassic Park dragon, or simply a dragon curve (see fig. 2). It’s quite a nice thing to doodle! There are a few ways you can do this and the choice is yours:

1. The paper strip folding method

Take a strip of paper. Start folding it: right over left, and keep repeating: right over left, right over left… You won’t be able to do that more than 4-5 times. Don't worry! You can always make more components and connect them end to end  to get more complicated shapes (more iterations of the fractal).

Unfold  each of the components and crease all the folds so they all form right angles (see fig. 3). Place it on a flat surface, and voila!

Fig. 3. How to make the Dragon Curve by folding the paper strips.

2. The pen-and-paper method
You can very well draw the dragon on the paper, starting with a straight line segment and making proper right or left 90 degree turns. There is a neat method that can be used for the determination of the turns in the sequence. Let's start with an example (R marks a right turn and L - a left turn):

1st iteration:  R,
2nd iteration:  R_R_L,
3rd:            RRL_R_RLL,
4th:            RRLRRLL_R_RRLLRLL,

And so on… As you can see, in each of the iterations you take the previous one, add an R (right 90 degree turn) at the end, and then add the previous iteration again, but this time  both reversing i, and swapping R’s and L’s (see fig. 4).

Fig. 4. Drawing the Dragon Curve.

3. The computer friendly method
You can calculate the n-th turn direction by evaluating the following expression:

if ((n & -n) << 1) & n == 0 then:

  turn ← R;

else:

  turn ← L;

& is a bitwise and operator, << is left shift and you have to remember the -n should be encoded as two-complement. Also, the n-th full iteration is a sequence of 2n-1 turns, so you should probably calculate all of these! :)

For example, the direction of 42nd turn is:

((00101010 & 11010110) << 1) & 00101010 =
= 00000100 & 00101010 = 0,

so the 42nd turn is R.

The figure 1 comes from an old program I wrote in C to explore the possibilities offered by the Dragon curves. You can find this program here.

If you ever want to summon a dragon, just use your imagination! 

Sources:
http://en.wikipedia.org/wiki/Dragon_curve
http://math.rice.edu/~lanius/frac/jurra.html

Note. This was originally posted on my Tumblr blog: http://dagothar.tumblr.com/post/26697353061/the-jurassic-park-fractal-if-you-read-the. I think this is a much better place for it though, and I'm pretty sure you haven't seen it yet anyway!