Dragon curve
Encyclopedia
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
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+
- Y −FX−Y.
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:
.svg.png)
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).
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 codeGray 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 dimensionFractal dimensionIn 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 curveSpace-filling curveIn 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
..jpg) |
 |
Terdragon
- 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 curveLé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.
.jpg) |
See also
- List of fractals by Hausdorff dimension
- Complex base systemsComplex base systemsIn 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 sequenceRegular paperfolding sequenceIn 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
- Dragon Curve—from MathWorldMathWorldMathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...
- Dragon Curve Maker in Flash
- Tile made by David Chow
- Twin dragon tile with JAVA
