Dragon curve

From Rosetta Code
Jump to: navigation, search
Task
Dragon curve
You are encouraged to solve this task according to the task description, using any language you may know.

Create and display a dragon curve fractal. (You may either display the curve directly or write it to an image file.)

Contents

[edit] Algorithms

Here are some brief notes the algorithms used and how they might suit various languages.

  • Recursively a right curling dragon is a right dragon followed by a left dragon, at 90-degree angle. And a left dragon is a left followed by a right.
*---R----*     expands to     *       *
                               \     /
                                R   L
                                 \ /
                                  *

                                  *
                                 / \
                                L   R
                               /     \
*---L---*      expands to     *       *
The co-routines dcl and dcr in various examples do this recursively to a desired expansion level.
  • The curl direction right or left can be a parameter instead of two separate routines.
  • Recursively, a curl direction can be eliminated by noting the dragon consists of two copies of itself drawn towards a central point at 45-degrees.
*------->*   becomes    *       *     Recursive copies drawn
                         \     /      from the ends towards
                          \   /       the centre.
                           v v
                            *
This can be seen in the SVG example. This is best suited to off-line drawing since the reversal in the second half means the drawing jumps backward and forward (in binary reflected Gray code order) which is not very good for a plotter or for drawing progressively on screen.
  • Successive approximation repeatedly re-writes each straight line as two new segments at a right angle,
                       *       
*-----*   becomes     / \      bend to left
                     /   \     if N odd
                    *     *

                    *     *   
*-----*   becomes    \   /     bend to right  
                      \ /      if N even 
                       *
Numbering from the start of the curve built so far, if the segment is at an odd position then the bend introduced is on the right side. If the segment is an even position then on the left. The process is then repeated on the new doubled list of segments. This constructs a full set of line segments before any drawing.
The effect of the splitting is a kind of bottom-up version of the recursions. See the Asymptote example for code doing this.
  • Iteratively the curve always turns 90-degrees left or right at each point. The direction of the turn is given by the bit above the lowest 1-bit of n. Some bit-twiddling can extract that efficiently.
n = 1010110000
        ^
        bit above lowest 1-bit, turn left or right as 0 or 1

LowMask = n BITXOR (n-1)   # eg. giving 0000011111
AboveMask = LowMask + 1    # eg. giving 0000100000
BitAboveLowestOne = n BITAND AboveMask
The first turn is at n=1, so reckon the curve starting at the origin as n=0 then a straight line segment to position n=1 and turn there.
If you prefer to reckon the first turn as n=0 then take the bit above the lowest 0-bit instead. This works because "...10000" minus 1 is "...01111" so the lowest 0 in n-1 is where the lowest 1 in n is.
Going by turns suits turtle graphics such as Logo or a plotter drawing with a pen and current direction.
  • If a language doesn't maintain a "current direction" for drawing then you can always keep that separately and apply turns by bit-above-lowest-1.
  • Absolute direction to move at point n can be calculated by the number of bit-transitions in n.
n = 11 00 1111 0 1
      ^  ^    ^ ^     4 places where change bit value
                      so direction=4*90degrees=East
This can be calculated by counting the number of 1 bits in "n XOR (n RIGHTSHIFT 1)" since such a shift and xor leaves a single 1 bit at each position where two adjacent bits differ.
  • Absolute X,Y coordinates of a point n can be calculated in complex numbers by some powers (i+1)^k and add/subtract/rotate. This is done in the gnuplot code. This might suit things similar to Gnuplot which want to calculate each point independently.
  • Predicate test for whether a given X,Y point or segment is on the curve can be done. This might suit line-by-line output rather than building an entire image before printing. See M4 for an example of this.
A predicate works by dividing out complex number i+1 until reaching the origin, so it takes roughly a bit at a time from X and Y is thus quite efficient. Why it works is slightly subtle but the calculation is not difficult. (Check segment by applying an offset to move X,Y to an "even" position before dividing i+1. Check vertex by whether the segment either East or West is on the curve.)
The number of steps in the predicate corresponds to doublings of the curve, so stopping the check at say 8 steps can limit the curve drawn to 2^8=256 points. The offsets arising in the predicate are bits of n the segment number, so can note those bits to calculate n and limit to an arbitrary desired length or sub-section.
  • As a Lindenmayer system of expansions. The simplest is two symbols F and S both straight lines, as used by the PGF code.
Axiom F, angle 90 degrees
F -> F+S
S -> F-S

This always has F at even positions and S at odd. Eg. after 3 levels F_S_F_S_F_S_F_S. The +/- turns in between bend to the left or right the same as the "successive approximation" method above. Read more at for instance Joel Castellanos' L-system page.

Variations are possible if you have only a single symbol for line draw, for example the Icon and Unicon and Xfractint code. The angles can also be broken into 45-degree parts to keep the expansion in a single direction rather than the endpoint rotating around.

The string rewrites can be done recursively without building the whole string, just follow its instructions at the target level. See for example C by IFS Drawing code. The effect is the same as "recursive with parameter" above but can draw other curves defined by L-systems.

[edit] ALGOL 68

Translation of: python
Works with: ALGOL 68G version Any - tested with release algol68g-2.8.
File: prelude/turtle_draw.a68
# -*- coding: utf-8 -*- #
 
STRUCT (REAL x, y, heading, BOOL pen down) turtle;
 
PROC turtle init = VOID: (
draw erase (window);
turtle := (0.5, 0.5, 0, TRUE);
draw move (window, x OF turtle, y OF turtle);
draw colour name(window, "white")
);
 
PROC turtle left = (REAL left turn)VOID:
heading OF turtle +:= left turn;
 
PROC turtle right = (REAL right turn)VOID:
heading OF turtle -:= right turn;
 
PROC turtle forward = (REAL distance)VOID:(
x OF turtle +:= distance * cos(heading OF turtle) / width * height;
y OF turtle +:= distance * sin(heading OF turtle);
IF pen down OF turtle THEN
draw line
ELSE
draw move
FI (window, x OF turtle, y OF turtle)
);
 
SKIP
File: prelude/exception.a68
# -*- coding: utf-8 -*- #
 
COMMENT
REQUIRES :
MODE EXCEPTOBJ = UNION(VOID, MODEA, MODEB, MODEC ...);
OP FIRMSTR = (EXCEPTOBJ obj)STRING: ~
END COMMENT
 
MODE EXCEPTOBJS = [0]EXCEPTOBJ;
 
OP STR = (EXCEPTOBJS obj)STRING: (
STRING out := "(", fs := "";
FOR this FROM LWB obj TO UPB obj DO out +:= fs+FIRMSTR obj[this]; fs:=", " OD;
out +")"
);
 
MODE EXCEPTMEND = PROC(EXCEPTOBJS #obj#,STRING #msg#)BOOL;
 
PROC super mend = (EXCEPTOBJS obj,STRING sub exception, msg)BOOL:
( put(stand error, ("exception/",sub exception,": ", msg," - ", STR obj, new line)); break; TRUE);
 
PROC super break mend = (EXCEPTOBJS obj,STRING sub exception, msg)BOOL: ( super mend(obj, sub exception, msg); break; TRUE);
PROC super stop mend = (EXCEPTOBJS obj,STRING sub exception, msg)BOOL: ( super mend(obj, sub exception, msg); stop; FALSE);
PROC super ignore mend = (EXCEPTOBJS obj,STRING sub exception, msg)BOOL: ( #super mend(obj, sub exception, msg);# TRUE);
 
EXCEPTMEND on undefined mend := super break mend(,"undefined",);
PROC on undefined = (EXCEPTMEND undefined mend)VOID: on undefined mend := undefined mend;
PROC raise undefined = (EXCEPTOBJS obj, STRING msg)VOID: IF NOT on undefined mend(obj, msg) THEN stop FI;
 
EXCEPTMEND on value error mend := super break mend(,"value error",);
PROC on value error = (EXCEPTMEND value error mend)VOID: on value error mend := value error mend;
PROC raise value error = (EXCEPTOBJS obj, STRING msg)VOID: IF NOT on value error mend(obj, msg) THEN stop FI;
 
EXCEPTMEND on bounds error mend := super break mend(,"bounds error",);
PROC on bounds error = (EXCEPTMEND bounds error mend)VOID: on bounds error mend := bounds error mend;
PROC raise bounds error = (EXCEPTOBJS obj, STRING msg)VOID: IF NOT on bounds error mend(obj, msg) THEN stop FI;
 
EXCEPTMEND on tagged union error mend := super break mend(,"tagged union error",);
PROC on tagged union error = (EXCEPTMEND tagged union error mend)VOID: on tagged union error mend := tagged union error mend;
PROC raise tagged union error = (EXCEPTOBJS obj, STRING msg)VOID: IF NOT on tagged union error mend(obj, msg) THEN stop FI;
 
EXCEPTMEND on untested mend := super break mend(,"untested",);
PROC on untested = (EXCEPTMEND untested mend)VOID: on untested mend := untested mend;
PROC raise untested = (EXCEPTOBJS obj, STRING msg)VOID: IF NOT on untested mend(obj, msg) THEN stop FI;
 
EXCEPTMEND on unimplemented mend := super break mend(,"unimplemented",);
PROC on unimplemented = (EXCEPTMEND unimplemented mend)VOID: on unimplemented mend := unimplemented mend;
PROC raise unimplemented = (EXCEPTOBJS obj, STRING msg)VOID: IF NOT on unimplemented mend(obj, msg) THEN stop FI;
 
SKIP
File: test/Dragon_curve.a68
#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
 
PR read "prelude/turtle_draw.a68" PR;
MODE EXCEPTOBJ = FILE;
OP FIRMSTR = (EXCEPTOBJ obj)STRING: "FILE";
 
PR read "prelude/exception.a68" PR;
 
REAL sqrt 2 = sqrt(2), degrees = pi/180;
 
STRUCT ( INT count, depth, current shade, upb lines, upb colours ) morph;
 
PROC morph init = (INT depth)VOID: (
count OF morph := 0;
depth OF morph := depth;
current shade OF morph := -1;
upb lines OF morph := 2**depth;
upb colours OF morph := 16
);
 
PROC morph colour = VOID: (
INT colour sectors = 3; # RGB #
INT candidate shade = ENTIER ( count OF morph / upb lines OF morph * upb colours OF morph );
IF candidate shade /= current shade OF morph THEN
current shade OF morph := candidate shade;
REAL colour sector = colour sectors * candidate shade / upb colours OF morph - 0.5;
REAL shade = colour sector - ENTIER colour sector;
CASE ENTIER colour sector + 1 # of 3 # IN
draw colour (window, 1 - shade, shade, 0),
draw colour (window, 0, 1 - shade, shade)
OUT
draw colour (window, shade, 0, 1 - shade)
ESAC
FI;
count OF morph +:= 1
);
 
PROC dragon init = VOID: (
pen down OF turtle := FALSE;
turtle forward(23/64); turtle right(90*degrees);
turtle forward (1/8); turtle right(90*degrees);
pen down OF turtle := TRUE
);
 
PROC dragon = (REAL in step, in length, PROC(REAL)VOID zig, zag)VOID: (
IF in step <= 0 THEN
morph colour;
turtle forward(in length)
ELSE
REAL step = in step - 1;
REAL length = in length / sqrt 2;
 
zig(45*degrees);
dragon(step, length, turtle right, turtle left);
zag(90*degrees);
dragon(step, length, turtle left, turtle right);
zig(45*degrees)
FI
);
 
PROC window init = VOID: (
STRING aspect; FILE f; associate(f, aspect); putf(f, ($g(-4)"x"g(-3)$, width, height));
CO # depricated #
IF NOT draw device (window, "X", aspect)THEN
raise undefined(window, "cannot initialise X draw device") FI;
END CO
IF open (window, "Dragon Curve", stand draw channel) = 0 THEN
raise undefined(window, "cannot open Dragon Curve window") FI;
IF NOT make device (window, "X", aspect) THEN
raise undefined(window, "cannot make device X draw device") FI
);
 
INT width = 800-15, height = 600-15;
 
FILE window; window init;
INT cycle length = 18;
FOR snap shot TO cycle length DO
INT depth := (snap shot - 2) MOD cycle length;
turtle init; dragon init; morph init(depth);
# move to initial turtle location #
dragon(depth, 7/8, turtle right, turtle left);
draw show (window);
VOID(system("sleep 1"))
OD;
close (window)

Output:

ALGOL 68 Dragon curve animated

Note: each Dragon curve is composed of many smaller dragon curves (shown in a different colour).

[edit] Asymptote

The Asymptote source code includes an examples/dragon.asy which draws the dragon curve (four interlocking copies actually),

http://asymptote.sourceforge.net/gallery/dragon.asy
http://asymptote.sourceforge.net/gallery/dragon.pdf

As of its version 2.15 it uses the successive approximation method. Vertices are represented as an array of "pairs" (complex numbers). Between each two vertices a new vertex is is introduced so as to double the segments, repeated to a desired level.

[edit] AutoHotkey

See: Dragon curve/AutoHotkey

[edit] BASIC

Works with: QBasic
DIM SHARED angle AS DOUBLE
 
SUB turn (degrees AS DOUBLE)
angle = angle + degrees*3.14159265/180
END SUB
 
SUB forward (length AS DOUBLE)
LINE - STEP (COS(angle)*length, SIN(angle)*length), 7
END SUB
 
SUB dragon (length AS DOUBLE, split AS INTEGER, d AS DOUBLE)
IF split=0 THEN
forward length
ELSE
turn d*45
dragon length/1.4142136, split-1, 1
turn -d*90
dragon length/1.4142136, split-1, -1
turn d*45
END IF
END SUB
 
' Main program
 
SCREEN 12
angle = 0
PSET (150,180), 0
dragon 400, 12, 1
SLEEP


See also Sydney Afriat "Dragon Curves" paper for various approaches in BASIC

[edit] BASIC256

Image created by the BASIC-256 script
# Version without functions (for BASIC-256 ver. 0.9.6.66)
 
graphsize 390,270
 
level = 18 : insize = 247 # initial values
x = 92 : y = 94 #
 
iters = 2^level # total number of iterations
qiter = 510/iters # constant for computing colors
SQ = sqrt(2) : QPI = pi/4 # constants
 
rotation = 0 : iter = 0 : rq = 1.0 # state variables
dim rqs(level) # stack for rq (rotation coefficient)
 
color white
fastgraphics
rect 0,0,graphwidth,graphheight
refresh
gosub dragon
refresh
imgsave "Dragon_curve_BASIC-256.png", "PNG"
end
 
dragon:
if level<=0 then
yn = sin(rotation)*insize + y
xn = cos(rotation)*insize + x
if iter*2<iters then
color 0,iter*qiter,255-iter*qiter
else
color qiter*iter-255,(iters-iter)*qiter,0
end if
line x,y,xn,yn
iter = iter + 1
x = xn : y = yn
return
end if
insize = insize/SQ
rotation = rotation + rq*QPI
level = level - 1
rqs[level] = rq : rq = 1
gosub dragon
rotation = rotation - rqs[level]*QPI*2
rq = -1
gosub dragon
rq = rqs[level]
rotation = rotation + rq*QPI
level = level + 1
insize = insize*SQ
return

[edit] BBC BASIC

      MODE 8
MOVE 800,400
GCOL 11
PROCdragon(512, 12, 1)
END
 
DEF PROCdragon(size, split%, d)
PRIVATE angle
IF split% = 0 THEN
DRAW BY -COS(angle)*size, SIN(angle)*size
ELSE
angle += d*PI/4
PROCdragon(size/SQR(2), split%-1, 1)
angle -= d*PI/2
PROCdragon(size/SQR(2), split%-1, -1)
angle += d*PI/4
ENDIF
ENDPROC

[edit] C

See: Dragon curve/C

[edit] C by IFS Drawing

Dragon-C.png

C code that writes PNM of dragon curve. run as a.out [depth] > dragon.pnm. Sample image was with depth 9 (512 pixel length).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
/* x, y: coordinates of current point; dx, dy: direction of movement.
* Think turtle graphics. They are divided by scale, so as to keep
* very small coords/increments without losing precission. clen is
* the path length travelled, which should equal to scale at the end
* of the curve.
*/

long long x, y, dx, dy, scale, clen;
typedef struct { double r, g, b; } rgb;
rgb ** pix;
 
/* for every depth increase, rotate 45 degrees and scale up by sqrt(2)
* Note how coords can still be represented by integers.
*/

void sc_up()
{
long long tmp = dx - dy; dy = dx + dy; dx = tmp;
scale *= 2; x *= 2; y *= 2;
}
 
/* Hue changes from 0 to 360 degrees over entire length of path; Value
* oscillates along the path to give some contrast between segments
* close to each other spatially. RGB derived from HSV gets *added*
* to each pixel reached; they'll be dealt with later.
*/

void h_rgb(long long x, long long y)
{
rgb *p = &pix[y][x];
 
# define SAT 1
double h = 6.0 * clen / scale;
double VAL = 1 - (cos(3.141592653579 * 64 * clen / scale) - 1) / 4;
double c = SAT * VAL;
double X = c * (1 - fabs(fmod(h, 2) - 1));
 
switch((int)h) {
case 0: p->r += c; p->g += X; return;
case 1: p->r += X; p->g += c; return;
case 2: p->g += c; p->b += X; return;
case 3: p->g += X; p->b += c; return;
case 4: p->r += X; p->b += c; return;
default:
p->r += c; p->b += X;
}
}
 
/* string rewriting. No need to keep the string itself, just execute
* its instruction recursively.
*/

void iter_string(const char * str, int d)
{
long tmp;
# define LEFT tmp = -dy; dy = dx; dx = tmp
# define RIGHT tmp = dy; dy = -dx; dx = tmp
while (*str != '\0') {
switch(*(str++)) {
case 'X': if (d) iter_string("X+YF+", d - 1); continue;
case 'Y': if (d) iter_string("-FX-Y", d - 1); continue;
case '+': RIGHT; continue;
case '-': LEFT; continue;
case 'F':
/* draw: increment path length; add color; move. Here
* is why the code does not allow user to choose arbitrary
* image size: if it's not a power of two, aliasing will
* occur and grid-like bright or dark lines will result
* when normalized later. It can be gotten rid of, but that
* involves computing multiplicative order and would be a huge
* bore.
*/

clen ++;
h_rgb(x/scale, y/scale);
x += dx; y += dy;
continue;
}
}
}
 
void dragon(long leng, int depth)
{
long i, d = leng / 3 + 1;
long h = leng + 3, w = leng + d * 3 / 2 + 2;
 
/* allocate pixel buffer */
rgb *buf = malloc(sizeof(rgb) * w * h);
pix = malloc(sizeof(rgb *) * h);
for (i = 0; i < h; i++)
pix[i] = buf + w * i;
memset(buf, 0, sizeof(rgb) * w * h);
 
/* init coords; scale up to desired; exec string */
x = y = d; dx = leng; dy = 0; scale = 1; clen = 0;
for (i = 0; i < depth; i++) sc_up();
iter_string("FX", depth);
 
/* write color PNM file */
unsigned char *fpix = malloc(w * h * 3);
double maxv = 0, *dbuf = (double*)buf;
 
/* find highest value among pixels; normalize image according
* to it. Highest value would be at points most travelled, so
* this ends up giving curve edge a nice fade -- it's more apparaent
* if we increase iteration depth by one or two.
*/

for (i = 3 * w * h - 1; i >= 0; i--)
if (dbuf[i] > maxv) maxv = dbuf[i];
for (i = 3 * h * w - 1; i >= 0; i--)
fpix[i] = 255 * dbuf[i] / maxv;
 
printf("P6\n%ld %ld\n255\n", w, h);
fflush(stdout); /* printf and fwrite may treat buffer differently */
fwrite(fpix, h * w * 3, 1, stdout);
}
 
int main(int c, char ** v)
{
int size, depth;
 
depth = (c > 1) ? atoi(v[1]) : 10;
size = 1 << depth;
 
fprintf(stderr, "size: %d depth: %d\n", size, depth);
dragon(size, depth * 2);
 
return 0;
}

[edit] C++

DragonCpp.png

This program will generate the curve and save it to your hard drive.

 
#include <windows.h>
#include <iostream>
 
//-----------------------------------------------------------------------------------------
using namespace std;
 
//-----------------------------------------------------------------------------------------
const int BMP_SIZE = 800, NORTH = 1, EAST = 2, SOUTH = 4, WEST = 8, LEN = 1;
 
//-----------------------------------------------------------------------------------------
class myBitmap
{
public:
myBitmap() : pen( NULL ), brush( NULL ), clr( 0 ), wid( 1 ) {}
~myBitmap()
{
DeleteObject( pen ); DeleteObject( brush );
DeleteDC( hdc ); DeleteObject( bmp );
}
 
bool create( int w, int h )
{
BITMAPINFO bi;
ZeroMemory( &bi, sizeof( bi ) );
bi.bmiHeader.biSize = sizeof( bi.bmiHeader );
bi.bmiHeader.biBitCount = sizeof( DWORD ) * 8;
bi.bmiHeader.biCompression = BI_RGB;
bi.bmiHeader.biPlanes = 1;
bi.bmiHeader.biWidth = w;
bi.bmiHeader.biHeight = -h;
 
HDC dc = GetDC( GetConsoleWindow() );
bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 );
if( !bmp ) return false;
 
hdc = CreateCompatibleDC( dc );
SelectObject( hdc, bmp );
ReleaseDC( GetConsoleWindow(), dc );
 
width = w; height = h;
return true;
}
 
void clear( BYTE clr = 0 )
{
memset( pBits, clr, width * height * sizeof( DWORD ) );
}
 
void setBrushColor( DWORD bClr )
{
if( brush ) DeleteObject( brush );
brush = CreateSolidBrush( bClr );
SelectObject( hdc, brush );
}
 
void setPenColor( DWORD c )
{
clr = c; createPen();
}
 
void setPenWidth( int w )
{
wid = w; createPen();
}
 
void saveBitmap( string path )
{
BITMAPFILEHEADER fileheader;
BITMAPINFO infoheader;
BITMAP bitmap;
DWORD wb;
 
GetObject( bmp, sizeof( bitmap ), &bitmap );
DWORD* dwpBits = new DWORD[bitmap.bmWidth * bitmap.bmHeight];
 
ZeroMemory( dwpBits, bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD ) );
ZeroMemory( &infoheader, sizeof( BITMAPINFO ) );
ZeroMemory( &fileheader, sizeof( BITMAPFILEHEADER ) );
 
infoheader.bmiHeader.biBitCount = sizeof( DWORD ) * 8;
infoheader.bmiHeader.biCompression = BI_RGB;
infoheader.bmiHeader.biPlanes = 1;
infoheader.bmiHeader.biSize = sizeof( infoheader.bmiHeader );
infoheader.bmiHeader.biHeight = bitmap.bmHeight;
infoheader.bmiHeader.biWidth = bitmap.bmWidth;
infoheader.bmiHeader.biSizeImage = bitmap.bmWidth * bitmap.bmHeight * sizeof( DWORD );
 
fileheader.bfType = 0x4D42;
fileheader.bfOffBits = sizeof( infoheader.bmiHeader ) + sizeof( BITMAPFILEHEADER );
fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage;
 
GetDIBits( hdc, bmp, 0, height, ( LPVOID )dwpBits, &infoheader, DIB_RGB_COLORS );
 
HANDLE file = CreateFile( path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL );
WriteFile( file, &fileheader, sizeof( BITMAPFILEHEADER ), &wb, NULL );
WriteFile( file, &infoheader.bmiHeader, sizeof( infoheader.bmiHeader ), &wb, NULL );
WriteFile( file, dwpBits, bitmap.bmWidth * bitmap.bmHeight * 4, &wb, NULL );
CloseHandle( file );
 
delete [] dwpBits;
}
 
HDC getDC() const { return hdc; }
int getWidth() const { return width; }
int getHeight() const { return height; }
 
private:
void createPen()
{
if( pen ) DeleteObject( pen );
pen = CreatePen( PS_SOLID, wid, clr );
SelectObject( hdc, pen );
}
 
HBITMAP bmp;
HDC hdc;
HPEN pen;
HBRUSH brush;
void *pBits;
int width, height, wid;
DWORD clr;
};
//-----------------------------------------------------------------------------------------
class dragonC
{
public:
dragonC() { bmp.create( BMP_SIZE, BMP_SIZE ); dir = WEST; }
void draw( int iterations ) { generate( iterations ); draw(); }
 
private:
void generate( int it )
{
generator.push_back( 1 );
string temp;
 
for( int y = 0; y < it - 1; y++ )
{
temp = generator; temp.push_back( 1 );
for( string::reverse_iterator x = generator.rbegin(); x != generator.rend(); x++ )
temp.push_back( !( *x ) );
 
generator = temp;
}
}
 
void draw()
{
HDC dc = bmp.getDC();
unsigned int clr[] = { 0xff, 0xff00, 0xff0000, 0x00ffff };
int mov[] = { 0, 0, 1, -1, 1, -1, 1, 0 }; int i = 0;
 
for( int t = 0; t < 4; t++ )
{
int a = BMP_SIZE / 2, b = a; a += mov[i++]; b += mov[i++];
MoveToEx( dc, a, b, NULL );
 
bmp.setPenColor( clr[t] );
for( string::iterator x = generator.begin(); x < generator.end(); x++ )
{
switch( dir )
{
case NORTH:
if( *x ) { a += LEN; dir = EAST; }
else { a -= LEN; dir = WEST; }
break;
case EAST:
if( *x ) { b += LEN; dir = SOUTH; }
else { b -= LEN; dir = NORTH; }
break;
case SOUTH:
if( *x ) { a -= LEN; dir = WEST; }
else { a += LEN; dir = EAST; }
break;
case WEST:
if( *x ) { b -= LEN; dir = NORTH; }
else { b += LEN; dir = SOUTH; }
}
LineTo( dc, a, b );
}
}
// !!! change this path !!!
bmp.saveBitmap( "f:/rc/dragonCpp.bmp" );
}
 
int dir;
myBitmap bmp;
string generator;
};
//-----------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
dragonC d; d.draw( 17 );
return system( "pause" );
}
//-----------------------------------------------------------------------------------------
 

[edit] Common Lisp

Library: CLIM

This implementation uses nested transformations rather than turtle motions. with-scaling, etc. establish transformations for the drawing which occurs within them.

The recursive dragon-part function draws a curve connecting (0,0) to (1,0); if depth is 0 then the curve is a straight line. bend-direction is either 1 or -1 to specify whether the deviation from a straight line should be to the right or left.

(defpackage #:dragon
(:use #:clim-lisp #:clim)
(:export #:dragon #:dragon-part))
(in-package #:dragon)
 
(defun dragon-part (depth bend-direction)
(if (zerop depth)
(draw-line* *standard-output* 0 0 1 0)
(with-scaling (t (/ (sqrt 2)))
(with-rotation (t (* pi -1/4 bend-direction))
(dragon-part (1- depth) 1)
(with-translation (t 1 0)
(with-rotation (t (* pi 1/2 bend-direction))
(dragon-part (1- depth) -1)))))))
 
(defun dragon (&optional (depth 7) (size 100))
(with-room-for-graphics ()
(with-scaling (t size)
(dragon-part depth 1))))

[edit] D

[edit] Text mode

A textual version of Dragon curve.
The Dragon curve drawn using an L-system.

  • variables : X Y F
  • constants : + −
  • start  : FX
  • rules  : (X → X+YF+),(Y → -FX-Y)
  • angle  : 90°
import std.stdio, std.string;
 
struct Board {
enum char spc = ' ';
char[][] b = [[' ']]; // Set at least 1x1 board.
int shiftx, shifty;
 
void clear() pure nothrow {
shiftx = shifty = 0;
b = [['\0']];
}
 
void check(in int x, in int y) pure nothrow {
while (y + shifty < 0) {
auto newr = new char[b[0].length];
newr[] = spc;
b = newr ~ b;
shifty++;
}
 
while (y + shifty >= b.length) {
auto newr = new char[b[0].length];
newr[] = spc;
b ~= newr;
}
 
while (x + shiftx < 0) {
foreach (ref c; b)
c = [spc] ~ c;
shiftx++;
}
 
while (x + shiftx >= b[0].length)
foreach (ref c; b)
c ~= [spc];
}
 
char opIndexAssign(in char value, in int x, in int y)
pure nothrow {
check(x, y);
b[y + shifty][x + shiftx] = value;
return value;
}
 
string toString() const pure {
return format("%-(%s\n%)", b);
}
}
 
struct Turtle {
static struct TState {
int[2] xy;
int heading;
}
 
enum int[2][] dirs = [[1, 0], [1, 1], [0, 1], [-1, 1],
[-1, 0], [-1, -1], [0, -1], [1, -1]];
enum string trace = r"-\|/-\|/";
TState t;
 
void reset() pure nothrow {
t = typeof(t).init;
}
 
void turn(in int dir) pure nothrow {
t.heading = (t.heading + 8 + dir) % 8;
}
 
void forward(ref Board b) pure nothrow {
with (t) {
xy[] += dirs[heading][];
b[xy[0], xy[1]] = trace[heading];
xy[] += dirs[heading][];
b[xy[0], xy[1]] = b.spc;
}
}
}
 
void dragonX(in int n, ref Turtle t, ref Board b) pure nothrow {
if (n >= 0) { // X -> X+YF+
dragonX(n - 1, t, b);
t.turn(2);
dragonY(n - 1, t, b);
t.forward(b);
t.turn(2);
}
}
 
void dragonY(in int n, ref Turtle t, ref Board b) pure nothrow {
if (n >= 0) { // Y -> -FX-Y
t.turn(-2);
t.forward(b);
dragonX(n - 1, t, b);
t.turn(-2);
dragonY(n - 1, t, b);
}
}
 
void main() {
Turtle t;
Board b;
// Seed : FX
t.forward(b); // <- F
dragonX(7, t, b); // <- X
writeln(b);
}
Output:
           -   -           -   -               
          | | | |         | | | |              
         - - - -         - - - -               
        | | | |         | | | |                
         -   - -   -     -   - -   -           
              | | | |         | | | |          
             - - - -         - - - -           
            | | | |         | | | |            
   -   -   - - - - -   -   - - - -             
  | | | | | | | | | | | | | | | |              
 - - - - -   - - -   - - - - - -               
| | | | |     | |     | | | | |                
 -   - - -     - -     - - - - -   -           
      | | |     | |     | | | | | | |          
     -   -       -     - - - - - - -           
    |                 | | | | | | |            
   - -                 - - - - - -             
  | | |                 | | | | |              
 - - -                 - -   - -           -   
| | |                 | |     |           | |  
 -   -     -           - -     -   -         - 
      |     |           | |     | | |         |
     - -   -             -     - - -         - 
    | | | |                   | | |         |  
     -   -                     - - -   -   - - 
                                | | | | | | | |
                               - -   - - -   - 
                              | |     | |      
                               - -     - -     
                                | |     | |    
                                 -       -     

[edit] PostScript Output Version

Translation of: Haskell
import std.stdio, std.string;
 
string drx(in size_t n) pure nothrow {
return n ? (drx(n - 1) ~ " +" ~ dry(n - 1) ~ " f +") : "";
}
 
string dry(in size_t n) pure nothrow {
return n ? (" - f" ~ drx(n - 1) ~ " -" ~ dry(n - 1)) : "";
}
 
string dragonCurvePS(in size_t n) pure nothrow {
return ["0 setlinewidth 300 400 moveto",
"/f{2 0 rlineto}def/+{90 rotate}def/-{-90 rotate}def\n",
"f", drx(n), " stroke showpage"].join();
}
 
void main() {
writeln(dragonCurvePS(9)); // Increase this for a bigger curve.
}

[edit] On a Bitmap

This uses the modules from the bresenhams line algorithm and Grayscale Image tasks.

First a small "turtle.d" module, useful for other tasks:

module turtle;
 
import bitmap_bresenhams_line_algorithm, grayscale_image, std.math;
 
// Minimal turtle graphics.
struct Turtle {
real x = 100, y = 100, angle = -90;
 
void left(in real a) pure nothrow { angle -= a; }
void right(in real a) pure nothrow { angle += a; }
 
void forward(Color)(Image!Color img, in real len) pure nothrow {
immutable r = angle * (PI / 180.0);
immutable dx = r.cos * len;
immutable dy = r.sin * len;
img.drawLine(cast(uint)x, cast(uint)y,
cast(uint)(x + dx), cast(uint)(y + dy),
Color.white);
x += dx;
y += dy;
}
}

Then the implementation is simple:

Translation of: PicoLisp
import grayscale_image, turtle;
 
void drawDragon(Color)(Image!Color img, ref Turtle t, in uint depth,
in real dir, in uint step) {
if (depth == 0)
return t.forward(img, step);
t.right(dir);
img.drawDragon(t, depth - 1, 45.0, step);
t.left(dir * 2);
img.drawDragon(t, depth - 1, -45.0, step);
t.right(dir);
}
 
void main() {
auto img = new Image!Gray(500, 700);
auto t = Turtle(180, 510, -90);
img.drawDragon(t, 14, 45.0, 3);
img.savePGM("dragon_curve.pgm");
}

[edit] With QD

See: Dragon curve/D/QD

[edit] With DFL

See: Dragon curve/D/DFL

[edit] Emacs Lisp

Drawing ascii art characters into a buffer using picture-mode

(require 'cl) ;; Emacs 22 and earlier for `ignore-errors'
 
(defun dragon-ensure-line-above ()
"If point is in the first line of the buffer then insert a new line above."
(when (= (line-beginning-position) (point-min))
(save-excursion
(goto-char (point-min))
(insert "\n"))))
 
(defun dragon-ensure-column-left ()
"If point is in the first column then insert a new column to the left.
This is designed for use in `picture-mode'."

(when (zerop (current-column))
(save-excursion
(goto-char (point-min))
(insert " ")
(while (= 0 (forward-line 1))
(insert " ")))
(picture-forward-column 1)))
 
(defun dragon-insert-char (char len)
"Insert CHAR repeated LEN many times.
After each CHAR point move in the current `picture-mode'
direction (per `picture-set-motion' etc).
 
This is the same as `picture-insert' except in column 0 or row 0
a new row or column is inserted to make room, with existing
buffer contents shifted down or right."

 
(dotimes (i len)
(dragon-ensure-line-above)
(dragon-ensure-column-left)
(picture-insert char 1)))
 
(defun dragon-bit-above-lowest-0bit (n)
"Return the bit above the lowest 0-bit in N.
For example N=43 binary \"101011\" has lowest 0-bit at \"...0..\"
and the bit above that is \"..1...\" so return 8 which is that
bit."

(logand n (1+ (logxor n (1+ n)))))
 
(defun dragon-next-turn-right-p (n)
"Return non-nil if the dragon curve should turn right after segment N.
Segments are numbered from N=0 for the first, so calling with N=0
is whether to turn right after drawing that N=0 segment."

(zerop (dragon-bit-above-lowest-0bit n)))
 
(defun dragon-picture (len step)
"Draw the dragon curve in a *dragon* buffer.
LEN is the number of segments of the curve to draw.
STEP is the length of each segment, in characters.
 
Any LEN can be given but a power-of-2 such as 256 shows the
self-similar nature of the curve.
 
If STEP >= 2 then the segments are lines using \"-\" or \"|\"
characters (`picture-rectangle-h' and `picture-rectangle-v').
If STEP=1 then only \"+\" corners.
 
There's a `sit-for' delay in the drawing loop to draw the curve
progressively on screen."

 
(interactive (list (read-number "Length of curve " 256)
(read-number "Each step size " 3)))
(unless (>= step 1)
(error "Step length must be >= 1"))
 
(switch-to-buffer "*dragon*")
(erase-buffer)
(ignore-errors ;; if already in picture-mode
(picture-mode))
 
(dotimes (n len) ;; n=0 to len-1, inclusive
(dragon-insert-char ?+ 1) ;; corner char
(dragon-insert-char (if (zerop picture-vertical-step)
picture-rectangle-h picture-rectangle-v)
(1- step)) ;; line chars
 
(if (dragon-next-turn-right-p n)
;; turn right
(picture-set-motion (- picture-horizontal-step) picture-vertical-step)
;; turn left
(picture-set-motion picture-horizontal-step (- picture-vertical-step)))
 
;; delay to display the drawing progressively
(sit-for .01))
 
(picture-insert ?+ 1) ;; endpoint
(picture-mode-exit)
(goto-char (point-min)))
 
(dragon-picture 128 2)
     +-+ +-+
     | | | |
     +-+-+ +-+
       |     |
 +-+ +-+   +-+
 | | |
 +-+-+-+
   | | |
   +-+-+
     |
     +-+ +-+     +-+     +-+
       | | |     | |     | |
 +-+ +-+-+-+   +-+-+   +-+-+
 | | | | |     | |     | |
 +-+-+-+-+-+ +-+-+-+ +-+-+-+ +-+
   | | | | | | | | | | | | | | |
   +-+ +-+ +-+-+-+-+-+ +-+ +-+-+
             | | | |         |
             +-+-+-+-+       +-+
               | | | |         |
         +-+ +-+-+ +-+     + +-+
         | | | |           | |
         +-+-+-+-+         +-+
           | | | |
           +-+ +-+

[edit] F#

Using for visualization:
open System.Windows
open System.Windows.Media
 
let m = Matrix(0.0, 0.5, -0.5, 0.0, 0.0, 0.0)
 
let step segs =
seq { for a: Point, b: Point in segs do
let x = a + 0.5 * (b - a) + (b - a) * m
yield! [a, x; b, x] }
 
let rec nest n f x =
if n=0 then x else nest (n-1) f (f x)
 
[<System.STAThread>]
do
let path = Shapes.Path(Stroke=Brushes.Black, StrokeThickness=0.001)
path.Data <-
PathGeometry
[ for a, b in nest 13 step (seq [Point(0.0, 0.0), Point(1.0, 0.0)]) ->
PathFigure(a, [(LineSegment(b, true) :> PathSegment)], false) ]
(Application()).Run(Window(Content=Controls.Viewbox(Child=path))) |> ignore

[edit] Factor

A translation of the BASIC example, using OpenGL, drawing with HSV coloring similar to the C example.

 
USING: accessors colors colors.hsv fry kernel locals math
math.constants math.functions opengl.gl typed ui ui.gadgets
ui.gadgets.canvas ui.render ;
 
IN: dragon
 
CONSTANT: depth 12
 
TUPLE: turtle
{ angle fixnum }
{ color float }
{ x float }
{ y float } ;
 
TYPED: nxt-color ( turtle: turtle -- turtle )
[ [ 360 2 depth ^ /f + ] keep
1.0 1.0 1.0 <hsva> >rgba-components glColor4d
] change-color ; inline
 
TYPED: draw-fwd ( x1: float y1: float x2: float y2: float -- )
GL_LINES glBegin glVertex2d glVertex2d glEnd ; inline
 
TYPED:: fwd ( turtle: turtle l: float -- )
turtle x>>
turtle y>>
turtle angle>> pi * 180 / :> ( x y angle )
l angle [ cos * x + ] [ sin * y + ] 2bi :> ( dx dy )
turtle x y dx dy [ draw-fwd ] 2keep [ >>x ] [ >>y ] bi* drop ; inline
 
TYPED: trn ( turtle: turtle d: fixnum -- turtle )
'[ _ + ] change-angle ; inline
 
TYPED:: dragon' ( turtle: turtle l: float s: fixnum d: fixnum -- )
s zero? [
turtle nxt-color l fwd ! don't like this drop
] [
turtle d 45 * trn l 2 sqrt / s 1 - 1 dragon'
turtle d -90 * trn l 2 sqrt / s 1 - -1 dragon'
turtle d 45 * trn drop
] if ;
 
: dragon ( -- )
0 0 150 180 turtle boa 400 depth 1 dragon' ;
 
TUPLE: dragon-canvas < canvas ;
 
M: dragon-canvas draw-gadget* [ drop dragon ] draw-canvas ;
M: dragon-canvas pref-dim* drop { 640 480 } ;
 
MAIN-WINDOW: dragon-window { { title "Dragon Curve" } }
dragon-canvas new-canvas >>gadgets ;
 
MAIN: dragon-window
 

[edit] Forth

Works with: bigFORTH
include turtle.fs
 
2 value dragon-step
 
: dragon ( depth dir -- )
over 0= if dragon-step fd 2drop exit then
dup rt
over 1- 45 recurse
dup 2* lt
over 1- -45 recurse
rt drop ;
 
home clear
10 45 dragon
Works with: 4tH

Basically the same code as the BigForth version.

Output png
include lib/graphics.4th
include lib/gturtle.4th
 
2 constant dragon-step
 
: dragon ( depth dir -- )
over 0= if dragon-step forward 2drop exit then
dup right
over 1- 45 recurse
dup 2* left
over 1- -45 recurse
right drop ;
 
150 pic_width !
210 pic_height !
color_image
 
clear-screen 50 95 turtle!
xpendown 13 45 dragon
s" 4tHdragon.ppm" save_image

[edit] gnuplot

Implemented by "parametric" mode running an index t through the desired number of curve segments with X,Y position calculated for each. The "lines" plot joins them up.

# Return the position of the highest 1-bit in n.
# The least significant bit is position 0.
# For example n=13 is binary "1101" and the high bit is pos=3.
# If n==0 then the return is 0.
# Arranging the test as n>=2 avoids infinite recursion if n==NaN (any
# comparison involving NaN is always false).
#
high_bit_pos(n) = (n>=2 ? 1+high_bit_pos(int(n/2)) : 0)
 
# Return 0 or 1 for the bit at position "pos" in n.
# pos==0 is the least significant bit.
#
bit(n,pos) = int(n / 2**pos) & 1
 
# dragon(n) returns a complex number which is the position of the
# dragon curve at integer point "n". n=0 is the first point and is at
# the origin {0,0}. Then n=1 is at {1,0} which is x=1,y=0, etc. If n
# is not an integer then the point returned is for int(n).
#
# The calculation goes by bits of n from high to low. Gnuplot doesn't
# have iteration in functions, but can go recursively from
# pos=high_bit_pos(n) down to pos=0, inclusive.
#
# mul() rotates by +90 degrees (complex "i") at bit transitions 0->1
# or 1->0. add() is a vector (i+1)**pos for each 1-bit, but turned by
# factor "i" when in a "reversed" section of curve, which is when the
# bit above is also a 1-bit.
#
dragon(n) = dragon_by_bits(n, high_bit_pos(n))
dragon_by_bits(n,pos) \
= (pos>=0 ? add(n,pos) + mul(n,pos)*dragon_by_bits(n,pos-1) : 0)
 
add(n,pos) = (bit(n,pos) ? (bit(n,pos+1) ? {0,1} * {1,1}**pos \
: {1,1}**pos) \
: 0)
mul(n,pos) = (bit(n,pos) == bit(n,pos+1) ? 1 : {0,1})
 
# Plot the dragon curve from 0 to "length" with line segments.
# "trange" and "samples" are set so the parameter t runs through
# integers t=0 to t=length inclusive.
#
# Any trange works, it doesn't have to start at 0. But must have
# enough "samples" that all integers t in the range are visited,
# otherwise vertices in the curve would be missed.
#
length=256
set trange [0:length]
set samples length+1
set parametric
set key off
plot real(dragon(t)),imag(dragon(t)) with lines

[edit] Gri

Recursively by a dragon curve comprising two smaller dragons drawn towards a midpoint.

`Draw Dragon [ from .x1. .y1. to .x2. .y2. [level .level.] ]'
Draw a dragon curve going from .x1. .y1. to .x2. .y2. with recursion
depth .level.
 
The total number of line segments for the recursion is 2^level.
level=0 is a straight line from x1,y1 to x2,y2.
 
The default for x1,y1 and x2,y2 is to draw horizontally from 0,0
to 1,0.
{
new .x1. .y1. .x2. .y2. .level.
.x1. = \.word3.
.y1. = \.word4.
.x2. = \.word6.
.y2. = \.word7.
.level. = \.word9.
 
if {rpn \.words. 5 >=}
.x2. = 1
.y2. = 0
end if
if {rpn \.words. 7 >=}
.level. = 6
end if
 
if {rpn 0 .level. <=}
draw line from .x1. .y1. to .x2. .y2.
else
.level. = {rpn .level. 1 -}
 
# xmid,ymid is half way between x1,y1 and x2,y2 and up at
# right angles away.
#
# xmid,ymid xmid = (x1+x2 + y2-y1)/2
# ^ ^ ymid = (x1-x2 + y1+y2)/2
# / . \
# / . \
# x1,y1 ........... x2,y2
#
new .xmid. .ymid.
.xmid. = {rpn .x1. .x2. + .y2. .y1. - + 2 /}
.ymid. = {rpn .x1. .x2. - .y1. .y2. + + 2 /}
 
# The recursion is a level-1 dragon from x1,y1 to the midpoint
# and the same from x2,y2 to the midpoint (the latter
# effectively being a revered dragon.)
#
Draw Dragon from .x1. .y1. to .xmid. .ymid. level .level.
Draw Dragon from .x2. .y2. to .xmid. .ymid. level .level.
 
delete .xmid. .ymid.
end if
 
delete .x1. .y1. .x2. .y2. .level.
}
 
# Dragon curve from 0,0 to 1,0 extends out by 1/3 at the ends, so
# extents -0.5 to +1.5 for a bit of margin. The Y extent is the same
# size 2 to make the graph square.
set x axis -0.5 1.5 .25
set y axis -1 1 .25
 
Draw Dragon

[edit] Go

Output png

Version using standard image libriary is an adaptation of the version below using the Bitmap task. The only major change is that line drawing code was needed. See comments in code.

package main
 
import (
"fmt"
"image"
"image/color"
"image/draw"
"image/png"
"math"
"os"
)
 
// separation of the the two endpoints
// make this a power of 2 for prettiest output
const sep = 512
// depth of recursion. adjust as desired for different visual effects.
const depth = 14
 
var s = math.Sqrt2 / 2
var sin = []float64{0, s, 1, s, 0, -s, -1, -s}
var cos = []float64{1, s, 0, -s, -1, -s, 0, s}
var p = color.NRGBA{64, 192, 96, 255}
var b *image.NRGBA
 
func main() {
width := sep * 11 / 6
height := sep * 4 / 3
bounds := image.Rect(0, 0, width, height)
b = image.NewNRGBA(bounds)
draw.Draw(b, bounds, image.NewUniform(color.White), image.ZP, draw.Src)
dragon(14, 0, 1, sep, sep/2, sep*5/6)
f, err := os.Create("dragon.png")
if err != nil {
fmt.Println(err)
return
}
if err = png.Encode(f, b); err != nil {
fmt.Println(err)
}
if err = f.Close(); err != nil {
fmt.Println(err)
}
}
 
func dragon(n, a, t int, d, x, y float64) {
if n <= 1 {
// Go packages used here do not have line drawing functions
// so we implement a very simple line drawing algorithm here.
// We take advantage of knowledge that we are always drawing
// 45 degree diagonal lines.
x1 := int(x + .5)
y1 := int(y + .5)
x2 := int(x + d*cos[a] + .5)
y2 := int(y + d*sin[a] + .5)
xInc := 1
if x1 > x2 {
xInc = -1
}
yInc := 1
if y1 > y2 {
yInc = -1
}
for x, y := x1, y1; ; x, y = x+xInc, y+yInc {
b.Set(x, y, p)
if x == x2 {
break
}
}
return
}
d *= s
a1 := (a - t) & 7
a2 := (a + t) & 7
dragon(n-1, a1, 1, d, x, y)
dragon(n-1, a2, -1, d, x+d*cos[a1], y+d*sin[a1])
}

Original version written to Bitmap task:

package main
 
// Files required to build supporting package raster are found in:
// * Bitmap
// * Write a PPM file
 
import (
"math"
"raster"
)
 
// separation of the the two endpoints
// make this a power of 2 for prettiest output
const sep = 512
// depth of recursion. adjust as desired for different visual effects.
const depth = 14
 
var s = math.Sqrt2 / 2
var sin = []float64{0, s, 1, s, 0, -s, -1, -s}
var cos = []float64{1, s, 0, -s, -1, -s, 0, s}
var p = raster.Pixel{64, 192, 96}
var b *raster.Bitmap
 
func main() {
width := sep * 11 / 6
height := sep * 4 / 3
b = raster.NewBitmap(width, height)
b.Fill(raster.Pixel{255, 255, 255})
dragon(14, 0, 1, sep, sep/2, sep*5/6)
b.WritePpmFile("dragon.ppm")
}
 
func dragon(n, a, t int, d, x, y float64) {
if n <= 1 {
b.Line(int(x+.5), int(y+.5), int(x+d*cos[a]+.5), int(y+d*sin[a]+.5), p)
return
}
d *= s
a1 := (a - t) & 7
a2 := (a + t) & 7
dragon(n-1, a1, 1, d, x, y)
dragon(n-1, a2, -1, d, x+d*cos[a1], y+d*sin[a1])
}

[edit] Haskell

import Data.List
import Graphics.Gnuplot.Simple
 
-- diamonds
-- pl = [[0,1],[1,0]]
 
pl = [[0,0],[0,1]]
r_90 = [[0,1],[-1,0]]
 
ip :: [Int] -> [Int] -> Int
ip xs = sum . zipWith (*) xs
matmul xss yss = map (\xs -> map (ip xs ). transpose $ yss) xss
 
vmoot xs = (xs++).map (zipWith (+) lxs). flip matmul r_90.
map (flip (zipWith (-)) lxs) .reverse . init $ xs
where lxs = last xs
 
dragoncurve = iterate vmoot pl

For plotting I use the gnuplot interface module from hackageDB

Use:

plotPath [] . map (\[x,y] -> (x,y)) $ dragoncurve!!13

String rewrite, and outputs a postscript:

x 0 = ""
x n = (x$n-1)++" +"++(y$n-1)++" f +"
y 0 = ""
y n = " - f"++(x$n-1)++" -"++(y$n-1)
 
dragon n =
concat ["0 setlinewidth 300 400 moveto",
"/f{2 0 rlineto}def/+{90 rotate}def/-{-90 rotate}def\n",
"f", x n, " stroke showpage"]
 
main = putStrLn $ dragon 14

[edit] HicEst

A straightforward approach, since HicEst does not know recursion (rarely needed in daily work)

    CHARACTER dragon
 
1 DLG(NameEdit=orders,DNum, Button='&OK', TItle=dragon) ! input orders
WINDOW(WINdowhandle=wh, Height=1, X=1, TItle='Dragon curves up to order '//orders)
 
IF( LEN(dragon) < 2^orders) ALLOCATE(dragon, 2^orders)
 
AXIS(WINdowhandle=wh, Xaxis=2048, Yaxis=2048) ! 2048: black, linear, noGrid, noScales
dragon = ' '
NorthEastSouthWest = 0
x = 0
y = 1
LINE(PenUp, Color=1, x=0, y=0, x=x, y=y)
last = 1
 
DO order = 1, orders
changeRtoL = LEN_TRIM(dragon) + 1 + (LEN_TRIM(dragon) + 1)/2
dragon = TRIM(dragon) // 'R' // TRIM(dragon)
IF(changeRtoL > 2) dragon(changeRtoL) = 'L'
 
DO last = last, LEN_TRIM(dragon)
NorthEastSouthWest = MOD( NorthEastSouthWest-2*(dragon(last)=='L')+5, 4 )
x = x + (NorthEastSouthWest==1) - (NorthEastSouthWest==3)
y = y + (NorthEastSouthWest==0) - (NorthEastSouthWest==2)
LINE(Color=order, X=x, Y=y)
ENDDO
ENDDO
GOTO 1 ! this is to stimulate a discussion
 
END

[edit] Icon and Unicon

The following implements a Heighway Dragon using the Lindenmayer system. It's based on the linden program in the Icon Programming Library.

link linddraw,wopen
 
procedure main()
gener := 12 # generations
w := h := 800 # window size
rewrite := table() # L rewrite rules
rewrite["X"] := "X+YF+"
rewrite["Y"] := "-FX-Y"
every (C := '') ++:= !!rewrite
every /rewrite[c := !C] := c # map all rule characters
 
WOpen("size=" || w || "," || h, "dx=" || (w / 2), "dy=" || (h / 2)) | stop("*** cannot open window")
WAttrib("fg=blue")
 
linddraw(0, 0, "FX", rewrite, 5, 90.0, gener, 0)
# x,y, axiom, rules, length, angle, generations, delay
 
WriteImage("dragon-unicon" || ".gif") # save the image
WDone()
end

linddraw wopen linden

[edit] J

require 'plot'
start=: 0 0,: 1 0
step=: ],{: +"1 (0 _1,: 1 0) +/ .*~ |.@}: -"1 {:
plot <"1 |: step^:13 start

In English: Start with a line segment. For each step of iteration, retrace that geometry backwards, but oriented 90 degrees about its original end point. To show the curve you need to pick some arbitrary number of iterations.

Any line segment is suitable for start. (For example, -start+123 works just fine though of course the resulting orientation and coordinates for the curve will be different from those obtained using start for the line segment.)

J-dragon.png

For a more colorful display, with a different color for the geometry introduced at each iteration, replace that last line of code with:

([:pd[:<"1|:)every'reset';|.'show';step&.>^:(i.17)<start

The curve can also be represented as a limiting set of the iterated function system

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

Giving the code

require 'plot'
f1=.*&(-:1j1)
f2=.[: -. *&(-:1j_1)
plot (f1,}.@|.@f2)^:12 ]0 1

Where both functions are applied successively to starting complex values of 0 and 1. Note the formatting of f2 as }.@|.@f2 . This allows the plotted path to go in the right order and removes redundant points, paralleling similar operations in the previous solution.

[edit] Java

import java.awt.Color;
import java.awt.Graphics;
import java.util.*;
import javax.swing.JFrame;
 
public class DragonCurve extends JFrame {
 
private List<Integer> turns;
private double startingAngle, side;
 
public DragonCurve(int iter) {
super("Dragon Curve");
setBounds(100, 100, 800, 600);
setDefaultCloseOperation(EXIT_ON_CLOSE);
turns = getSequence(iter);
startingAngle = -iter * (Math.PI / 4);
side = 400 / Math.pow(2, iter / 2.);
}
 
public List<Integer> getSequence(int iterations) {
List<Integer> turnSequence = new ArrayList<Integer>();
for (int i = 0; i < iterations; i++) {
List<Integer> copy = new ArrayList<Integer>(turnSequence);
Collections.reverse(copy);
turnSequence.add(1);
for (Integer turn : copy) {
turnSequence.add(-turn);
}
}
return turnSequence;
}
 
@Override
public void paint(Graphics g) {
g.setColor(Color.BLACK);
double angle = startingAngle;
int x1 = 230, y1 = 350;
int x2 = x1 + (int) (Math.cos(angle) * side);
int y2 = y1 + (int) (Math.sin(angle) * side);
g.drawLine(x1, y1, x2, y2);
x1 = x2;
y1 = y2;
for (Integer turn : turns) {
angle += turn * (Math.PI / 2);
x2 = x1 + (int) (Math.cos(angle) * side);
y2 = y1 + (int) (Math.sin(angle) * side);
g.drawLine(x1, y1, x2, y2);
x1 = x2;
y1 = y2;
}
}
 
public static void main(String[] args) {
new DragonCurve(14).setVisible(true);
}
}

[edit] JavaScript

Works with: Chrome 8.0

I'm sure this can be simplified further, but I have this working here!

Though there is an impressive SVG example further below, this uses JavaScript to recurse through the expansion and simply displays each line with SVG. It is invoked as a method DRAGON.fractal(...) as described.

var DRAGON = (function () {
// MATRIX MATH
// -----------
 
var matrix = {
mult: function ( m, v ) {
return [ m[0][0] * v[0] + m[0][1] * v[1],
m[1][0] * v[0] + m[1][1] * v[1] ];
},
 
minus: function ( a, b ) {
return [ a[0]-b[0], a[1]-b[1] ];
},
 
plus: function ( a, b ) {
return [ a[0]+b[0], a[1]+b[1] ];
}
};
 
 
// SVG STUFF
// ---------
 
// Turn a pair of points into an SVG path like "M1 1L2 2".
var toSVGpath = function (a, b) { // type system fail
return "M" + a[0] + " " + a[1] + "L" + b[0] + " " + b[1];
};
 
 
// DRAGON MAKING
// -------------
 
// Make a dragon with a better fractal algorithm
var fractalMakeDragon = function (svgid, ptA, ptC, state, lr, interval) {
 
// make a new <path>
var path = document.createElementNS('http://www.w3.org/2000/svg', 'path');
path.setAttribute( "class", "dragon");
path.setAttribute( "d", toSVGpath(ptA, ptC) );
 
// append the new path to the existing <svg>
var svg = document.getElementById(svgid); // call could be eliminated
svg.appendChild(path);
 
// if we have more iterations to go...
if (state > 1) {
 
// make a new point, either to the left or right
var growNewPoint = function (ptA, ptC, lr) {
var left = [[ 1/2,-1/2 ],
[ 1/2, 1/2 ]];
 
var right = [[ 1/2, 1/2 ],
[-1/2, 1/2 ]];
 
return matrix.plus(ptA, matrix.mult( lr ? left : right,
matrix.minus(ptC, ptA) ));
};
 
var ptB = growNewPoint(ptA, ptC, lr, state);
 
// then recurse using each new line, one left, one right
var recurse = function () {
// when recursing deeper, delete this svg path
svg.removeChild(path);
 
// then invoke again for new pair, decrementing the state
fractalMakeDragon(svgid, ptB, ptA, state-1, lr, interval);
fractalMakeDragon(svgid, ptB, ptC, state-1, lr, interval);
};
 
window.setTimeout(recurse, interval);
}
};
 
 
// Export these functions
// ----------------------
return {
fractal: fractalMakeDragon
 
// ARGUMENTS
// ---------
// svgid id of <svg> element
// ptA first point [x,y] (from top left)
// ptC second point [x,y]
// state number indicating how many steps to recurse
// lr true/false to make new point on left or right
 
// CONFIG
// ------
// CSS rules should be made for the following
// svg#fractal
// svg path.dragon
};
 
}());

My current demo page includes the following to invoke this:

...
<script src='./dragon.js'></script>
...
<div>
<svg xmlns='http://www.w3.org/2000/svg' id='fractal'></svg>
</div>
<script>
DRAGON.fractal('fractal', [100,300], [500,300], 15, false, 700);
</script>
...

[edit] Liberty BASIC

nomainwin
mainwin 50 20
 
WindowHeight =620
WindowWidth =690
 
open "Graphics library" for graphics as #a
 
#a, "trapclose [quit]"
 
#a "down"
 
Turn$ ="R"
Pace =100
s = 16
 
[again]
print Turn$
 
#a "cls ; home ; north ; down ; fill black"
 
for i =1 to len( Turn$)
v =255 *i /len( Turn$)
#a "color "; v; " 120 "; 255 -v
#a "go "; Pace
if mid$( Turn$, i, 1) ="R" then #a "turn 90" else #a "turn -90"
next i
 
#a "color 255 120 0"
#a "go "; Pace
#a "flush"
 
FlippedTurn$ =""
for i =len( Turn$) to 1 step -1
if mid$( Turn$, i, 1) ="R" then FlippedTurn$ =FlippedTurn$ +"L" else FlippedTurn$ =FlippedTurn$ +"R"
next i
 
Turn$ =Turn$ +"R" +FlippedTurn$
 
Pace =Pace /1.35
 
scan
 
timer 1000, [j]
wait
[j]
timer 0
 
if len( Turn$) <40000 then goto [again]
 
 
wait
 
[quit]
close #a
end

[edit]

[edit] Recursive

to dcr :step :length
make "step :step - 1
make "length :length / 1.41421
if :step > 0 [rt 45 dcr :step :length lt 90 dcl :step :length rt 45]
if :step = 0 [rt 45 fd :length lt 90 fd :length rt 45]
end
 
to dcl :step :length
make "step :step - 1
make "length :length / 1.41421
if :step > 0 [lt 45 dcr :step :length rt 90 dcl :step :length lt 45]
if :step = 0 [lt 45 fd :length rt 90 fd :length lt 45]
end

The program can be started using dcr 4 300 or dcl 4 300.

Or removing duplication:

to dc :step :length :dir
if :step = 0 [fd :length stop]
rt :dir
dc :step-1 :length/1.41421 45
lt :dir lt :dir
dc :step-1 :length/1.41421 -45
rt :dir
end
to dragon :step :length
dc :step :length 45
end

An alternative approach by using sentence-like grammar using four productions o->on, n->wn, w->ws, s->os. O, S, N and W mean cardinal points.

to O :step :length
if :step=1 [Rt 90 fd :length Lt 90] [O (:step - 1) (:length / 1.41421) N (:step - 1) (:length / 1.41421)]
end
 
to N :step :length
if :step=1 [fd :length] [W (:step - 1) (:length / 1.41421) N (:step - 1) (:length / 1.41421)]
end
 
to W :step :length
if :step=1 [Lt 90 fd :length Rt 90] [W (:step - 1) (:length / 1.41421) S (:step - 1) (:length / 1.41421)]
end
 
to S :step :length
if :step=1 [Rt 180 fd :length Lt 180] [O (:step - 1) (:length / 1.41421) S (:step - 1) (:length / 1.41421)]
end

[edit] Iterative

Or drawing iteratively by making a turn left or right at each point calculated by bit-twiddling. This allows any length to be drawn, not just powers-of-2.

Works with: UCB Logo
; Return the bit above the lowest 1-bit in :n.
; If :n = binary "...z100..00" then the return is "z000..00".
; Eg. n=22 is binary 10110 the lowest 1-bit is the "...1." and the return is
; bit above that "..1.," which is 4.
to bit.above.lowest.1bit :n
output bitand :n (1 + (bitxor :n (:n - 1)))
end
 
; Return angle +90 or -90 for dragon curve turn at point :n.
; The curve is reckoned as starting from n=0 so the first turn is at n=1.
to dragon.turn.angle :n
output ifelse (bit.above.lowest.1bit :n) = 0 [90] [-90]
end
 
; Draw :steps many segments of the dragon curve.
to dragon :steps
localmake "step.len 12  ; length of each step
repeat :steps [
forward :step.len
left dragon.turn.angle repcount  ; repcount = 1 to :steps inclusive
]
end
 
dragon 256
; Draw :steps many segments of the dragon curve, with corners chamfered
; off with little 45-degree diagonals.
; Done this way the vertices don't touch.
to dragon.chamfer :steps
localmake "step.len 12  ; length of each step
localmake "straight.frac 0.5 ; fraction of the step to go straight
 
localmake "straight.len  :step.len * :straight.frac
localmake "diagonal.len (:step.len - :straight.len) * sqrt(1/2)
 
repeat :steps [
localmake "turn (dragon.turn.angle repcount)/2  ; +45 or -45
forward :straight.len
left  :turn
forward :diagonal.len
left  :turn
]
end
 
dragon.chamfer 256

[edit] Lua

Works with: Lua version 5.1.4

Could be made much more compact, but this was written for speed. It has two rendering modes, one which renders the curve in text mode (default,) and one which just dumps all the coordinates for use by an external rendering application.

function dragon()
local l = "l"
local r = "r"
local inverse = {l = r, r = l}
local field = {r}
local num = 1
local loop_limit = 6 --increase this number to render a bigger curve
for discard=1,loop_limit do
field[num+1] = r
for i=1,num do
field[i+num+1] = inverse[field[num-i+1]]
end
num = num*2+1
end
return field
end
 
function render(field, w, h, l)
local x = 0
local y = 0
local points = {}
local highest_x = 0
local highest_y = 0
local lowest_x = 0
local lowest_y = 0
local l = "l"
local r = "r"
local u = "u"
local d = "d"
local heading = u
local turn = {r = {r = d, d = l, l = u, u = r}, l = {r = u, u = l, l = d, d = r}}
for k, v in ipairs(field) do
heading = turn[v][heading]
for i=1,3 do
points[#points+1] = {x, y}
if heading == l then
x = x-w
elseif heading == r then
x = x+w
elseif heading == u then
y = y-h
elseif heading == d then
y = y+h
end
if x > highest_x then
highest_x = x
elseif x < lowest_x then
lowest_x = x
end
if y > highest_y then
highest_y = y
elseif y < lowest_y then
lowest_y = y
end
end
end
points[#points+1] = {x, y}
highest_x = highest_x - lowest_x + 1
highest_y = highest_y - lowest_y + 1
for k, v in ipairs(points) do
v[1] = v[1] - lowest_x + 1
v[2] = v[2] - lowest_y + 1
end
return highest_x, highest_y, points
end
 
function render_text_mode()
local width, height, points = render(dragon(), 1, 1, 1)
local rows = {}
for i=1,height do
rows[i] = {}
for j=1,width do
rows[i][j] = ' '
end
end
for k, v in ipairs(points) do
rows[v[2]][v[1]] = "*"
end
 
for i=1,height do
print(table.concat(rows[i], ""))
end
end
 
function dump_points()
local width, height, points = render(dragon(), 4, 4, 1)
for k, v in ipairs(points) do
print(unpack(v))
end
end
 
--replace this line with dump_points() to output a list of coordinates:
render_text_mode()

Output:

      ****  ****                     
      *  *  *  *                     
      *  *  *  *                     
   ****  *******                     
   *        *                        
   *        *                        
   ****     ****  ****               
               *  *  *               
               *  *  *               
            **********               
            *  *  *                  
            *  *  *                  
            *******                  
               *                     
               *                     
      ****  ****                     
      *  *  *                        
      *  *  *                        
      **********  ****               
         *  *  *  *  *               
         *  *  *  *  *               
****  ****************               
*  *  *  *  *  *  *                  
*  *  *  *  *  *  *                  
*******************                  
   *  *  *  *  *                     
   *  *  *  *  *                     
*******  *******              ****   
*  *        *                    *   
*  *        *                    *   
*******     ****  ****           ****
   *  *        *  *  *              *
   *  *        *  *  *              *
   ****     **********           ****
            *  *  *              *   
            *  *  *              *   
            **********  ****  *******
               *  *  *  *  *  *  *  *
               *  *  *  *  *  *  *  *
            *******  **********  ****
            *  *        *  *         
            *  *        *  *         
            *******     *******      
               *  *        *  *      
               *  *        *  *      
               ****        ****      

[edit] M4

This code uses the "predicate" approach. A given x,y position is tested by a predicate as to whether it's on the curve or not and printed as a character or a space accordingly. The output goes row by row and column by column with no image storage or buffering.

# The macros which return a pair of values x,y expand to an unquoted 123,456
# which is suitable as arguments to a further macro. The quoting is slack
# because the values are always integers and so won't suffer unwanted macro
# expansion.
 
# 0,1 Vertex and segment x,y numbering.
# |
# | Segments are numbered as if a
# |s=0,1 square grid turned anti-clockwise
# | by 45 degrees.
# |
# -1,0 -------- 0,0 -------- 1,0 vertex_to_seg_east(x,y) returns
# s=-1,1 | s=0,0 the segment x,y to the East,
# | so vertex_to_seg_east(0,0) is 0,0
# |
# |s=-1,0 vertex_to_seg_west(x,y) returns
# | the segment x,y to the West,
# 0,-1 so vertex_to_seg_west(0,0) is -1,1
#
define(`vertex_to_seg_east', `eval($1 + $2), eval($2 - $1)')
define(`vertex_to_seg_west', `eval($1 + $2 - 1), eval($2 - $1 + 1)')
define(`vertex_to_seg_south', `eval($1 + $2 - 1), eval($2 - $1)')
 
# Some past BSD m4 didn't have "&" operator, so mod2(n) using % instead.
# mod2() returns 0,1 even if "%" gives -1 for negative odds.
#
define(`mod2', `ifelse(eval($1 % 2),0,0,1)')
 
# seg_to_even(x,y) returns x,y moved to an "even" position by subtracting an
# offset in a way which suits the segment predicate test.
#
# seg_offset_y(x,y) is a repeating pattern
#
# | 1,1,0,0
# | 1,1,0,0
# | 0,0,1,1
# | 0,0,1,1
# +---------
#
# seg_offset_x(x,y) is the same but offset by 1 in x,y
#
# | 0,1,1,0
# | 1,0,0,1
# | 1,0,0,1
# | 0,1,1,0
# +---------
#
# Incidentally these offset values also give n which is the segment number
# along the curve. "x_offset XOR y_offset" is 0,1 and is a bit of n from
# low to high.
#
define(`seg_offset_y', `mod2(eval(($1 >> 1) + ($2 >> 1)))')
define(`seg_offset_x', `seg_offset_y(eval($1+1), eval($2+1))')
define(`seg_to_even', `eval($1 - seg_offset_x($1,$2)),
eval($2 - seg_offset_y($1,$2))');
 
# xy_div_iplus1(x,y) returns x,y divided by complex number i+1.
# So (x+i*y)/(i+1) which means newx = (x+y)/2, newy = (y-x)/2.
# Must have x,y "even", meaning x+y even, so newx and newy are integers.
#
define(`xy_div_iplus1', `eval(($1 + $2)/2), eval(($2 - $1)/2)')
 
# seg_is_final(x,y) returns 1 if x,y is one of the final four points.
# On these four points xy_div_iplus1(seg_to_even(x,y)) returns x,y
# unchanged, so the seg_pred() recursion does not reduce any further.
#
# .. | ..
# final | final y=+1
# final | final y=0
# -------+--------
# .. | ..
# x=-1 x=0
#
define(`seg_is_final', `eval(($1==-1 || $1==0) && ($2==1 || $2==0))')
 
# seg_pred(x,y) returns 1 if segment x,y is on the dragon curve.
# If the final point reached is 0,0 then the original x,y was on the curve.
# (If a different final point then x,y was one of four rotated copies of the
# curve.)
#
define(`seg_pred', `ifelse(seg_is_final($1,$2), 1,
`eval($1==0 && $2==0)',
`seg_pred(xy_div_iplus1(seg_to_even($1,$2)))')')
 
# vertex_pred(x,y) returns 1 if point x,y is on the dragon curve.
# The curve always turns left or right at a vertex, it never crosses itself,
# so if a vertex is visited then either the segment to the east or to the
# west must have been traversed. Prefer ifelse() for the two checks since
# eval() || operator is not a short-circuit.
#
define(`vertex_pred', `ifelse(seg_pred(vertex_to_seg_east($1,$2)),1,1,
`seg_pred(vertex_to_seg_west($1,$2))')')
 
# forloop(varname, start,end, body)
# Expand body with varname successively define()ed to integers "start" to
# "end" inclusive. "start" to "end" can go either increasing or decreasing.
#
define(`forloop', `define(`$1',$2)$4`'dnl
ifelse($2,$3,,`forloop(`$1',eval($2 + 2*($2 < $3) - 1), $3, `$4')')')
 
#----------------------------------------------------------------------------
 
# dragon01(xmin,xmax, ymin,ymax) prints an array of 0s and 1s which are the
# vertex_pred() values. `y' runs from ymax down to ymin so that y
# coordinate increases up the screen.
#
define(`dragon01',
`forloop(`y',$4,$3, `forloop(`x',$1,$2, `vertex_pred(x,y)')
')')
 
# dragon_ascii(xmin,xmax, ymin,ymax) prints an ascii art dragon curve.
# Each y value results in two output lines. The first has "+" vertices and
# "--" horizontals. The second has "|" verticals.
#
define(`dragon_ascii',
`forloop(`y',$4,$3,
`forloop(`x',$1,$2,
`ifelse(vertex_pred(x,y),1, `+', ` ')dnl
ifelse(seg_pred(vertex_to_seg_east(x,y)), 1, `--', ` ')')
forloop(`x',$1,$2,
`ifelse(seg_pred(vertex_to_seg_south(x,y)), 1, `| ', ` ')')
')')
 
#--------------------------------------------------------------------------
divert`'dnl
 
# 0s and 1s directly from vertex_pred().
#
dragon01(-7,23, dnl X range
-11,10) dnl Y range
 
# ASCII art lines.
#
dragon_ascii(-6,5, dnl X range
-10,2) dnl Y range
Output
# 0s and 1s directly from vertex_pred().
#
0000000000000000011111110000000
0000000000000011011111111000000
0000000000000111011111111000000
0000000000000111111111100000000
0000000000000111111111111111000
0000000000000111111111111111100
0000000000000001111111111111100
0000000000000001111111111110000
0000111100000000011111111111000
0000111110000011011110001111100
0011110110000111011110111111100
0011110000000111111000111110000
0001110000000111111100011110000
0000111100110111111110000000000
0011111101110111111110000000000
0011111111111111111000000000000
0001111111111111111100000000000
0000000011111000111110000000000
0000001111111011111110000000000
0000001111100011111000000000000
0000000111100001111000000000000
0000000000000000000000000000000
     
# ASCII art lines.
#
         +--+  +--+                 
         |  |  |  |                 
         +--+--+  +--+              
            |        |              
   +--+  +--+     +--+              
   |  |  |                          
   +--+--+--+                       
      |  |  |                       
      +--+--+                       
         |                          
         +--+  +--+        +--+     
            |  |  |        |  |     
   +--+  +--+--+--+     +--+--+     
   |  |  |  |  |        |  |        
   +--+--+--+--+--+  +--+--+--+  +--
      |  |  |  |  |  |  |  |  |  |  
      +--+  +--+  +--+--+--+--+--+  
                     |  |  |  |     
                     +--+--+--+--+  
                        |  |  |  |  
               +--+  +--+--+  +--+  
               |  |  |  |           
               +--+--+--+--+        
                  |  |  |  |        
                  +--+  +--+

[edit] Mathematica

Two functions: one that makes 2 lines from 1 line. And another that applies this function to all existing lines:

FoldOutLine[{a_,b_}]:={{a,#},{b,#}}&[a+0.5(b-a)+{{0.,0.5},{-0.5,0.}}.(b-a)]
NextStep[in_]:=Flatten[FoldOutLine/@in,1]
lines={{{0.,0.},{1.,0.}}};
Graphics[Line/@Nest[NextStep,lines,11]]

[edit] Metafont

Metafont is a language to create fonts; since fonts normally are not too big, Metafont has hard encoded limits which makes it difficult to produce large images. This is one of the reasons why Metapost came into being.

The following code produces a single character font, 25 points wide and tall (0 points in depth), and store it in the position where one could expect to find the character D.

mode_setup;
dragoniter := 8;
beginchar("D", 25pt#, 25pt#, 0pt#);
pickup pencircle scaled .5pt;
x1 = 0; x2 = w; y1 = y2 = .5h;
mstep := .5; sg := -1;
for i = 1 upto dragoniter:
for v = 1 step mstep until (2-mstep):
if unknown z[v+mstep]:
pair t;
t := .7071[ z[v], z[v+2mstep] ];
z[v+mstep] = t rotatedaround(z[v], 45sg);
sg := -1*sg;
fi
endfor
mstep := mstep/2;
endfor
draw for v:=1 step 2mstep until (2-2mstep): z[v] -- endfor z[2];
endchar;
end

The resulting character, magnified by 2, looks like:

Dragon1.png

[edit] OCaml

Library: Tk

Example solution, using an OCaml class and displaying the result in a Tk canvas, mostly inspired by the Tcl solution.

(* This constant does not seem to be defined anywhere in the standard modules *)
let pi = acos (-1.0);
 
(*
** CLASS dragon_curve_computer:
** ----------------------------
** Computes the coordinates for the line drawing the curve.
** - initial_x initial_y: coordinates for starting point for curve
** - total_length: total length for the curve
** - total_splits: total number of splits to perform
*)

class dragon_curve_computer initial_x initial_y total_length total_splits =
object(self)
val mutable current_x = (float_of_int initial_x) (* current x coordinate in curve *)
val mutable current_y = (float_of_int initial_y) (* current y coordinate in curve *)
val mutable current_angle = 0.0 (* current angle *)
 
(*
** METHOD compute_coords:
** ----------------------
** Actually computes the coordinates in the line for the curve
** - length: length for current iteration
** - nb_splits: number of splits to perform for current iteration
** - direction: direction for current line (-1.0 or 1.0)
** Returns: the list of coordinates for the line in this iteration
*)

method compute_coords length nb_splits direction =
(* If all splits have been done *)
if nb_splits = 0
then
begin
(* Draw line segment, updating current coordinates *)
current_x <- current_x +. length *. cos current_angle;
current_y <- current_y +. length *. sin current_angle;
[(int_of_float current_x, int_of_float current_y)]
end
(* If there are still splits to perform *)
else
begin
(* Compute length for next iteration *)
let sub_length = length /. sqrt 2.0 in
(* Turn 45 degrees to left or right depending on current direction and draw part
of curve in this direction *)

current_angle <- current_angle +. direction *. pi /. 4.0;
let coords1 = self#compute_coords sub_length (nb_splits - 1) 1.0 in
(* Turn 90 degrees in the other direction and draw part of curve in that direction *)
current_angle <- current_angle -. direction *. pi /. 2.0;
let coords2 = self#compute_coords sub_length (nb_splits - 1) (-1.0) in
(* Turn back 45 degrees to set head in the initial direction again *)
current_angle <- current_angle +. direction *. pi /. 4.0;
(* Concatenate both sub-curves to get the full curve for this iteration *)
coords1 @ coords2
end
 
(*
** METHOD get_coords:
** ------------------
** Returns the coordinates for the curve with the parameters set in the object initializer
*)

method get_coords = self#compute_coords total_length total_splits 1.0
end;;
 
 
(*
** MAIN PROGRAM:
** =============
*)

let () =
(* Curve is displayed in a Tk canvas *)
let top=Tk.openTk() in
let c = Canvas.create ~width:400 ~height:400 top in
Tk.pack [c];
(* Create instance computing the curve coordinates *)
let dcc = new dragon_curve_computer 100 200 200.0 16 in
(* Create line with these coordinates in canvas *)
ignore (Canvas.create_line ~xys: dcc#get_coords c);
Tk.mainLoop ();
;;

Here is another OCaml solution, in a functional rather than OO style:

let zig (x1,y1) (x2,y2) = (x1+x2+y1-y2)/2, (x2-x1+y1+y2)/2
let zag (x1,y1) (x2,y2) = (x1+x2-y1+y2)/2, (x1-x2+y1+y2)/2
 
let rec dragon p1 p2 p3 n =
if n = 0 then [p1;p2] else
(dragon p1 (zig p1 p2) p2 (n-1)) @ (dragon p2 (zag p2 p3) p3 (n-1))
 
let _ =
let top = Tk.openTk() in
let c = Canvas.create ~width:430 ~height:300 top in
Tk.pack [c];
let p1, p2 = (100, 100), (356,100) in
let points = dragon p1 (zig p1 p2) p2 15 in
ignore (Canvas.create_line ~xys: points c);
Tk.mainLoop ()

producing:

OCaml Dragon-curve-example2.png

Run an example with:

ocaml -I +labltk labltk.cma dragon.ml

[edit] Perl 6

Iterative algorithm. Prints in SVG format.

say "<?xml version='1.0' encoding='utf-8' standalone='no'?>
<!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 1.1//EN'
'http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd'>
<svg width='100%' height='100%' version='1.1'
xmlns='http://www.w3.org/2000/svg'>"
;
 
my $order = 10; # akin to number of recursion steps
my $d_size = 1000; # size in pixels
my $turn_angle = pi/2; # turn angle of each segment, 90 degrees for the canonical dragon
 
my $angle = pi - ($order * (pi/4)); # starting angle
my $len = ($d_size/1.5) / sqrt(2)**$order; # size of each segment
my ($x, $y) = ($d_size*5/6, $d_size*1/3); # starting point
 
for 0..2**$order-1 -> $i
{
# find which side to turn based on the iteration
$angle += ((($i +& -$i) +< 1) +& $i) ?? -$turn_angle !! $turn_angle;
 
my ($dx, $dy) = ($x + $len * $angle.sin, $y - $len * $angle.cos);
say "<line x1='$x' y1='$y' x2='$dx' y2='$dy' style='stroke:rgb(0,0,0);stroke-width:1'/>";
($x, $y) = ($dx, $dy);
}
 
say "</svg>";

[edit] Pascal

using Compas (Pascal with Logo-expansion):

procedure dcr(step,dir:integer;length:real);
begin;
step:=step -1;
length:= length/sqrt(2);
if dir > 0 then
begin
if step > 0 then
begin
turnright(45);
dcr(step,1,length);
turnleft(90);
dcr(step,0,length);
turnright(45);
end
else
begin
turnright(45);
forward(length);
turnleft(90);
forward(length);
turnright(45);
end;
end
else
begin
if step > 0 then
begin
turnleft(45);
dcr(step,1,length);
turnright(90);
dcr(step,0,length);
turnleft(45);
end
else
begin
turnleft(45);
forward(length);
turnright(90);
forward(length);
turnleft(45);
end;
end;
end;

main program:

begin
init;
penup;
back(100);
pendown;
dcr(step,direction,length);
close;
end.

[edit] PicoLisp

Translation of: Forth

This uses the 'brez' line drawing function from Bitmap/Bresenham's line algorithm#PicoLisp.

# Need some turtle graphics
(load "@lib/math.l")
 
(setq
*TurtleX 100 # X position
*TurtleY 75 # Y position
*TurtleA 0.0 ) # Angle
 
(de fd (Img Len) # Forward
(let (R (*/ *TurtleA pi 180.0) DX (*/ (cos R) Len 1.0) DY (*/ (sin R) Len 1.0))
(brez Img *TurtleX *TurtleY DX DY)
(inc '*TurtleX DX)
(inc '*TurtleY DY) ) )
 
(de rt (A) # Right turn
(inc '*TurtleA A) )
 
(de lt (A) # Left turn
(dec '*TurtleA A) )
 
 
# Dragon curve stuff
(de *DragonStep . 4)
 
(de dragon (Img Depth Dir)
(if (=0 Depth)
(fd Img *DragonStep)
(rt Dir)
(dragon Img (dec Depth) 45.0)
(lt (* 2 Dir))
(dragon Img (dec Depth) -45.0)
(rt Dir) ) )
 
# Run it
(let Img (make (do 200 (link (need 300 0)))) # Create image 300 x 200
(dragon Img 10 45.0) # Build dragon curve
(out "img.pbm" # Write to bitmap file
(prinl "P1")
(prinl 300 " " 200)
(mapc prinl Img) ) )

[edit] PostScript

%!PS
%%BoundingBox: 0 0 550 400
/ifpendown false def
/rotation 0 def
/srootii 2 sqrt def
/turn {
rotation add /rotation exch def
} def
/forward {
dup rotation cos mul
exch rotation sin mul
ifpendown
{ rlineto }
{ rmoveto }
ifelse
} def
/penup {
/ifpendown false def
} def
/pendown {
/ifpendown true def
} def
 
/dragon { % [ length, split, d ]
dup
dup 1 get 0 eq
{ 0 get forward }
{ dup 2 get 45 mul turn
dup aload pop pop
1 sub exch srootii div exch
1 3 array astore dragon pop
dup 2 get 90 mul neg turn
dup aload pop pop
1 sub exch srootii div exch
-1 3 array astore dragon
dup 2 get 45 mul turn
}
ifelse
pop
} def
150 150 moveto pendown [ 300 12 1 ] dragon stroke
% 0 0 moveto 550 0 rlineto 0 400 rlineto -550 0 rlineto closepath stroke
showpage
%%END

Or (almost) verbatim string rewrite: (this is a 20 page document, and don't try to print it, or you might have a very angry printer).

%!PS-Adobe-3.0
%%BoundingBox 0 0 300 300
 
/+ { 90 rotate } def
/- {-90 rotate } def
/!1 { dup 1 sub dup 0 eq not } def
 
/F { 180 0 rlineto } def
/X { !1 { X + Y F + } if pop } def
/Y { !1 { - F X - Y } if pop } def
 
/dragon {
gsave
70 180 moveto
dup 1 sub { 1 2 div sqrt dup scale -45 rotate } repeat
F X stroke
grestore
} def
 
1 1 20 { dragon showpage } for
 
%%EOF
See also

[edit] Prolog

Works with SWI-Prolog which has a Graphic interface XPCE.
DCG are used to compute the list of "turns" of the Dragon Curve and the list of points.

dragonCurve(N) :-
dcg_dg(N, [left], DCL, []),
Side = 4,
Angle is -N * (pi/4),
dcg_computePath(Side, Angle, DCL, point(180,400), P, []),
new(D, window('Dragon Curve')),
send(D, size, size(800,600)),
new(Path, path(poly)),
send_list(Path, append, P),
send(D, display, Path),
send(D, open).
 
 
% compute the list of points of the Dragon Curve
dcg_computePath(Side, Angle, [left | DCT], point(X1, Y1)) -->
[point(X1, Y1)],
{ X2 is X1 + Side * cos(Angle),
Y2 is Y1 + Side * sin(Angle),
Angle1 is Angle + pi / 2
},
dcg_computePath(Side, Angle1, DCT, point(X2, Y2)).
 
dcg_computePath(Side, Angle, [right | DCT], point(X1, Y1)) -->
[point(X1, Y1)],
{ X2 is X1 + Side * cos(Angle),
Y2 is Y1 + Side * sin(Angle),
Angle1 is Angle - pi / 2
},
dcg_computePath(Side, Angle1, DCT, point(X2, Y2)).
 
 
dcg_computePath(_Side, _Angle, [], point(X1, Y1)) -->
[ point(X1, Y1)].
 
 
% compute the list of the "turns" of the Dragon Curve
dcg_dg(1, L) --> L.
 
dcg_dg(N, L) -->
{dcg_dg(L, L1, []),
N1 is N - 1},
dcg_dg(N1, L1).
 
% one interation of the process
dcg_dg(L) -->
L,
[left],
inverse(L).
 
inverse([H | T]) -->
inverse(T),
inverse(H).
 
inverse([]) --> [].
 
inverse(left) -->
[right].
 
inverse(right) -->
[left].

Output  :

1 ?- dragonCurve(13).
true 
Prolog-DragonCurve.jpg

[edit] PureBasic

#SqRt2 = 1.4142136
#SizeH = 800: #SizeV = 550
Global angle.d, px, py, imageNum
 
Procedure turn(degrees.d)
angle + degrees * #PI / 180
EndProcedure
 
Procedure forward(length.d)
Protected w = Cos(angle) * length
Protected h = Sin(angle) * length
LineXY(px, py, px + w, py + h, RGB(255,255,255))
px + w: py + h
EndProcedure
 
Procedure dragon(length.d, split, d.d)
If split = 0
forward(length)
Else
turn(d * 45)
dragon(length / #SqRt2, split - 1, 1)
turn(-d * 90)
dragon(length / #SqRt2, split - 1, -1)
turn(d * 45)
EndIf
EndProcedure
 
OpenWindow(0, 0, 0, #SizeH, #SizeV, "DragonCurve", #PB_Window_SystemMenu)
imageNum = CreateImage(#PB_Any, #SizeH, #SizeV, 32)
ImageGadget(0, 0, 0, 0, 0, ImageID(imageNum))
 
angle = 0: px = 185: py = 190
If StartDrawing(ImageOutput(imageNum))
dragon(400, 15, 1)
StopDrawing()
SetGadgetState(0, ImageID(imageNum))
EndIf
 
Repeat: Until WaitWindowEvent(10) = #PB_Event_CloseWindow

[edit] Python

Translation of: Logo
Library: turtle
from turtle import *
 
def dragon(step, length):
dcr(step, length)
 
def dcr(step, length):
step -= 1
length /= 1.41421
if step > 0:
right(45)
dcr(step, length)
left(90)
dcl(step, length)
right(45)
else:
right(45)
forward(length)
left(90)
forward(length)
right(45)
 
def dcl(step, length):
step -= 1
length /= 1.41421
 
if step > 0:
left(45)
dcr(step, length)
right(90)
dcl(step, length)
left(45)
else:
left(45)
forward(length)
right(90)
forward(length)
left(45)

A more pythonic version:

from turtle import right, left, forward, speed, exitonclick, hideturtle
 
def dragon(level=4, size=200, zig=right, zag=left):
if level <= 0:
forward(size)
return
 
size /= 1.41421
zig(45)
dragon(level-1, size, right, left)
zag(90)
dragon(level-1, size, left, right)
zig(45)
 
speed(0)
hideturtle()
dragon(6)
exitonclick() # click to exit

Other version:

from turtle import right, left, forward, speed, exitonclick, hideturtle
 
def dragon(level=4, size=200, direction=45):
if level:
right(direction)
dragon(level-1, size/1.41421356237, 45)
left(direction * 2)
dragon(level-1, size/1.41421356237, -45)
right(direction)
else:
forward(size)
 
speed(0)
hideturtle()
dragon(6)
exitonclick() # click to exit

[edit] Racket

#lang racket
 
(require plot)
 
(define (dragon-turn n)
(if (> (bitwise-and (arithmetic-shift (bitwise-and n (- n)) 1) n) 0)
'L
'R))
 
(define (rotate heading dir)
(cond
[(eq? dir 'R) (cond [(eq? heading 'N) 'E]
[(eq? heading 'E) 'S]
[(eq? heading 'S) 'W]
[(eq? heading 'W) 'N])]
[(eq? dir 'L) (cond [(eq? heading 'N) 'W]
[(eq? heading 'E) 'N]
[(eq? heading 'S) 'E]
[(eq? heading 'W) 'S])]))
(define (step pos heading)
(cond
[(eq? heading 'N) (list (car pos) (add1 (cadr pos)))]
[(eq? heading 'E) (list (add1 (car pos)) (cadr pos))]
[(eq? heading 'S) (list (car pos) (sub1 (cadr pos)))]
[(eq? heading 'W) (list (sub1 (car pos)) (cadr pos))]
))
 
(let-values ([(dir pos trail)
(for/fold ([dir 'N]
[pos (list 0 0)]
[trail '((0 0))])
([n (in-range 0 50000)])
(let* ([new-dir (rotate dir (dragon-turn n))]
[new-pos (step pos new-dir)])
(values new-dir
new-pos
(cons new-pos trail))))])
(plot-file (lines trail) "dragon.png" 'png))

Racket Dragon curve.png


[edit] RapidQ

Translation of: BASIC

This implementation displays the Dragon Curve fractal in a GUI window.

DIM angle AS Double
DIM x AS Double, y AS Double
DECLARE SUB PaintCanvas
 
CREATE form AS QForm
Width = 800
Height = 600
CREATE canvas AS QCanvas
Height = form.ClientHeight
Width = form.ClientWidth
OnPaint = PaintCanvas
END CREATE
END CREATE
 
SUB turn (degrees AS Double)
angle = angle + degrees*3.14159265/180
END SUB
 
SUB forward (length AS Double)
x2 = x + cos(angle)*length
y2 = y + sin(angle)*length
canvas.Line(x, y, x2, y2, &Haaffff)
x = x2: y = y2
END SUB
 
SUB dragon (length AS Double, split AS Integer, d AS Double)
IF split=0 THEN
forward length
ELSE
turn d*45
dragon length/1.4142136, split-1, 1
turn -d*90
dragon length/1.4142136, split-1, -1
turn d*45
END IF
END SUB
 
SUB PaintCanvas
canvas.FillRect(0, 0, canvas.Width, canvas.Height, &H102800)
x = 220: y = 220: angle = 0
dragon 384, 12, 1
END SUB
 
form.ShowModal

[edit] REXX

This REXX version uses a unique plot character to indicate which part of the dragon curve is being shown.
A specific plot character can be specified instead for all curve parts   (the 3rd argument).

Also, the initial (facing) direction may be specified   (0 ──► 3   representing   N, E, S, W).
This, in effect, allows the dragon curve to be plotted with a different orientation.

/*REXX program to draw an ASCII Dragon Curve (or Harter-Heighway dragon)*/
d.=1; d.L=-1; @.=' '; x=0; x2=x; y=0; y2=y; @.x.y='∙'; z=1
plot_pts='123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZΘ'
minx=0; maxx=0; miny=0; maxy=0 /*assign various constants & vars*/
parse arg # p c . /*# is # iterations, P=init dir.*/
if #=='' | #==',' then #=11 /*Not specified? Use the default*/
if p=='' | p==',' then p=0 /*Not specified? Use the default*/
if c=='' then c=plot_pts /*Not specified? Use the default*/
if length(c)==2 then c=x2c(c) /*hexadecimal code was specified?*/
if length(c)==3 then c=d2c(c) /* decimal " " "  ?*/
$= /*nullify the dragon curve string*/
do # /*create the dragon curve string.*/
$=$'R'reverse(translate($,'RL','LR')) /*append,flip,reverse.*/
end /*#*/
/*create dragon curve.*/
do j=1 for length($); _=substr($,j,1) /*get next direction.*/
p=(p+d._)//4; if p<0 then p=p+4 /*move in a direction.*/
if p==0 then do; y=y+1; y2=y+1; end /*going east map-wise.*/
if p==1 then do; x=x+1; x2=x+1; end /* " south " */
if p==2 then do; y=y-1; y2=y-1; end /* " west " */
if p==3 then do; x=x-1; x2=x-1; end /* " north " */
if j>2**z then z=z+1 /*the curve being done*/
 !=substr(c,z,1); if !==' ' then !=right(c,1) /*choose plot pt char.*/
@.x.y=!; @.x2.y2=! /*draw part of dragon.*/
minx=min(minx,x,x2); maxx=max(maxx,x,x2); x=x2 /*define graph limits.*/
miny=min(miny,y,y2); maxy=max(maxy,y,y2); y=y2 /* " " " */
end /*j*/
/*display dragon curve on screen.*/
do r=minx to maxx; a= /*nullify the line to be drawn. */
do c=miny to maxy /*create a line (row) of points. */
a=a || @.r.c /*build one column at a time. */
end /*c*/
a=strip(a,'T') /*be nice & strip trailing blanks*/
if a\=='' then say a /*display a line (row) of points.*/
end /*r*/
/*stick a fork in it, we're done.*/

output when using the following input: 11 e9

                                                                                    ΘΘΘ ΘΘΘ         ΘΘΘ ΘΘΘ
                                                                                    Θ Θ Θ Θ         Θ Θ Θ Θ
                                                                                  ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                                                                                  Θ Θ Θ Θ         Θ Θ Θ Θ
                                                                                  ΘΘΘ ΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ
                                                                                        Θ Θ Θ Θ         Θ Θ Θ Θ
                                                                                      ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                                                                                      Θ Θ Θ Θ         Θ Θ Θ Θ
                                                                            ΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘ
                                                                            Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                                          ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                                          Θ Θ Θ Θ Θ     Θ Θ     Θ Θ Θ Θ Θ
                                                                          ΘΘΘ ΘΘΘΘΘΘΘ   ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ
                                                                                Θ Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ
                                                                              ΘΘΘ ΘΘΘ     ΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                                              Θ                 Θ Θ Θ Θ Θ Θ Θ
                                                                            ΘΘΘΘΘ               ΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘ ΘΘΘ
                                                                            Θ Θ Θ                 Θ Θ Θ Θ Θ         Θ Θ Θ Θ
                                                                          ΘΘΘΘΘΘΘ               ΘΘΘΘΘ ΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                                                                          Θ Θ Θ                 Θ Θ     Θ         Θ Θ Θ Θ
                                                                          ΘΘΘ ΘΘΘ     ∙         ΘΘΘΘΘ   ΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ
                                                                                Θ     Θ           Θ Θ     Θ Θ Θ         Θ Θ Θ Θ
                                                                              ΘΘΘΘΘ ΘΘΘ           ΘΘΘ   ΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                                                                              Θ Θ Θ Θ                   Θ Θ Θ         Θ Θ Θ Θ
                                                                              ΘΘΘ ΘΘΘ                   ΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘ
                                                                                                          Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                                                                    ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                                                                    Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                                                                    ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ
                                                                                                      Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                                                                ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                                                                Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                                                                ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘ
                                                                                                  Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                                                                ΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                                                                Θ Θ     Θ Θ Θ Θ Θ
                                                                                                ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ
                                                                                                  Θ Θ     Θ Θ Θ Θ Θ Θ Θ
                                                                                                  ΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                                                                        Θ Θ Θ Θ Θ Θ Θ
                                                                                                        ΘΘΘΘΘ ΘΘΘ ΘΘΘ
                                                                                                          Θ
                    ΘΘΘ     ΘΘΘ                     ΘΘΘ     ΘΘΘ                     ΘΘΘ     ΘΘΘ     ΘΘΘ ΘΘΘ
                    Θ Θ     Θ Θ                     Θ Θ     Θ Θ                     Θ Θ     Θ Θ     Θ Θ Θ
                    ΘΘΘΘΘ   ΘΘΘΘΘ                   ΘΘΘΘΘ   ΘΘΘΘΘ                   ΘΘΘΘΘ   ΘΘΘΘΘ   ΘΘΘΘΘΘΘ ΘΘΘ
                      Θ Θ     Θ Θ                     Θ Θ     Θ Θ                     Θ Θ     Θ Θ     Θ Θ Θ Θ Θ
                ΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘ               ΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘ               ΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ
                Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
                ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ               ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ               ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘ ΘΘΘ
                  Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
                ΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ   ΘΘΘ         ΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ   ΘΘΘ         ΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                Θ Θ     Θ Θ Θ Θ     Θ Θ         Θ Θ     Θ Θ Θ Θ     Θ Θ         Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
                ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘ   ΘΘΘΘΘ       ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘ   ΘΘΘΘΘ       ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ
                  Θ Θ     Θ Θ Θ Θ     Θ Θ         Θ Θ     Θ Θ Θ Θ     Θ Θ         Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
                  ΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘΘΘ         ΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘΘΘ         ΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                        Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
                        ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ               ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ               ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘ
                          Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
    ΘΘΘ     ΘΘΘ     ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ   ΘΘΘ     ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ   ΘΘΘ     ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
    Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
    ΘΘΘΘΘ   ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ   ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ   ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ
      Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ     Θ Θ     Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
ΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘ
  Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ
ΘΘΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
Θ Θ     Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ
ΘΘΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ
  Θ Θ     Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ
  ΘΘΘ   ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
        Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ         Θ Θ Θ Θ
        ΘΘΘΘΘ ΘΘΘ ΘΘΘ         ΘΘΘ ΘΘΘ       ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘ         ΘΘΘ ΘΘΘ         ΘΘΘ ΘΘΘ
          Θ                                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
    ΘΘΘ ΘΘΘ                               ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
    Θ Θ Θ                                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
    ΘΘΘΘΘΘΘ ΘΘΘ                           ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ
      Θ Θ Θ Θ Θ                                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ                               ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
Θ Θ Θ Θ Θ Θ Θ                                 Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
ΘΘΘΘΘΘΘΘΘΘΘΘΘ                               ΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘ ΘΘΘ
  Θ Θ Θ Θ Θ                                 Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
ΘΘΘΘΘ ΘΘΘΘΘ         ΘΘΘ                   ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
Θ Θ     Θ           Θ Θ                   Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
ΘΘΘΘΘ   ΘΘΘ ΘΘΘ     Θ ΘΘΘ                 ΘΘΘ ΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ
  Θ Θ     Θ Θ Θ         Θ                       Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
  ΘΘΘ   ΘΘΘΘΘΘΘ       ΘΘΘ                     ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
        Θ Θ Θ         Θ                       Θ Θ Θ Θ         Θ Θ Θ Θ Θ Θ Θ Θ         Θ Θ Θ Θ
        ΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘ                     ΘΘΘ ΘΘΘ       ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘ
          Θ Θ Θ Θ Θ Θ Θ Θ                                   Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
        ΘΘΘΘΘ ΘΘΘΘΘΘΘ ΘΘΘ                                 ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
        Θ Θ     Θ Θ                                       Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
        ΘΘΘΘΘ   ΘΘΘΘΘ                                     ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ
          Θ Θ     Θ Θ                                           Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
          ΘΘΘ     ΘΘΘ                                         ΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘΘ
                                                              Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ Θ
                                                            ΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘΘΘΘΘΘΘΘΘ ΘΘΘ ΘΘΘ
                                                            Θ Θ Θ Θ         Θ Θ Θ Θ
                                                          ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                                                          Θ Θ Θ Θ         Θ Θ Θ Θ
                                                          ΘΘΘ ΘΘΘΘΘ ΘΘΘ   ΘΘΘ ΘΘΘΘΘ ΘΘΘ
                                                                Θ Θ Θ Θ         Θ Θ Θ Θ
                                                              ΘΘΘΘΘΘΘΘΘ       ΘΘΘΘΘΘΘΘΘ
                                                              Θ Θ Θ Θ         Θ Θ Θ Θ
                                                              ΘΘΘ ΘΘΘ         ΘΘΘ ΘΘΘ


output when using the default input

                                                                                    777 777         888 888
                                                                                    7 7 7 7         8 8 8 8
                                                                                  777677777       888788888
                                                                                  7 6 6 7         8 7 7 8
                                                                                  666 66777 777   777 77888 888
                                                                                        6 7 7 7         7 8 8 8
                                                                                      667777777       778888888
                                                                                      6 7 7 7         7 8 8 8
                                                                            666 666 66667777777 777 777788888
                                                                            6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8
                                                                          66656666666 6677777 7777778887888
                                                                          6 5 5 6 6     7 7     7 7 8 8 8
                                                                          555 5566666   77777   77778888888 888
                                                                                5 6 6     7 7     7 7 8 8 8 8 8
                                                                              555 666     777   888788888888888
                                                                              5                 8 8 8 8 8 8 8
                                                                            55555               8888888888888       999 999
                                                                            5 5 5                 8 8 8 8 8         9 9 9 9
                                                                          5554555               88888 88888       999899999
                                                                          5 4 4                 8 8     8         9 8 8 9
                                                                          444 444     ∙         88888   888 888   888 88999 999
                                                                                4     1           8 8     8 8 8         8 9 9 9
                                                                              44433 111           888   8888888       889999999
                                                                              4 3 3 2                   8 8 8         8 9 9 9
                                                                              333 222                   8888888 888 888899999
                                                                                                          8 8 8 8 8 8 8 8 9
                                                                                                    999 8888999888889998999
                                                                                                    9 9 8 8 9 9 8 8 9 9 9
                                                                                                    99999888999998889999999 999
                                                                                                      9 9 8 8 9 9 8 8 9 9 9 9 9
                                                                                                999 999999989999999899999999999
                                                                                                9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
                                                                                                999999999999999999999 999 999
                                                                                                  9 9 9 9 9 9 9 9 9
                                                                                                99999 9999999999999
                                                                                                9 9     9 9 9 9 9
                                                                                                99999   99999999999 999
                                                                                                  9 9     9 9 9 9 9 9 9
                                                                                                  999   999999999999999
                                                                                                        9 9 9 9 9 9 9
                                                                                                        99999 999 999
                                                                                                          9
                    bbb     bbb                     bbb     bbb                     aaa     aaa     999 999
                    b b     b b                     b b     b b                     a a     a a     9 9 9
                    bbbbb   bbbbb                   bbbbb   bbbbb                   aaaaa   aaaaa   9999999 999
                      b b     b b                     b b     b b                     a a     a a     9 9 9 9 9
                bbb bbbbbbb bbbbb               bbb bbbbbbb bbbbb               aaa aaaaaaa aaaaa99 99999999999
                b b b b b b b b                 b b b b b b b b                 a a a a a a a a 9 9 9 9 9 9 9
                bbbbbbbbbbbbbbbbb               bbbbbbbbbbbbbbbbb               aaaaaaaaaaaaaaaaa999999999999       aaa aaa
                  b b b b b b b b                 b b b b b b b b                 a a a a a a a a 9 9 9 9 9         a a a a
                bbbbb bbbbbbbbbbb   bbb         bbbbb bbbbbbbbbbb   bbb         aaaaa aaaaaaaaaaa999aaa9999       aaa9aaaaa
                b b     b b b b     b b         b b     b b b b     b b         a a     a a a a 9 9 a a 9         a 9 9 a
                bbbbb   bbbbbbbbb   bbbbb       bbbbb   bbbbbbbbb   bbbbb       aaaaa   aaaaaaaaa999aaaaa99 999   999 99aaa aaa
                  b b     b b b b     b b         b b     b b b b     b b         a a     a a a a 9 9 a a 9 9 9         9 a a a
                  bbb   bbbbbbbbbbb bbbbb         bbb   bbbbbbbbbbb bbbbb         aaa   aaaaaaaaaaa9aaaaa999999       99aaaaaaa
                        b b b b b b b b                 b b b b b b b b                 a a a a a a a a 9 9 9         9 a a a
                        bbbbbbbbbbbbbbbbb               bbbbbbbbbbbbbbbbb               aaaaaaaaaaaaaaaaa999999 999 9999aaaaa
                          b b b b b b b b                 b b b b b b b b                 a a a a a a a a 9 9 9 9 9 9 9 9 a
    bbb     bbb     bbb bbbbbbbbbbbbbbbbb   bbb     bbb bbbbbbbbbbbbbabbb   aaa     aaa aaaaaaaaaaaaaaaaa999aaa99999aaa9aaa
    b b     b b     b b b b b b b b b b     b b     b b b b b b b b a a     a a     a a a a a a a a a a 9 9 a a 9 9 a a a
    bbbbb   bbbbb   bbbbbbbbbbbbbbbbbbbbb   bbbbb   bbbbbbbbbbbbbbbbbaaaa   aaaaa   aaaaaaaaaaaaaaaaaaaaa999aaaaa999aaaaaaa aaa
      b b     b b     b b b b b b b b b b     b b     b b b b b b b b a a     a a     a a a a a a a a a a 9 9 a a 9 9 a a a a a
bbb bbbbbbb bbbbbbb bbbbbbbbbbbbbbbbbbbbbbb bbbbbbb bbbbbbbbbbbbbabbbaaaaaa aaaaaaa aaaaaaaaaaaaaaaaaaaaaaa9aaaaaaa9aaaaaaaaaaa
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a
bbbbbbbbbbbbbbbbbbbbb bbb bbbbbbbbbbb bbb bbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaa aaa aaaaaaaaaaa aaa aaaaaaaaaaa aaa aaa
  b b b b b b b b b         b b b b         b b b b b b b b b b b a a a a a a a a a         a a a a         a a a a
bbbbb bbbbbbbbbbbbb       bbbbbbbbb       bbbbbbbbbbbbbbbbbbbbbbbaaabbbaaaaaaaaaaaa       aaaaaaaaa       aaaaaaaaa
b b     b b b b b         b b b b         b b b b b b b b b b b a a b b a a a a a         a a a a         a a a a
bbbbb   bbbbbbbbbbb bbb   bbb bbbbb bbb   bbb bbbbbbbbbbbbbbbbbbbaaabbbbbaaaaaaaaaa aaa   aaa aaaaa aaa   aaa aaaaa aaa
  b b     b b b b b b b         b b b b         b b b b b b b b b a a b b a a a a a a a         a a a a         a a a a
  bbb   bbbbbbbbbbbbbbb       bbbbbbbbb       bbbbbbbbbbbbbbbbbbbbbabbbbbaaaaaaaaaaaaaa       aaaaaaaaa       aaaaaaaaa
        b b b b b b b         b b b b         b b b b b b b b b b b b b a a a a a a a         a a a a         a a a a
        bbbbb bbb bbb         bbb bbb       bbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaa aaa aaa         aaa aaa         aaa aaa
          b                                 b b b b b b b b b b b b b b b a
    bbb bbb                               bbbbbbbbbbbbbbbbbbbbbbbbbbbabbbaa
    b b b                                 b b b b b b b b b b b b b a a a
    bbbbbbb bbb                           bbb bbbbbbbbbbbbbbbbbbbbbbbaaaaaa aaa
      b b b b b                                 b b b b b b b b b b b a a a a a
bbb bbbbbbbbbbb                               bbbbbbbbbbbbbbbbbbbabbbaaaaaaaaaa
b b b b b b b                                 b b b b b b b b b a a a a a a a
bbbbbbbbbbbbb                               bbbbbbbbb bbb bbbbbbbaaaaaaaaaaaa       bbb bbb
  b b b b b                                 b b b b         b b b a a a a a         b b b b
bbbbb bbbbb         bbb                   bbbbbbbbb       bbbbbbbaaabbbaaaa       bbbabbbbb
b b     b           b b                   b b b b         b b b a a b b a         b a a b
bbbbb   bbb bbb     b bbb                 bbb bbbbb bbb   bbb bbbaaabbbbbaa aaa   aaa aabbb bbb
  b b     b b b         b                       b b b b         b a a b b a a a         a b b b
  bbb   bbbbbbb       bbb                     bbbbbbbbb       bbbbbabbbbbaaaaaa       aabbbbbbb
        b b b         b                       b b b b         b b b b b a a a         a b b b
        bbbbbbb bbb bbbbb                     bbb bbb       bbbbbbbbbbbbbaaaaaa aaa aaaabbbbb
          b b b b b b b b                                   b b b b b b b a a a a a a a a b
        bbbbb bbbbbbb bbb                                 bbbbbbbbbbbbbbbaaabbbaaaaabbbabbb
        b b     b b                                       b b b b b b b a a b b a a b b b
        bbbbb   bbbbb                                     bbb bbbbbbbbbbbaaabbbbbaaabbbbbbb bbb
          b b     b b                                           b b b b b a a b b a a b b b b b
          bbb     bbb                                         bbbbbbbbbbbbbabbbbbbbabbbbbbbbbbb
                                                              b b b b b b b b b b b b b b b b
                                                            bbbbbbbbb bbb bbbbbbbbbbb bbb bbb
                                                            b b b b         b b b b
                                                          bbbbbbbbb       bbbbbbbbb
                                                          b b b b         b b b b
                                                          bbb bbbbb bbb   bbb bbbbb bbb
                                                                b b b b         b b b b
                                                              bbbbbbbbb       bbbbbbbbb
                                                              b b b b         b b b b
                                                              bbb bbb         bbb bbb

[edit] Ruby

Library: Shoes
Point = Struct.new(:x, :y)
Line = Struct.new(:start, :stop)
 
Shoes.app(:width => 800, :height => 600, :resizable => false) do
 
def split_segments(n)
dir = 1
@segments = @segments.inject([]) do |new, l|
a, b, c, d = l.start.x, l.start.y, l.stop.x, l.stop.y
 
mid_x = a + (c-a)/2.0 - (d-b)/2.0*dir
mid_y = b + (d-b)/2.0 + (c-a)/2.0*dir
mid_p = Point.new(mid_x, mid_y)
 
dir *= -1
new << Line.new(l.start, mid_p)
new << Line.new(mid_p, l.stop)
end
end
 
@segments = [Line.new(Point.new(200,200), Point.new(600,200))]
15.times do |n|
info "calculating frame #{n}"
split_segments(n)
end
 
stack do
@segments.each do |l|
line l.start.x, l.start.y, l.stop.x, l.stop.y
end
end
end

[edit] Run BASIC

graphic #g, 600,600
RL$ = "R"
loc = 90
pass = 0
 
[loop]
#g "cls ; home ; north ; down ; fill black"
for i =1 to len(RL$)
v = 255 * i /len(RL$)
#g "color "; v; " 120 "; 255 -v
#g "go "; loc
if mid$(RL$,i,1) ="R" then #g "turn 90" else #g "turn -90"
next i
 
#g "color 255 120 0"
#g "go "; loc
LR$ =""
for i =len( RL$) to 1 step -1
if mid$( RL$, i, 1) ="R" then LR$ =LR$ +"L" else LR$ =LR$ +"R"
next i
 
RL$ = RL$ + "R" + LR$
loc = loc / 1.35
pass = pass + 1
render #g
input xxx
cls
 
if pass < 16 then goto [loop]
end
DragonCurveRunBasic.png

[edit] Seed7

$ include "seed7_05.s7i";
include "float.s7i";
include "math.s7i";
include "draw.s7i";
include "keybd.s7i";
 
var float: angle is 0.0;
var integer: x is 220;
var integer: y is 220;
 
const proc: turn (in integer: degrees) is func
begin
angle +:= flt(degrees) * PI / 180.0
end func;
 
const proc: forward (in float: length) is func
local
var integer: x2 is 0;
var integer: y2 is 0;
begin
x2 := x + trunc(cos(angle) * length);
y2 := y + trunc(sin(angle) * length);
lineTo(x, y, x2, y2, black);
x := x2;
y := y2;
end func;
 
const proc: dragon (in float: length, in integer: split, in integer: direct) is func
begin
if split = 0 then
forward(length);
else
turn(direct * 45);
dragon(length/1.4142136, pred(split), 1);
turn(-direct * 90);
dragon(length/1.4142136, pred(split), -1);
turn(direct * 45);
end if;
end func;
 
const proc: main is func
begin
screen(976, 654);
clear(curr_win, white);
KEYBOARD := GRAPH_KEYBOARD;
dragon(768.0, 14, 1);
ignore(getc(KEYBOARD));
end func;

Original source: [1]

[edit] Smalltalk

The classic book "Smalltalk-80 The Language and its Implementation" chapter 19 pages 372-3 includes a few lines for drawing the dragon curve (and the Hilbert curve too).


[edit] SVG

This example is in need of improvement:
Use the method described in #TI-89 BASIC to fit the curve neatly in the boundaries of the image.
Example rendering.

SVG does not support recursion, but it does support transformations and multiple uses of the same graphic, so the fractal can be expressed linearly in the iteration count of the fractal.

This version also places circles at the endpoints of each subdivision, size varying with the scale of the fractal, so you can see the shape of each step somewhat.

Note: Some SVG implementations, particularly rsvg (as of v2.26.0), do not correctly interpret XML namespaces; in this case, replace the “l” namespace prefix with “xlink”.

<?xml version="1.0" standalone="yes"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN"
"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:l="http://www.w3.org/1999/xlink"
width="400" height="400">
<style type="text/css"><![CDATA[
line { stroke: black; stroke-width: .05; }
circle { fill: black; }
]]></style>
 
<defs>
 
<g id="marks">
<circle cx="0" cy="0" r=".03"/>
<circle cx="1" cy="0" r=".03"/>
</g>
 
<g id="l0">
<line x1="0" y1="0" x2="1" y2="0"/>
<!-- useful for studying the transformation stages:
<line x1="0.1" y1="0" x2="0.9" y2="0.1"/> -->
</g>
 
<!-- These are identical except for the id and href. -->
<g id="l1"> <use l:href="#l0" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l0" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l2"> <use l:href="#l1" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l1" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l3"> <use l:href="#l2" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l2" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l4"> <use l:href="#l3" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l3" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l5"> <use l:href="#l4" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l4" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l6"> <use l:href="#l5" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l5" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l7"> <use l:href="#l6" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l6" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l8"> <use l:href="#l7" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l7" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l9"> <use l:href="#l8" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l8" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
</defs>
 
<g transform="translate(100, 200) scale(200)">
<use l:href="#marks"/>
<use l:href="#l9"/>
</g>
 
</svg>

[edit] Tcl

Works with: Tcl version 8.5
Library: Tk
package require Tk
 
set pi [expr acos(-1)]
set r2 [expr sqrt(2)]
 
proc turn {degrees} {
global a pi
set a [expr {$a + $degrees*$pi/180}]
}
proc forward {len} {
global a coords
lassign [lrange $coords end-1 end] x y
lappend coords [expr {$x + cos($a)*$len}] [expr {$y + sin($a)*$len}]
}
proc dragon {len split {d 1}} {
global r2 coords
if {$split == 0} {
forward $len
return
}
 
# This next part is only necessary to allow the illustration of progress
if {$split == 10 && [llength $::coords]>2} {
.c coords dragon $::coords
update
}
 
incr split -1
set sublen [expr {$len/$r2}]
turn [expr {$d*45}]
dragon $sublen $split 1
turn [expr {$d*-90}]
dragon $sublen $split -1
turn [expr {$d*45}]
}
 
set coords {150 180}
set a 0.0
pack [canvas .c -width 700 -height 500]
.c create line {0 0 0 0} -tag dragon
dragon 400 17
.c coords dragon $coords

See also the Tcl/Tk wiki Dragon Curves and Recursive curves pages.

[edit] TeX

[edit] PGF

Library: PGF

The PGF package includes a "lindenmayersystems" library. A dragon can be made with the "F-S" rule by defining S as a second drawing symbol. So, for plainTeX,

\input tikz.tex
\usetikzlibrary{lindenmayersystems}
 
\pgfdeclarelindenmayersystem{Dragon curve}{
\symbol{S}{\pgflsystemdrawforward}
\rule{F -> F+S}
\rule{S -> F-S}
}
\tikzpicture
\draw
[lindenmayer system={Dragon curve, step=10pt, axiom=F, order=8}]
lindenmayer system;
\endtikzpicture
\bye
 

Or fixed-direction variant to stay horizontal, this time for LaTeX,

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{lindenmayersystems}
\begin{document}
 
\pgfdeclarelindenmayersystem{Dragon curve}{
\symbol{S}{\pgflsystemdrawforward}
\rule{F -> -F++S-}
\rule{S -> +F--S+}
}
 
\foreach \i in {1,...,8} {
\hbox{
order=\i
\hspace{.5em}
\begin{tikzpicture}[baseline=0pt]
\draw
[lindenmayer system={Dragon curve, step=10pt,angle=45, axiom=F, order=\i}]
lindenmayer system;
\end{tikzpicture}
\hspace{1em}
}
\vspace{.5ex}
}
\end{document}
 

[edit] TI-89 BASIC

Translation of: SVG
Define dragon = (iter, xform)
Prgm
Local a,b
If iter > 0 Then
dragon(iter-1, xform*[[.5,.5,0][–.5,.5,0][0,0,1]])
dragon(iter-1, xform*[[–.5,.5,0][–.5,–.5,1][0,0,1]])
Else
xform*[0;0;1]→a
xform*[0;1;1]→b
PxlLine floor(a[1,1]), floor(a[2,1]), floor(b[1,1]), floor(b[2,1])
EndIf
EndPrgm
 
FnOff
PlotsOff
ClrDraw
dragon(7, [[75,0,26] [0,75,47] [0,0,1]])

Valid coordinates on the TI-89's graph screen are x 0..76 and y 0..158. This and the outer size of the dragon curve were used to choose the position and scale determined by the transformation matrix initially passed to dragon such that the curve will fit onscreen no matter the number of recursions chosen. The height of the curve is 1 unit, so the vertical (and horizontal, to preserve proportions) scale is the height of the screen (rather, one less, to avoid rounding/FP error overrunning), or 75. The curve extends 1/3 unit above its origin, so the vertical translation is (one more than) 1/3 of the scale, or 26. The curve extends 1/3 to the left of its origin, or 25 pixels; the width of the curve is 1.5 units, or 1.5·76 = 114 pixels, and the screen is 159 pixels, so to center it we place the origin at 25 + (159-114)/2 = 47 pixels.

[edit] Vedit macro language

Vedit is a text editor, so obviously there is no graphics support in the macro language. However, since Vedit can edit any file, including graphics files, it is possible to do some graphics.

This implementation first creates a blank BMP file in an edit buffer, then plots the fractal in that file, and finally calls the application associated to BMP files to display the results.

The DRAGON routine combines two steps of the algorithm used in other implementations. As a result, each turn is 90 degrees and thus all lines are vertical or horizontal (or alternatively diagonal). In addition, the length is divided by 2 instead of square root of 2 on each step. This way we can avoid using any floating point calculations, trigonometric functions etc.

File_Open("|(USER_MACRO)\dragon.bmp", OVERWRITE+NOEVENT)
BOF Del_Char(ALL)
 
#11 = 640 // width of the image
#12 = 480 // height of the image
Call("CREATE_BMP")
 
#1 = 384 // dx
#2 = 0 // dy
#3 = 6 // depth of recursion
#4 = 1 // flip
#5 = 150 // x
#6 = 300 // y
Call("DRAGON")
Buf_Close(NOMSG)
 
Sys(`start "" "|(USER_MACRO)\dragon.bmp"`, DOS+SUPPRESS+SIMPLE+NOWAIT)
return
 
/////////////////////////////////////////////////////////////////////
//
// Dragon fractal, recursive
//
:DRAGON:
if (#3 == 0) {
Call("DRAW_LINE")
} else {
#1 /= 2
#2 /= 2
#3--
if (#4) {
Num_Push(1,4) #4=1; #7=#1; #1=#2; #2=-#7; Call("DRAGON") Num_Pop(1,4)
Num_Push(1,4) #4=0; Call("DRAGON") Num_Pop(1,4)
Num_Push(1,4) #4=1; #7=#1; #1=-#2; #2=#7; Call("DRAGON") Num_Pop(1,4)
Num_Push(1,4) #4=0; Call("DRAGON") Num_Pop(1,4)
} else {
Num_Push(1,4) #4=1; Call("DRAGON") Num_Pop(1,4)
Num_Push(1,4) #4=0; #7=#1; #1=-#2; #2=#7; Call("DRAGON") Num_Pop(1,4)
Num_Push(1,4) #4=1; Call("DRAGON") Num_Pop(1,4)
Num_Push(1,4) #4=0; #7=#1; #1=#2; #2=-#7; Call("DRAGON") Num_Pop(1,4)
}
}
return
 
/////////////////////////////////////////////////////////////////////
//
// Daw a horizontal, vertical or diagonal line. #1 = dx, #2 = dy
//
:DRAW_LINE:
while (#1 || #2 ) {
#21 = (#1>0) - (#1<0)
#22 = (#2>0) - (#2<0)
#5 += #21; #1 -= #21
#6 += #22; #2 -= #22
Goto_Pos(1078 + #5 + #6*#11)
IC(255, OVERWRITE) // plot a pixel
}
return
 
/////////////////////////////////////////////////////////////////////
//
// Create a bitmap file
//
:CREATE_BMP:
 
// BITMAPFILEHEADER:
IT("BM") // bfType
#10 = 1078+#11*#12 // file size
Call("INS_4BYTES")
IC(0, COUNT, 4) // reserved
#10 = 1078; Call("INS_4BYTES") // offset to bitmap data
 
// BITMAPINFOHEADER:
#10 = 40; Call("INS_4BYTES") // size of BITMAPINFOHEADER
#10 = #11; Call("INS_4BYTES") // width of image
#10 = #12; Call("INS_4BYTES") // height of image
IC(1) IC(0) // number of bitplanes = 1
IC(8) IC(0) // bits/pixel = 8
IC(0, COUNT, 24) // compression, number of colors etc.
 
// Color table - create greyscale palette
for (#1 = 0; #1 < 256; #1++) {
IC(#1) IC(#1) IC(#1) IC(0)
}
 
// Pixel data - init to black
for (#1 = 0; #1 < #12; #1++) {
IC(0, COUNT, #11)
}
return
 
//
// Write 32 bit binary value from #10 in the file
//
:INS_4BYTES:
for (#1 = 0; #1 < 4; #1++) {
Ins_Char(#10 & 0xff)
#10 = #10 >> 8
}
return

[edit] X86 Assembly

DragX86.gif

Translation of XPL0. Assemble with tasm, tlink /t

        .model  tiny
.code
.486
org 100h ;assume ax=0, bx=0, sp=-2
start: mov al, 13h ;(ah=0) set 320x200 video graphics mode
int 10h
push 0A000h
pop es
mov si, 8000h ;color
 
mov cx, 75*256+100 ;coordinates of initial horizontal line segment
mov dx, 75*256+164 ;use power of 2 for length
 
call dragon
mov ah, 0 ;wait for keystroke
int 16h
mov ax, 0003h ;restore normal text mode
int 10h
ret
 
dragon: cmp sp, -100 ;at maximum recursion depth?
jne drag30 ;skip if not
mov bl, dh ;draw at max depth to get solid image
imul di, bx, 320 ;(bh=0) plot point at X=dl, Y=dh
mov bl, dl
add di, bx
mov ax, si ;color
shr ax, 13
or al, 8 ;use bright colors 8..F
stosb ;es:[di++]:= al
inc si
ret
drag30:
push cx ;preserve points P and Q
push dx
 
xchg ax, dx ;DX:= Q(0)-P(0);
sub al, cl
sub ah, ch ;DY:= Q(1)-P(1);
 
mov dx, ax ;new point
sub dl, ah ;R(0):= P(0) + (DX-DY)/2
jns drag40
inc dl
drag40: sar dl, 1 ;dl:= (al-ah)/2 + cl
add dl, cl
 
add dh, al ;R(1):= P(1) + (DX+DY)/2;
jns drag45
inc dh
drag45: sar dh, 1 ;dh:= (al+ah)/2 + ch
add dh, ch
 
call dragon ;Dragon(P, R);
pop cx ;get Q
push cx
call dragon ;Dragon(Q, R);
 
pop dx ;restore points
pop cx
ret
end start

[edit] Xfractint

The xfractint program includes two dragon curves in its lsystem/fractint.l. Here is another version. Xfractint has only a single "F" drawing symbol, so empty symbols X and Y are used for even and odd positions to control the expansion. Each X and each Y is always followed by a single F each.

Dragon3 {
Angle 4
Axiom XF
X=XF+Y
Y=XF-Y
}

Put this in a file dragon3.l and run as follows. params=8 means an 8-order curve.

xfractint type=lsystem lfile=dragon3.l lname=Dragon3 params=8

[edit] XPL0

DragonXPL0.gif
include c:\cxpl\codes;          \intrinsic 'code' declarations
 
proc Dragon(D, P, Q); \Draw a colorful dragon curve
int D, P, Q; \recursive depth, coordinates of line segment
int R(2), \coordinates of generated new point
DX, DY, C; \deltas, color
[C:= [0]; \color is a local, static-like variable
D:= D+1; \depth of recursion increases
if D >= 13 then \draw lines at maximum depth to get solid image
[Move(P(0), P(1)); Line(Q(0), Q(1), C(0)>>9+4!8); C(0):= C(0)+1; return];
DX:= Q(0)-P(0); DY:= Q(1)-P(1);
R(0):= P(0) + (DX-DY)/2; \new point
R(1):= P(1) + (DX+DY)/2;
Dragon(D, P, R); \draw two segments that include the new point
Dragon(D, Q, R);
];
 
int X, Y, P(2), Q(2);
[SetVid($101); \set 640x480 video graphics mode
X:= 32; Y:= 32; \coordinates of initial horizontal line segment
P(0):= X; P(1):= Y;
Q(0):= X+64; Q(1):= Y; \(power of two length works best for integers)
Dragon(0, P, Q); \draw its dragon curve
X:= ChIn(1); \wait for keystroke
SetVid(3); \restore normal text mode
]

[edit] zkl

Draw the curve in SVG to stdout.

Translation of: Perl 6
println(0'|<?xml version='1.0' encoding='utf-8' standalone='no'?>|"\n"
0'|<!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 1.1//EN'|"\n"
0'|'http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd'>|"\n"
0'|<svg width='100%' height='100%' version='1.1'|"\n"
0'|xmlns='http://www.w3.org/2000/svg'>|);
 
order:=13.0; # akin to number of recursion steps
d_size:=1000.0; # size in pixels
pi:=(1.0).pi;
turn_angle:=pi/2; # turn angle of each segment, 90 degrees for the canonical dragon
 
angle:=pi - (order * (pi/4)); # starting angle
len:=(d_size/1.5) / (2.0).sqrt().pow(order); # size of each segment
x:=d_size*5/6; y:=d_size*1/3; # starting point
 
foreach i in ([0 .. (2.0).pow(order-1)]){
# find which side to turn based on the iteration
angle += i.bitAnd(-i).shiftLeft(1).bitAnd(i) and -turn_angle or turn_angle;
 
dx:=x + len * angle.sin(); dy:=y - len * angle.cos();
println("<line x1='",x,"' y1='",y,"' x2='",dx,"' y2='",dy,
"' style='stroke:rgb(0,0,0);stroke-width:1'/>");
x=dx; y=dy;
}
println("</svg>");
Output:
$zkl bbb > dragon.svg
$ls -l dragon.svg 
... 408780 May 18 00:29 dragon.svg
$less dragon.svg 
<?xml version='1.0' encoding='utf-8' standalone='no'?>
<!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 1.1//EN'
'http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd'>
<svg width='100%' height='100%' version='1.1'
xmlns='http://www.w3.org/2000/svg'>
<line x1='833.333' y1='333.333' x2='838.542' y2='328.125' style='stroke:rgb(0,0,0);stroke-width:1'/>
....
Visiting file:///home/craigd/Projects/ZKL/Tmp/dragon.svg shows a nice dragon curve
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox