Drawing the dragon curve

Question

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?

Answer 1

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

Update adds variant with rounded corners (see end of answer).

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}

\def\IterateDragon {\advance\Iter 1
    % adjust initial direction, rotating 45 degrees clockwise
    \count255 = \DeltaX
    \advance\DeltaX by  \DeltaY
    \advance\DeltaY by -\count255
    % adjust scale
    \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
\def\DrawSegment {\advance\X\DeltaX
                  \advance\Y\DeltaY 
                  \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 {%
    \global\advance\Iter 1
    % adjust initial direction, rotating 45 degrees clockwise
    \count255 = \DeltaX
    \global\advance\DeltaX by  \DeltaY
    \global\advance\DeltaY by -\count255
    % adjust scale
    \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}

Answer 2

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}

Answer 3

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
  \multido{\i=0+1}{10}{% Add 10 more folds
    % Add 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).

Answer 4

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:

Answer 5

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.

Answer 6

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.

Answer 7

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 : 
    dragonr := (reverse dragon) rotatedabout(b,-90);
    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;

Answer 8

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.

Answer 9

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);