Dragon curve

A dragon curve is the generic name for a member of a family of self similar fractal curves, which can be approximated by recursive methods such as Lindenmayer systems.

Heighway dragon

The Heighway dragon (also known as the Harter-Heighway dragon or the Jurassic Park dragon) was first investigated by NASA physicists John Heighway, Bruce Banks, and William Harter. It was described by Martin Gardner in his Scientific American column Mathematical Games in 1967. Many of its properties were first published by Chandler Davis and Donald Knuth.

It can be be written as a Lindenmayer system with

angle 90°
initial string FX
string rewriting rules
- X $\mapsto$ X+YF+
- Y $\mapsto$ -FX-Y

The Heighway dragon is also the limit set of the following iterated function system in the complex plane:

f_{1}(z)={\frac {(1+i)z}{2}}

f_{2}(z)=1-{\frac {(1-i)z}{2}}

.

Heighway dragon curve

The dragon curve can be tiled to fill a plane.

A model of a Heighway dragon curve can be made by repeatedly folding a strip of paper always to the same side, and then unfolding it so that all angles are at 90 degrees (see below).

[Un]Folding the Dragon

Of course, the beautiful images you see on this page weren't created by folding pieces of paper. Fortunately, it's easy to use a computer to generate a "fold array" that emulates this paper folding. And you can do it without any complex math. To start, we'll work out a pattern for the fold array by making a few folds with real paper.

Make the first fold to the right, and now your fold array is just a single fold, [R]. To make the dragon curve, you continue folding in the same direction over and over. So with the paper still folded in half, fold it in half again, the same way, and again to the right. If you unfold it now and arrange all the folds to be 90 degrees, you'll see that the fold array is now: [R,R,L]. The middle R is our first fold. When we folded it again, the first half of the paper was still right side up, so the right hand fold just stayed a right hand fold. The other half of the paper, however, was inverted, so the right hand fold translates into a left hand fold, on the other side of the center fold.

From this, you can see that for any fold we make, we can just divide the paper in half along the previous fold, make the intended fold on the first half of the paper, and make the opposite fold on the other half. For instance, from where we left off after the second iteration, we can divde it into two seperate papers, each with it's own fold array. The first is just [R], and the second is simply [L], because we divded it around the middle fold. The first half is right back to where we were after the first iteration, so another iteration will make it [R,R,L], just like we got last time. Because the other half of the paper was turned upside down by the center hold, any fold we make here is going to be inverted. After making the fold, you can see that the array for this half of the paper is [R,L,L]. You can see from this example (and by logic I don't feel like getting into) that the fold array for the second half of the paper can always be found by inverting all the folds of the first half (R becomes L, and L becomes R), and reversing the order. So for this iteration, inverting the first array gets us [L,L,R], and reversing it gives us [R,L,L], which is our second half. To get our overall fold array, we put them together, recalling that they are joined by a right hand fold: [R,R,L] + [R] + [R,L,L] = [R,R,L,R,R,L,L].

Now that we have the pattern, we can put down the paper and pick up (so to speak) the computer. Just pick your favorite programming language (MATLAB's M-code actually works really for this type of rapid array operation) and use the following algorithm:

Array(N+1) = Array(N) + [R] + reverse(invert(Array(N)))

So carrying on from the third iteration we derived above: 3rd - [R,R,L,R,R,L,L] 4th - [R,R,L,R,R,L,L] + [R] + [R,R,L,L,R,L,L] 5th - [R,R,L,R,R,L,L,R,R,R,L,L,R,L,L] + [R] + [R,R,L,R,R,L,L,L,R,R,L,L,R,L,L] 6TH - [R,R,L,R,R,L,L,R,R,R,L,L,R,L,L,R,R,R,L,R,R,L,L,L,R,R,L,L,R,L,L] + [R] + [R,R,L,R,R,L,L,R,R,R,L,L,R,L,L,L,R,R,L,R,R,L,L,L,R,R,L,L,R,L,L] etc.

Now to construct the actual fractal from the folds array

start with a straight line up and down of length N
at the end of the line, turn in whatever direction is marked by the first element in the fold list (R, in this case)
draw another line in that direction of length N
use the next element in the array to determine which direction to turn
keep going!

Twindragon

The twindragon (also known as the Davis-Knuth dragon) can be constructed by placing two Heighway dragon curves back-to-back. It is the limit set of the following iterated function system: