Dragon curve
Encyclopedia
A dragon curve is any member of a family of self-similar
Self-similarity
In mathematics, a self-similar object is exactly or approximately similar to a part of itself . Many objects in the real world, such as coastlines, are statistically self-similar: parts of them show the same statistical properties at many scales...

 fractal
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...

 curves, which can be approximated by recursive
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

 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
NASA
The National Aeronautics and Space Administration is the agency of the United States government that is responsible for the nation's civilian space program and for aeronautics and aerospace research...

 physicists John Heighway, Bruce Banks, and William Harter. It was described by Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...

 in his Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...

 column Mathematical Games in 1967. Many of its properties were first published by Chandler Davis and Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...

. It appeared on the section title pages of the Michael Crichton
Michael Crichton
John Michael Crichton , best known as Michael Crichton, was an American best-selling author, producer, director, and screenwriter, best known for his work in the science fiction, medical fiction, and thriller genres. His books have sold over 200 million copies worldwide, and many have been adapted...

 novel Jurassic Park.

Construction

It can be written as a Lindenmayer system with
  • angle 90°
  • initial string FX
  • string rewriting rules
    • X X+YF+
    • YFXY.


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 Heighway dragon is also the limit set of the following iterated function system
Iterated function system
In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar....

 in the complex plane:


with the initial set of points .

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



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
Paper folding
Paper craft is the collection of art forms employing paper or card as the primary artistic medium for the creation of three-dimensional objects. It is the most widely used material in arts and crafts. It lends itself to a wide range of techniques, it can for instance be folded, cut, glued,...

. 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 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
Boolean logic
Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...

 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
Gray code
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted 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:

  • Its surface is also quite simple : If the initial segment equals 1, then its surface equals . This result comes from its paving properties.
  • Its boundary has an infinite length, since it increases by a factor of every iteration.
  • 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 .

  • Its fractal dimension
    Fractal dimension
    In fractal geometry, the fractal dimension, D, is a statistical quantity that gives an indication of how completely a fractal appears to fill space, as one zooms down to finer and finer scales. There are many specific definitions of fractal dimension. The most important theoretical fractal...

     can be calculated : . That makes it a space-filling curve
    Space-filling curve
    In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...

    .

  • The fractal dimension of its boundary has been approximated numerically by Chang & Zhang.

In fact it can be found analytically :
This is the root of the equation

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:


where the initial shape is defined by the following set .

Terdragon

The terdragon can be written as a Lindenmayer system:
  • angle 120°
  • initial string F
  • string rewriting rules
    • F F+F−F.


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

Lévy dragon

The Lévy C curve
Lévy C curve
In mathematics, the Lévy C curve is a self-similar fractal that was first described and whose differentiability properties were analysed by Ernesto Cesàro in 1906 and G...

 is sometimes known as the Lévy dragon.

See also

  • List of fractals by Hausdorff dimension
  • Complex base systems
    Complex base systems
    In arithmetic, a complex base system is a positional numeral system whose radix is an imaginary or complex number In arithmetic, a complex base system is a positional numeral system whose radix is an imaginary (proposed by Donald Knuth in 1955) or complex number In arithmetic, a complex base...

  • Regular paperfolding sequence
    Regular paperfolding sequence
    In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite automatic sequence of 0s and 1s defined as the limit of the following process:...


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK