Dragon curve

Dragon curve
Dragon curve animation.gif

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

Contents

Heighway dragon

Heighway dragon curve

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.

Construction

Recursive construction of the curve

It can be written as a Lindenmayer system with

  • angle 90°
  • initial string FX
  • string rewriting rules
    • XX+YF+
    • Y ↦ −FXY.

That can be described this way : Starting from a base segment, replace each segment by 2 segments with a right angle and with a rotation of 45° alternatively to the right and to the left:

The first 5 iterations and the 9th

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}

with the initial set of points S0 = {0,1}.

Using pairs of real numbers instead, this is the same as the two functions consisting of

f_1(x,y)= \frac{1}{\sqrt{2}}\begin{pmatrix} \cos 45^o & -\sin 45^o \\ \sin 45^0 & \cos 45^o \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}
f_2(x,y)= \frac{1}{\sqrt{2}}\begin{pmatrix} \cos 135^o & -\sin 135^o \\ \sin 135^0 & \cos 135^o \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} + \begin{pmatrix} 1 \\ 0 \end{pmatrix}

This representation is more commonly used in software such as Apophysis.

[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).

Dragon curve paper strip.png

This pattern also gives a method for determining the direction of the nth turn in the turn sequence of a Heighway dragon iteration. First, express n in the form k2m where k is an odd number. The direction of the nth 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 nth turn is R; if k mod 4 is 3 then the nth 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 = 3) or a zero (if k mod 4 = 1).
  • so "bool turn = (((n & −n) << 1) & n) != 0" is TRUE if the nth turn is L; and is FALSE if the nth turn is R.

Gray code method

Another way of handling this is a reduction for the above algorithm. Using Gray code, starting from zero, determine the change to the next value. If the change is a 1 turn left, and if it is 0 turn right. Given a binary input, B, the corresponding gray code, G, is given by "G = B XOR (B>>1)". Using Gi and Gi−1, turn equals" (not Gi) AND Gi−1".

  • G = B^(B >> 1); This gets gray code from binary.
  • T = (~G0)&G1; If T is equal to 0 turn clockwise else turn counterclockwise.

Dimensions

  • In spite of its strange aspect, the Heighway dragon curve has simple dimensions:
Dimensions fractale dragon.gif
  • Its surface is also quite simple : If the initial segment equals 1, then its surface equals \textstyle{\frac{1}{2}}. This result comes from its paving properties.
  • Its boundary has an infinite length, since it increases by a factor of {\sqrt{2}} every iteration.[1]
  • The curve never crosses itself.
  • 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 \textstyle{\sqrt{2}}.
Auto-similarity dragon curve.gif
  • The fractal dimension of its boundary has been approximated numerically by Chang & Zhang.

In fact it can be found analytically [2]: \log_2\left(\frac{1+\sqrt[3]{73-6\sqrt{87}}+\sqrt[3]{73+6\sqrt{87}}}{3}\right)\cong 1.523627086202492. This is the root of the equation \textstyle{4^x(2^x-1)=4(2^x+1).}

Tiling

The dragon curve can tile the plane in many ways.

Twindragon

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

f_1(z)=\frac{(1+i)z}{2}
f_2(z)=1-\frac{(1+i)z}{2}

where the initial shape is defined by the following set S0 = {0,1,1 − i}.

Twindragon curve.
Twindragon curve constructed from two Heighway dragons.

Terdragon

Terdragon curve.

The terdragon can be written as a Lindenmayer system:

  • angle 120°
  • initial string F
  • string rewriting rules
    • FF+F−F.

It is the limit set of the following iterated function system:

f1(z) = λz
f_2(z)=\frac{i}{\sqrt{3}}z + \lambda
f3(z) = λz + λ *
\mbox{where }\lambda=\frac{1}{2}-\frac{i}{2\sqrt{3}}
\text{ and }\lambda^*=\frac{1}{2}+\frac{i}{2\sqrt{3}}.

Lévy dragon

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

Lévy C curve.

See also

Notes

  1. ^ http://library.thinkquest.org/26242/full/fm/fm8.html
  2. ^ "The Boundary of Periodic Iterated Function Systems" by Jarek Duda, The Wolfram Demonstrations Project. Recurrent construction of the boundary of dragon curve.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Curve — For other uses, see Curve (disambiguation). A parabola, a simple example of a curve In mathematics, a curve (also called a curved line in older texts) is, generally speaking, an object similar to a line but which is not required to be straight.… …   Wikipedia

  • Dragon (disambiguation) — A dragon is a legendary creature, typically with serpentine or otherwise reptilian traits. Dragon may also refer to: Contents 1 Literature 2 Music 3 …   Wikipedia

  • Dragon Challenge — Location Islands of Adventure Park section The Wizarding World Of Harry Potter Coordinates …   Wikipedia

  • Dragon Quest — For the first video game in the series, see Dragon Warrior. For other uses, see Dragon Quest (disambiguation). Dragon Quest …   Wikipedia

  • Dragon Warrior — This article is about the NES video game Dragon Warrior. For the series, see Dragon Quest. For the similarly named role playing game, see Dragon Warriors. Dragon Warrior …   Wikipedia

  • Dragon Coaster (Playland) — The Dragon Coaster Location Playland Park Coordinates …   Wikipedia

  • Courbe du dragon — La courbe du dragon (ou Fractale du dragon ou courbe de Heighway ou dragon de Heighway ) a été pour la première fois étudiée par les physiciens de la NASA John Heighway, Bruce Banks, et William Harter. Elle a été décrite par Martin Gardner dans… …   Wikipédia en Français

  • Fractale du dragon — Courbe du dragon Courbe du dragon La courbe du dragon (ou Fractale du dragon ou courbe de Heighway ou dragon de Heighway ) a été pour le première fois étudiée par les physiciens de la NASA John Heighway, Bruce Banks, et William Harter. Elle a été …   Wikipédia en Français

  • Curva del dragón — Saltar a navegación, búsqueda Proceso de formación de este fractal. La curva del dragón es un fractal que se construye siguiendo los siguientes pasos: A partir de un segmento, se construye el triángulo rectángulo e isósceles, como lo muestra las… …   Wikipedia Español

  • Space-filling curve — 3 iterations of a Peano curve construction, whose limit is a space filling curve. In mathematical analysis, a space filling curve is a curve whose range contains the entire 2 dimensional unit square (or more generally an N dimensional hypercube) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”