NationMaster - Encyclopedia: Dragon curve

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. A self-similar object is exactly or approximately similar to a part of itself. ... The boundary of the Mandelbrot set is a famous example of a fractal. ... A visual form of recursion known as the Droste effect. ... An L-system or Lindenmayer system is a formal grammar (a set of rules and symbols) most famously used to model the growth processes of plant development, though able to model the morphology of a variety of organisms. ...

1 Heighway dragon
- 1.1 [Un]Folding the Dragon
- 1.2 Dimensions of the Heighway dragon curve
2 Twindragon
3 Terdragon
4 Lévy dragon
5 See also
6 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. The National Aeronautics and Space Administration (NASA) is an agency of the United States federal government, responsible for the nations public space program. ... Martin Gardner (b. ... Scientific American is a popular-science magazine, published (first weekly and later monthly) since August 28, 1845, making it the oldest continuously published magazine in the United States. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Jurassic Park is a techno-thriller novel written by Michael Crichton that was published in 1990. ...

It can be written as a Lindenmayer system with An L-system or Lindenmayer system is a formal grammar (a set of rules and symbols) most famously used to model the growth processes of plant development, though able to model the morphology of a variety of organisms. ...

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: Menger sponge, created by using IFS. Iterated function systems or IFSs, are a kind of fractal which were conceived in their present form by John Hutchinson in 1981 and popularized by Michael Barnsleys book Fractals Everywhere. ...

$f_1(z)=frac{(1+i)z}{2}$

$f_2(z)=1-frac{(1-i)z}{2}$ .

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.

Image File history File links Fractal_dragon_curve. ... Image File history File links Fractal_dragon_curve. ... Image File history File links Pavement_with_dragons. ... Image File history File links Pavement_with_dragons. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ...

[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 nth turn in the turn sequence of a Heighway dragon iteration. First, express n in the form k2^m 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. Image File history File links Download high resolution version (1714x400, 143 KB) File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...

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: The adjective Boolean [], coined in honor of George Boole, is used in many contexts: An evaluation that results in either of the truth values true or false. A Boolean value is a truth value, either true or false, often coded 1 and 0, respectively. ...

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 nth turn is R; and is FALSE if the nth 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 $textstyle{frac{1}{2}}$ . 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 $textstyle{sqrt{2}}$ .

Its fractal dimension can be calculated : $textstyle{frac {ln 2} {ln sqrt{2}} = 2}$ . That makes it a space-filling curve.

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

Image File history File links Size of this preview: 800 Ã— 430 pixelsFull resolution (849 Ã— 456 pixel, file size: 16 KB, MIME type: image/gif) File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ... Image File history File links Size of this preview: 800 Ã— 576 pixelsFull resolution (808 Ã— 582 pixel, file size: 19 KB, MIME type: image/gif) File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ... Space-filling curves or Peano curves are curves, first described by Giuseppe Peano, whose ranges contain the entire 2-dimensional unit square (or the 3-dimensional unit cube). ...

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:

$f_1(z)=frac{(1+i)z}{2}$

$f_2(z)=frac{(1+i)z+1-i}{2}$ .

Twindragon curve.

Twindragon curve constructed from two Heighway dragons.

Image File history File links LÃ©vys_dragon_curve_(IFS). ... Image File history File links LÃ©vys_dragon_curve_(IFS). ... Image File history File links Twindragon. ... Image File history File links Twindragon. ...

Terdragon

Terdragon curve.

The terdragon can be written as a Lindenmayer system: Image File history File links Terdragon. ... Image File history File links Terdragon. ...

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) = λ z

$f_2(z)=frac{i}{sqrt{3}}z + lambda$

f 3 (z) = λ z + λ *

$mbox{where }lambda=frac{1}{2}-frac{i}{2sqrt{3}} mbox{ and }lambda^*=frac{1}{2}+frac{i}{2sqrt{3}}$ .

Lévy dragon

The Lévy C curve is sometimes known as the Lévy dragon. In mathematics, the LÃ©vy C curve is a self similar fractal that was first described and whose differentiability properties were analysed by E.Cesaro in 1906 and G. Farber in 1910, but now bears the name of French mathematician Paul LÃ©vy, who was the first to describe its...

Lévy C curve.

External links

Wikimedia Commons has media related to:

Dragon curve

Dragon Curve—from MathWorld
Paperfolding and the Dragon curve

Category: Fractal curves Image File history File links Commons-logo. ... The Wikimedia Commons (also called Wikicommons) is a repository of free content images, sound and other multimedia files. ... MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ...

Results from FactBites:

Tail of the Dragon at Deals Gap and Cherohala Skyway, Graham Co, NC (213 words)
	Tail of the Dragon at Deals Gap and Cherohala Skyway, Graham Co, NC DESTINATION : TAIL OF THE DRAGON and CHEROHALA SKYWAY
	GPS Coordinates for the Tail of the Dragon at Deals Gap - at the NC / TN state line
	DRAGON MAP with location of deaths since 2000

European dragon - Wikipedia, the free encyclopedia (1960 words)
	The dragon of the modern period is typically depicted as a huge fire-breathing, scaly and horned dinosaur-like creature, with leathery wings, with four legs and a long muscular tail.
	The female dragon represents harsh weather and is the destroyer of crops, the hater of mankind, and is locked in a never ending battle with her brother.
	The red dragon is unmistakably linked with the Welsh and it is believed the white dragon refers to the English, but some have speculated that it originates from Arthurian Legend where Merlin had a vision of the red dragon (representing Uther Pendragon) and the white dragon (representing Vortigen) in battle.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 0825, e

Contents

Heighway dragon GA_googleFillSlot("encyclopedia_square");