# Drawing the dragon curve

I'd like to draw the dragon curve (or paper-folding curve) in a programmatic way. For example, create a sequence representing the curves, and then parse the sequence to draw the curve.

The sequence is well-documented on he On-Line Encyclopedia of Integer Sequences/OEIS as A014577, and here is one definition (generation via string substitution):

Start: L
Rules:
L --> L1R
R --> L0R
0 --> 0
1 --> 1
-------------
0:   (#=1)
L
1:   (#=3)
L1R
2:   (#=7)
L1R1L0R
3:   (#=15)
L1R1L0R1L1R0L0R
4:   (#=31)
L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R
5:   (#=63)
L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R1L1R1L0R1L1R0L0R0L1R1L0R0L1R0L0R
Drop all L and R to obtain 1101100111001001110110001100100


The complete sequence showing n folds would have 2^n-1 elements. Here is a recursive view on drawing the sequence:

How can I do this?

A solution using Plain TeX macros and LaTeX's picture environment (enhanced by pict2e package).

and this time starting rightwards (animation updated):

Variant with rounded corners at bottom.

\documentclass[multi=picture,ignorerest=false]{standalone}

% convert -density 150 -verbose -delay 40 -dispose None DG/dragoncurve.* -delay 200 DG/dragoncurve.13.png -loop 0  dragoncurve.gif

\usepackage{pict2e}
\usepackage{color}
\usepackage{picture}

\newcount\X % integer horizontal coordinate
\newcount\Y % integer vertical coordinate

\newdimen\E % initial scale
\E 4cm

\newcount\Iter % iteration level, for displaying
\Iter = 1

\newcount\DeltaX
\newcount\DeltaY
% initial direction for first drawn Dragon curve (has two segments)
\DeltaX = -1
\DeltaY = 1

\let\LL\relax
\let\RR\relax

\def\Dragon {\L}

% adjust initial direction, rotating 45 degrees clockwise
\count255 = \DeltaX
\E = 0.5\E
% apply rules
\def\L{\noexpand\L\LL\noexpand\R}%
\def\R{\noexpand\L\RR\noexpand\R}%
\edef\Dragon{\Dragon}%
}

% draw one segment in given direction and with current scale
\lineto(\X,\Y)}

\def\DrawDragon {%
\setlength{\unitlength}{\E}%
\begin{picture}(13cm,9cm)(-9.5cm,-3cm)
\linethickness{1.5pt}%
\def\L {\count255 = \DeltaX
\DeltaX = -\DeltaY
\DeltaY = \count255
\DrawSegment }%
\def\R {\count255 = \DeltaX
\DeltaX = \DeltaY
\DeltaY = -\count255
\DrawSegment }%
\let\LL\L
\let\RR\R
\X = 0
\Y = 0
\put(0,0){\textcolor{blue}{\phantom{x}\the\Iter}}
\moveto(0,0)
\DrawSegment
\Dragon
\strokepath
\end{picture}}

\begin{document}

\ttfamily

\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

\IterateDragon
\DrawDragon

% twelfth .. slow

\IterateDragon
\DrawDragon

% thirteenth .... sloooww

\IterateDragon
\DrawDragon

\end{document}


Code variant for rounded corners:

\documentclass[multi=picture,ignorerest=false]{standalone}

% convert -density 75 -verbose -dispose none -delay 100 -- DG3/dragoncurve3.* -delay 200 DG3/dragoncurve3.12.png -loop 0  dragoncurve3.gif

\usepackage{pict2e}
\usepackage{color}
\usepackage{picture}

\newcount\X % integer horizontal coordinate
\newcount\Y % integer vertical coordinate
% for convenience another pair
\newcount\x
\newcount\y

\newdimen\E % initial scale
\E 1cm

\newcount\Iter % iteration level, for displaying
\Iter = 1

\newcount\DeltaX
\newcount\DeltaY
% initial direction for first drawn Dragon curve (has two segments)
% this version goes rightward
\DeltaX = 1
\DeltaY = -1

% for convenience another pair
\newcount\deltax
\newcount\deltay

% (the first iterate goes down then up, thus turning left).
\def\Dragon {\L}

\def\IterMode {%
\let\LL\relax
\let\RR\relax
%
\def\L{\noexpand\L\LL\noexpand\R}%
\def\R{\noexpand\L\RR\noexpand\R}%
}

\def\DrawMode {%
\def\L {\deltax = -\DeltaY
\deltay = \DeltaX
\DrawArc
}%
\def\R {\deltax = \DeltaY
\deltay = -\DeltaX
\DrawArc
}%
\let\LL\L
\let\RR\R
}

\def\DrawArc {%
\x\numexpr \X + 2*\DeltaX + 2*\deltax\relax
\y\numexpr \Y + 2*\DeltaY + 2*\deltay\relax
\curveto
(\numexpr\X+\DeltaX\relax,\numexpr\Y+\DeltaY\relax)%
(\numexpr\x-\deltax\relax,\numexpr\y-\deltay\relax)%
(\x,\y)%
\X\x
\Y\y
\DeltaX\deltax
\DeltaY\deltay
}%

\def\IterateDragon {%
% adjust initial direction, rotating 45 degrees clockwise
\count255 = \DeltaX
\global\E = 0.5\E
% apply rules and modify \Dragon globally
\IterMode
\xdef\Dragon{\Dragon}%
}

\def\DrawDragonPath #1{%
\linethickness{#1}%
\ifodd\Iter\color{red}\else\color{blue}\fi
\moveto(0,0)
\X\numexpr2*\DeltaX\relax
\Y\numexpr2*\DeltaY\relax
\lineto(\X,\Y)
\DrawMode
\Dragon
\X\numexpr\X+2*\DeltaX\relax
\Y\numexpr\Y+2*\DeltaY\relax
\lineto(\X,\Y)
\strokepath
}%

\def\DrawOneDragon #1{%
\setlength{\unitlength}{\E}%
\begin{picture}(12.35cm,8.6cm)(-2.85cm,-5.6cm)
\DrawDragonPath {#1}%
\put(0,0){\llap{\the\Iter\phantom{x}}}%
\end{picture}%
}

\def\DrawTwoDragons {% draws AND iterates once to get next curve too.
\setlength{\unitlength}{\E}%
\begin{picture}(12.35cm,8.6cm)(-2.85cm,-5.6cm)
% je fais ça vite fait, car avec convert je n'ai pas vu comment avoir deux
% rémanences, donc on fait deux dessins ici.
% we store initial direction:
\count2=\DeltaX
\count4=\DeltaY
\DrawDragonPath {1pt}%
% restore initial direction (which will be rotated 45° by \IterateDragon)
\DeltaX \count2
\DeltaY \count4
\IterateDragon % does \IterMode, makes global changes to \Dragon etc...
% compensate (only in this picture) for scale being left the same.
\divide\DeltaX by 2
\divide\DeltaY by 2
\DrawDragonPath {1.5pt}%
\put(0,0){\llap{\the\Iter\phantom{x}}}%
\end{picture}%
}

\begin{document}

\ttfamily

\DrawOneDragon {1.5pt}%1

\DrawTwoDragons %2

\DrawTwoDragons %3

\DrawTwoDragons %4

\DrawTwoDragons %5

\DrawTwoDragons %6

\DrawTwoDragons %7

\DrawTwoDragons %8

\DrawTwoDragons %9

\DrawTwoDragons %10

\DrawTwoDragons %11

\DrawOneDragon {1pt}%

\end{document}


• @DavidCarlisle I now intervene only in emergency situations like this one... ;) – user4686 Feb 27 '15 at 19:40
• Although the generation of the symbolic left and right turns is not the time costly part (much more time is taken up by pict2e), for the sake of completeness let me mention that I could have used a much faster expansion trick: rather than iterating the rules L->L1R, R->L0R from the OP via \edef, where the 1 and 0 (\LL and RR in my code) are inert, it is much faster to iterate the global recursions A<-ALB, B<-ARB and the final output is ALB (A and B empty at first). One can even do it with \expandafters only, no need for \edef. – user4686 Mar 2 '15 at 21:30
• \def\A {}, \def\B {}, \let\L \relax, \let\R \relax, \def\Iterate {% \expandafter\expandafter\expandafter\def \expandafter\expandafter\expandafter\C \expandafter\expandafter\expandafter {\expandafter\A\expandafter\L\B}% \expandafter\expandafter\expandafter\def \expandafter\expandafter\expandafter\B \expandafter\expandafter\expandafter {\expandafter\A\expandafter\R\B}% \let\A\C }% – user4686 Mar 2 '15 at 21:31

As a Lindenmayer system, the dragon curve can be presented by

angle 90°
initial string FX
string rewriting rules
X ↦ X+YF+
Y ↦ −FX−Y.


so we have a simple TikZ solution using lindenmayersystems library:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{lindenmayersystems}

\begin{document}

\fbox{%
\tikz[rotate=65]
\draw[green!60!black]
l-system
[l-system={
rule set={X -> X+YF+,Y->-FX-Y},
axiom=FX,
angle=90,
order=12,
step=5pt
}
];
}

\end{document}


Changing to order=14 and reducing the step to 2pt gives:

And my computer reports pretty decent times:

real    0m48.379s
user    0m46.404s
sys     0m0.120s


However, order=15 already produces the dreadful TeX capacity exceeded! error.

A little beamer animation up to order 12:

\documentclass{beamer}
\usepackage{tikz}
\usetikzlibrary{lindenmayersystems}

\begin{document}

\begin{frame}
\centering
\tikz
\foreach \Valor in {1,2,...,12}
\draw<\Valor>[green!60!black]
l-system
[l-system={
rule set={X -> X+YF+,Y->-FX-Y},
axiom=FX,
angle=90,
order=\Valor,
step=3pt
}
];
\end{frame}

\end{document}


## Rounded version

The rounded version is obtained simply by adding rounded corners=<length> to the options for the \draw; a little example of order 11:

\documentclass[border=3pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{lindenmayersystems}

\begin{document}

\tikz
\draw[green!60!black,rounded corners=4pt]
l-system
[l-system={
rule set={X -> X+YF+,Y->-FX-Y},
axiom=FX,
angle=90,
order=11,
step=10pt
}
];

\end{document}


The result:

## Twindragon

The Davis-Knuth dragon can also be easily obtained:

\documentclass[tikz,border=3pt]{standalone}
\usetikzlibrary{lindenmayersystems}

\begin{document}

\tikz\draw[line width=1pt,green!60!black,rounded corners]
l-system
[l-system={
rule set={X -> X+YF,Y->FX-Y},
axiom=FX+FX+,
angle=90,
order=12,
step=10pt
}
];

\end{document}


Here is one implementation, using PSTricks.

The sequence is generated via repetitive string replacements using xstring's \StrSubstitute:

\documentclass{article}
\usepackage[paper=a3paper,landscape,margin=0pt]{geometry}
\usepackage{etoolbox,pstricks,xstring,multido}
\pagestyle{empty}
\begin{document}

\begin{pspicture}(-25cm,-10cm)(10cm,7cm)
\psset{unit=5mm}
\SpecialCoor

\def\dragoncurve{L,1R}% Starting fold
\StrSubstitute{\dragoncurve}{L}{L,1P}[\dragoncurve]% L -> L1P
\StrSubstitute{\dragoncurve}{R}{L,0R}[\dragoncurve]% R -> L0R
\StrSubstitute{\dragoncurve}{P}{R}[\dragoncurve]% P -> R
\xdef\dragoncurve{\dragoncurve}% Make definition global
}

\StrSubstitute{\dragoncurve}{L}{}[\dragoncurve]% Drop L
\StrSubstitute{\dragoncurve}{R}{}[\dragoncurve]% Drop R
\StrSubstitute[1]{\dragoncurve}{,}{}[\dragoncurve]% Drop first ,
\def\nextangle{0}% Starting angle
\pscustom[linewidth=.1pt]{
\psline(0,0)% Initial node
\renewcommand{\do}[1]{
\rlineto(1;\nextangle)% Draw next line
\xdef\nextangle{\number\numexpr\nextangle+\ifnum#1=1 (-90)\else (90)\fi}
}%
\expandafter\docsvlist\expandafter{\dragoncurve}% Process dragon curve
\rlineto(1;\nextangle)% Draw final line
}
\end{pspicture}

\end{document}


The production is only limited by TeX's memory. With the default settings, perhaps 12 folds can be made (compiling for a very long time, and having to use a very large paper size or adjustments to the unit and/or runit).

• I think \SpecialCoor has been enabled by default. I don't remember the exact version. – kiss my armpit Feb 27 '15 at 17:55

Here's a sagetex solution:

\documentclass{standalone}
\usepackage{sagetex}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usepackage{pgfplots}
\pagestyle{empty}
\begin{document}
\begin{sagesilent}
N = 15
def Rotate(A,P,degrees):
A1 = [A[0]-P[0],A[1]-P[1]]
theta = degrees*pi/180
R = [A1[0]*cos(theta)-A1[1]*sin(theta), A1[0]*sin(theta)+A1[1]*cos(theta)]
return [R[0]+P[0],R[1]+P[1]]

G = Graphics()
Start = [1,0]
Finish = [0,0]
Curve = [[1,0], [0,0]]
n = 1

while n<N:
CurveR=[]
for i in range(0,len(Curve)-1):
CurveR += [Rotate(Curve[i],Curve[len(Curve)-1],-90)]
for i in range(len(CurveR)-1,-1,-1):
Curve += [CurveR[i]]
n += 1

G += line(Curve)
Gplot = G.plot(aspect_ratio=1,axes=False)
\end{sagesilent}
\sageplot{Gplot,axes=False}
\end{document}


The code above has N=15 and gives this output without taking much time: Because a computer algebra system is handling the computations you can push the number of iterations higher. I had to increase the size of the buffer (shown in the picture below as buf_size=1000000) to get output for N=17--compilation time moved up noticeably: I'm unable to get output for N=18, getting an "undefined" error.

Creating the graphics in Sage (not LaTeX) will let us get more iterations. Using the animate command to link them together gives us this animated GIF:

A MetaPost solution, inside a LuaLaTeX program.

\documentclass{standalone}
\usepackage{luamplib}
\mplibnumbersystem{double}
\begin{document}
\begin{mplibcode}

vardef dragon(expr A, B, n) =
if n = 0: draw A--B;
else: save C; pair C; C = A rotatedaround (.5[A,B], 90);
dragon(A, C, n-1);
dragon(B, C, n-1); fi
enddef;

beginfig(1);
dragon(origin, (12cm, 0), 18);
endfig;
\end{mplibcode}
\end{document}


For 14 levels of recursions:

Now for 18 levels of recursion. It takes less than half a minute for my old laptop (2008). Further tests on the way, to test MetaPost's limits, but it won't change the graph itself very much anyway :-)

Edit: The result for 21 levels, produced in a little less than 3 minutes. As you see, the figure is sort of "smoothed". MetaPost can go further, I guess, but it slows down my old machine very much during the process. I think I'll stop here :-)

Edit: The recursion has been much simplified. Also, following Thruston's example, I've used a simpler new point computation (C = A rotatedaround (.5[A,B], 90) instead of C = B + .5sqrt2*(A-B) rotated 45. It may speed up the compilation time a bit.

As there is no tikzmath solution yet. Here is one.

\documentclass[tikz,border=7mm]{standalone}
\usetikzlibrary{math}
\tikzmath{
function Segment(\x,\y,\angle,\lr,\step){
int \step, \newangle;
if \step > 0 then {
\step  = \step - 1;
% draw the first falding
\newangle = mod(\angle-(\lr*45),360);
Segment(\x,\y,\newangle,1,\step);
% draw the second falding
\nlen = 2^(\step/2);
\x = \x + \nlen*cos(\newangle);
\y = \y + \nlen*sin(\newangle);
\newangle = mod(\angle+(\lr*45),360);
Segment(\x,\y,\newangle,-1,\step);
}
else { % draw one segment
{ \draw[shift={(\x,\y)}] (0,0) -- (\angle:1); };
};
};
}
\begin{document}
\begin{tikzpicture}[red,scale=.07]
\tikzmath{Segment(0,0,30,1,14);}
\end{tikzpicture}
\end{document}


Note : The maximal level of recursion is 14. For 15 we obtain TeX capacity exceeded!. And it is very slow : 4 minutes for 14 levels of recursion.

This is another MetaPost solution.

The curve is constructed globally recursively : one only needs adding at its extremity a 90° rotated copy of itself.

Also, the tiling property is illustrated (at level 11, i.e. each of the four "curve" has 2**11segments.)

A second animation, displayed first here, now added in last update, to illustrate even more the tiling properties. It is at level 8.

Don't stare at the one below too long !

prologues := 3;

% I did not get satisfactory result when trying png output
% with a black background hence I go via svg.

outputformat := "svg";
outputformatoptions := "format=rgb";
outputtemplate := "%j%c.svg";

beginfig(1);

pair a, b;
a := origin; b := right scaled 10pt;

path dragon, dragonr;

dragon := a -- b;

for t=1 upto 11 :
dragon  := (dragon & dragonr);
b := a rotatedabout(b,-90); % new end point
% there must be some primitive for the end point of a path
% but somehow I did not find it (fast enough) in the manual
% of metapost
endfor ;

pickup pencircle scaled 1.5pt ;

picture Dragons;

Dragons := image(
draw dragon withcolor (1,0.92,0) ;
draw dragon rotated 90 withcolor (0.83,0.83,0) ;
draw dragon rotated 180 withcolor (0.6, 0.75, 0.05) ;
draw dragon rotated 270 withcolor (0.5,0.6,0.1) ;
);

fill bbox Dragons withcolor black ;

draw Dragons ;

endfig;

end;

• The last point of a path pat you can get by point infinity of pat. See p. 33 of the MetaPost manual, at least the version available in TeX Live 2014. – Franck Pastor Feb 28 '15 at 19:09
• as it happens, infinity had just been discussed in the comments of this answer to another subject: tex.stackexchange.com/questions/230588/… ;-) – Franck Pastor Feb 28 '15 at 19:12
• oh, by the way I have shamelessly used ColorPicker to get RGB values from a similar image on wikipedia's page. – user4686 Feb 28 '15 at 19:18
• @fpast I see it mentioned in the Metapost manual now. Searching for end point did not give anything, I should have looked for end of a path (not end of path, sadly) ... or infinity if I had some kind of otherworldly prescience :) – user4686 Feb 28 '15 at 19:22
• Speaking of colours: As for me, I never got the grip on the RGB, CMYB, etc. systems. I prefer to use the very handy mpcolornames package instead! ftp.snt.utwente.nl/pub/software/tex/graphics/metapost/contrib/… – Franck Pastor Feb 28 '15 at 19:27

And another version in Metapost, but one that's a bit more like the version with rounded corners in the Knuth video, linked in the OP comments. I've also superimposed a grid to show that you could indeed create this using just three types of tiles (except for the beginning and end).

prologues := 3;
outputtemplate := "%j%c.eps";

vardef do_dragon(expr a, b, c, offset, depth) =
save m; pair m; m := c rotatedabout(.5[a,b],90);
corners[floor (0.5+offset+2**depth)] := m;
if depth>0:
do_dragon(a,m,a,offset,depth-1);
do_dragon(m,b,b,offset+2**depth,depth-1);
fi
enddef;

beginfig(1);

depth = 10;
pair a, b;
a = origin; b = right scaled 13cm if odd(depth): rotated 45 fi;

pair corners[];
corners[floor (0.5+2**depth)] = b;
do_dragon(a,b,a,0,depth-1);

path dragon;
dragon = a for i=1 upto 2**depth: -- corners[i] endfor;

path curly_track;
curly_track = a for t=1/2 upto length(dragon):
.. {direction t of dragon} point t of dragon
endfor .. b;

u = length(point 1 of dragon - point 2 of dragon);
path frame; frame = llcorner dragon + (-u,-u)/2
-- lrcorner dragon + (+u,-u)/2
-- urcorner dragon + (+u,+u)/2
-- ulcorner dragon + (-u,+u)/2 -- cycle;

% background
fill frame withcolor .7 white;

% track
for s = .4, .8, 1:
draw curly_track withpen pencircle scaled (2.6-2s) withcolor s[1/6 red+ 1/3 green, 1/2 red+ 1/2 green];
endfor

% tiles grid
n := 0;
for x = 0 step u until length(lrcorner frame - llcorner frame):
draw (llcorner frame -- ulcorner frame) shifted (x,0) withcolor .8 white;
if incr n mod 10 = 0: label.bot(decimal n, llcorner frame shifted (x+u,0)); fi
endfor
n := 0;
for y = 0 step u until length(ulcorner frame - llcorner frame):
draw (llcorner frame -- lrcorner frame) shifted (0,y) withcolor.8 white;
if incr n mod 10 = 0: label.lft(decimal n, llcorner frame shifted (0,y+u)); fi
endfor

% frame
draw frame withpen pencircle scaled 2 withcolor 3/4 red + 1/4 green;

endfig;
end.


Here's what it looks like at depth=9. Note that you have to rotate it to get the tiles to match properly.

• Quite out of topic, just out of curiosity: why do you give your MetaPost pictures the .eps extension, instead of .mps (or converting them to PDF)? – Franck Pastor Feb 28 '15 at 13:11
• @fpast - if you use .eps and set prologues:=3; then xelatex automagically includes the pictures. This does not always work, so sometimes I use epstopdf instead. The .mps extension was supposed to be for MP's own version of eps without the fonts included (ie with prologues:=1). – Thruston Feb 28 '15 at 13:37
• Have you considered using mptopdf instead? It makes the use of prologues irrelevant. This utility can be applied to the MetaPost file (with the drawback that it does not handle the numbersystem option) as well at its PostScript output files (which is usually preferable). – Franck Pastor Feb 28 '15 at 19:22
• @fpast the other advantage of using .eps is that Skim (and Preview.app) can open them directly, and update the view when I recompile. I like this workflow. – Thruston Mar 1 '15 at 0:54

Since there are not been any attempt with Asymptote up to now, I decided to have a go with it. It is in fact a translation of my former attempt with MetaPost, which was already very short, but this one may win the prize for the shortest code solving the OP's problem :-)

void dragon(pair A, pair B, int n){
if (n == 0) {draw (A--B);}
else {pair C = rotate(90, interp(A, B, 0.5))*A;
dragon(A, C, n-1);
dragon(B, C, n-1);}}

dragon((0, 0), (12cm, 0), 14);


Below one result, for a recursion depth of 14. I prefer not to overload the topic with pictures which would have been exactly the same as with MetaPost, the performances of both programs at drawing a dragon seeming perfectly equivalent :-)

I project to add an Asymptote-made animation later, if I manage to make one since it would be my first animation ever with this program.

Edit I managed to produced this (GIF) animation (up to depth 18). With weird visual effects I'm unable to explain and to suppress :-(

Edit bis An attempt at the ‘twin dragons’, which could be a start for a proper tiling like the amazing ones in other answers.

void dragon(pair A, pair B, int n){
if (n == 0) {draw (A--B);}
else {pair C = rotate(90, interp(A, B, 0.5))*A;
dragon(A, C, n-1);
dragon(B, C, n-1);}}

void twin_dragons(pair A, pair B, int n){
if (n==0) {draw (A--B);}
else{
currentpen=blue; dragon(A, B, n);
currentpen=red; dragon(B, A, n);}}

twin_dragons((0, 0), (12cm, 0), 19);