The dragon
fractal is a
path that doubles in length, and the distance from start to finish grows by a multiple of 2^.5 for every new iteration.
Some interesting facts about this fractal
No edges overlap.
Appears several times in the book "
Jurassic Park".
Virtually no application in real life.
How to draw it
Step 1: Draw the previous
iteration from start to finish.
Step 2: Starting at the finishing point of that image, draw a copy of that image
so that the copy is a 90° rotation of the first image, rotated about the finish point of the previous image.
(
The rotation can be either clockwise or counter-clockwise, as long as it is consistant throughout all other iterations.
)
The first few iterations
Iteration 0 Iteration 1 Iteration 2 Iteration 3
_ _ _
| | _| | _| |
|_
_|
Iteration 4 Iteration 5 Iteration 6
_ _ _ _
_| | _| | _ |_|_| |_
|_ |_ _| | _ _| _|
_|_ _|_ _ _ |_ |_|_|_
|_| |_ |_| |_|_|_| |_ _|_ _ _|_|_|
_| _|_| _| |_| |_|_|_| |_|_
|_| _|_| _|_|
|_| |_|
Iteration 7 Iteration 8
_ _ _ _
|_|_| |_ |_|_| |_
_ _| _| _ _| _|
|_|_|_ |_|_|_
|_|_| |_|_|
|_ _ |_ _ _ _
_ _|_|_| _ _|_|_| _|_| _|_|
|_|_|_|_|_ _ |_|_|_|_|_ _|_|_ _|_|_ _
|_|_|_|_|_|_| |_| |_| |_|_|_|_|_|_|_|_|_|_|
_ |_|_| |_|_ |_|_|_|_|_|_| |_|_
_| | _ _| _|_| _ _|_|_|_|_| _|_|
|_ |_|_|_ |_| |_|_|_|_|_|_|_ |_|
_|_ _ _|_|_| |_| |_| |_|_|
|_| |_|_|_| |_|_ |_ _
_|_| _|_| _ _|_|_|
|_| |_| |_|_|_|_|_ _
|_|_|_|_|_|_|
_ |_|_| |_|_
_| | _ _| _|_|
|_ |_|_|_ |_|
_|_ _ _|_|_|
|_| |_|_|_| |_|_
_|_| _|_|
|_| |_|
Iteration 9
_ _
_|_| _|_|
|_|_ _|_|_ _
_ _ _|_|_|_|_|_|_|_|
|_|_| |_ _ |_|_|_|_|_| |_|_
_ _| _| _|_| _|_|_|_| _|_|
|_|_|_ |_|_ _|_|_|_|_ |_|
|_|_| _|_|_|_|_|_|_|_|
|_ _ _ |_|_|_|_|_|_|_|_ _ _ _
_ _|_|_| _|_| _|_|_|_|_|_|_|_|_|_| _|_| _|_|
|_|_|_|_|_ _|_|_ _|_|_|_|_|_|_|_|_|_|_ _|_|_ _|_|_ _
|_| |_| |_|_|_|_|_| |_| |_|_|_|_|_| |_| |_|_|_|_|_|_|_|_|_|_|
|_|_|_|_ |_|_|_|_ |_|_|_|_|_|_| |_|_
_ _|_| |_| _ _|_| |_| _ _|_|_|_|_| _|_|
|_|_|_|_ |_|_|_|_ |_|_|_|_|_|_|_ |_|
|_| |_| |_| |_| |_| |_| |_|_|
|_ _
_ _|_|_|
|_|_|_|_|_ _
|_|_|_|_|_|_|
_ |_|_| |_|_
_| | _ _| _|_|
|_ |_|_|_ |_|
_|_ _ _|_|_|
|_| |_|_|_| |_|_
_|_| _|_|
|_| |_|
The recurrence relation
Fold
0 = (no turns)
Fold
n = First
n + "L" + Last
n
First
n = Fold
n-1
Last
n = (Fold
n-1)'
(apostrophe means traverse the path backwards.)
Basically what these equations mean is that A) the first iteration is just a straight path with no turning, and
B) in further iterations, drawing the image involves drawing the first half, making a 90° rotation (a left turn in this case), and then drawing the second half.
The first half involves drawing the previous iteration, the second half involves drawing the first image
backwards,
i.e.
the path is traversed in reverse order,
and every right turn becomes a left turn and vice versa.
The computer program
If a computer program was to draw this as described above, drawing the second half would be expensive because the
program has to create a
stack of turns before it can draw a path backwards.
A cheaper way of calculating the second part can be derived from further expanding the equation:
Last
n = (First
n-1 + "L" + Last
n-1)'
Last
n = (Last
n-1)' + ("L")' + (First
n-1)' // switch order
Last
n = First
n-1 + "R" + Last
n-1 // Left turn becomes right turn, etc.
Now the first part and the last part of the iteration differs only by one turn.
Thus the cheaper
algorithm in
pseudo-code follows:
void Fold (int turn, int n) {
if (n == 0) {
drawSegment();
}
else {
Fold (LEFT, n - 1); // same as First(n).
Turn (turn);
Fold (RIGHT, n - 1); // same as Last(n).
}
}