Discover

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

Contents

Heighway dragon

[Un]Folding the Dragon

Dimensions of the Heighway dragon curve

Twindragon

Terdragon

Lévy dragon

See also

External links

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 appeared on the section title pages of the Michael Crichton novel ''Jurassic Park''.
It can 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:
:
:.

'Heighway dragon curve'

The dragon curve can be tiled to fill a plane.

The combination of four dragon curves can be spacefiling when a constant size is assigned to a line segment, rather than the entire curve.

[Un]Folding the Dragon

Tracing an iteration of the Heighway dragon curve from one end to the other, one encounters a series of 90 degree turns, some to the right and some to the left. For the first few iterations the sequence of right (R) and left (L) turns is as follows:
:1st iteration: R
:2nd iteration: 'R' R 'L'
:3rd iteration: 'R' R 'L' R 'R' L 'L'
:4th iteration: 'R' R 'L' R 'R' L 'L' R 'R' R 'L' L 'R' L 'L'
This suggests the following pattern: each iteration is formed by taking the previous iteration, adding an R at the end, and then taking the original iteration again, flipping it, switching each letter and adding the result after the R.
This pattern in turn suggests the following method of creating models of iterations of the Heighway dragon curve by folding a strip of paper. Take a strip of paper and fold it in half to the right. Fold it in half again to the right. If the strip was opened out now, unbending each fold to become a 90 degree turn, the turn sequence would be RRL i.e. the second iteration of the Heighway dragon. Fold the strip in half again to the right, and the turn sequence of the unfolded strip is now RRLRRLL - the third iteration of the Heighway dragon. Continuing folding the strip in half to the right to create further iterations of the Heighway dragon (in practice, the strip becomes too thick to fold sharply after four or five iterations).

This pattern also gives a method for determining the direction of the ''n''th turn in the turn sequence of a Heighway dragon iteration. First, express ''n'' in the form ''k''2^''m'' where ''k'' is an odd number. The direction of the ''n''th turn is determined by ''k'' mod 4 i.e. the remainder left when ''k'' is divided by 4. If ''k'' mod 4 is 1 then the ''n''th turn is R; if ''k'' mod 4 is 3 then the ''n''th turn is L.
For example, to determine the direction of turn 76376:
:76376 = 9547 x 8.
:9547 = 2386x4 + 3
:so 9547 mod 4 = 3
:so turn 76376 is L
There is a simple one line non-recursive method of implementing the above ''k'' mod 4 method of finding the turn direction in code. Treating turn ''n'' as a binary number, calculate the following boolean value:
:bool turn = (((n & -n) << 1) & n) != 0;

★ "n & -n" leaves you with only one bit as a '1', the rightmost '1' in the binary expansion of ''n'';

★ "<< 1" shifts the that bit one bit to the left;

★ "& n" leaves you with either that single bit (if ''k'' mod 4 =1) or a zero (if ''k'' mod 4 =3).

★ so "bool turn = (((n & -n) << 1) & n) != 0" is TRUE if the ''n''th turn is R; and is FALSE if the ''n''th turn is L.

Dimensions of the Heighway dragon curve

★ In spite of its strange aspect, the Heighway dragon curve has simple dimensions:


★ Its 'surface' is also quite simple : If the initial segment equals 1, then its surface equals . This result comes immediately from its paving properties.

★ Many 'self-similarities' can be seen in the Heighway dragon curve. The most obvious is the repetition of the same pattern tilted by 45° and with a reduction ratio of $extstyle\{sqrt\{2\}\}$.


★ Its fractal dimension can be calculated : . That makes it a space-filling curve.

★ The fractal dimension of its 'boundary' has been calculated by Chang & Zhang : 1.5238

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:
:
:.

Twindragon curve.

Twindragon curve constructed from two Heighway dragons.

Terdragon

The 'terdragon' can be written as a Lindenmayer system:

★ angle 120°

★ initial string ''F''

★ string rewriting rules

★
★ ''F'' $mapsto$ ''F+F-F''
It is the limit set of the following iterated function system:
:$f\_1(z)=lambda\; z$
:
:$f\_3(z)=lambda\; z\; +\; lambda^$
★
:
mbox{ and }lambda^
★ =rac{1}{2}+rac{i}{2sqrt{3}}.

Lévy dragon

The Lévy C curve is sometimes known as the 'Lévy dragon'.

Lévy C curve.

See also

★ Fractal

★ List of fractals by Hausdorff dimension

External links

★ Dragon Curve—from MathWorld

★ Paperfolding and the Dragon curve

★ Dragon Curve Maker in Flash