{"id":3212,"date":"2018-04-06T09:00:28","date_gmt":"2018-04-06T14:00:28","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=3212"},"modified":"2018-04-16T08:10:13","modified_gmt":"2018-04-16T13:10:13","slug":"the-dragon-curve","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2018\/04\/06\/the-dragon-curve\/","title":{"rendered":"The Dragon Curve"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Let me tell you about a beautiful, fractal curve, the Dragon Curve. Download my new <tt>dragon<\/tt> program from the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/66744-dragon\">File Exchange<\/a> and follow along.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_movie.gif\" alt=\"\"> <\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#ae9e6166-c6dd-4d54-9edf-509eba4e3222\">Folding paper<\/a><\/li><li><a href=\"#35c42211-901a-4df5-8ec0-729f9a568a9a\">Signature<\/a><\/li><li><a href=\"#6375f303-7763-4cee-86f0-b09415e3adfb\">Folds<\/a><\/li><li><a href=\"#8525bb96-7ceb-4a47-969d-643ac71a4b37\">Rotations<\/a><\/li><li><a href=\"#af82d7d1-33c6-4d38-8166-6704715e0796\">Translates<\/a><\/li><li><a href=\"#23825097-195c-4ad1-b0db-ca1eef257b07\">Pendant<\/a><\/li><li><a href=\"#3f81a11a-b41e-498b-a4d5-4839ff1a511b\">Dragon<\/a><\/li><li><a href=\"#4fcafb93-cd8f-48a6-94ff-e35e9b78de50\">Videos<\/a><\/li><\/ul><\/div><h4>Folding paper<a name=\"ae9e6166-c6dd-4d54-9edf-509eba4e3222\"><\/a><\/h4><p>Start with a long, narrow strip of paper, like the one in the following photograph.  Fold it in half once, end over end. Then fold it a second time, being careful to fold in the same direction, right over left or left over right, as the first. Then a third fold, and a fourth.  Unfold the strip so that all the folds form the right angles pictured.  You will have created a Dragon Curve of degree four.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_folds.jpg\" alt=\"\"> <\/p><p>Image credit: <a href=\"http:\/\/www.cutoutfoldup.com\/216-dragon-curve.php\">http:\/\/www.cutoutfoldup.com\/216-dragon-curve.php<\/a><\/p><p>How many times do you imagine you could fold the paper before it is too thick to fold again?  Probably five, maybe six.<\/p><h4>Signature<a name=\"35c42211-901a-4df5-8ec0-729f9a568a9a\"><\/a><\/h4><p>The degree one curve has one right angle; let's denote that by R. The degree two curve has two right angles, followed by a left; that's RRL.  The degree three signature is RRLRRLL.<\/p><p>Can you read off the signature of degree four from the photo? Do you see the pattern?  Probably not yet.<\/p><p>The number of segments between folds doubles with each increase in degree.   Here's code to display the signatures of degrees one through six.   That's all I can display in one column of this blog post.<\/p><p>The key operation in the code is <tt>LR-fliplr(s)<\/tt>. That flips the string <tt>s<\/tt> end to end and replaces all the R's by L's and the L's by R's.<\/p><pre class=\"codeinput\">    s = <span class=\"string\">'R'<\/span>;\r\n    disp(s)\r\n    LR = <span class=\"string\">'L'<\/span>+<span class=\"string\">'R'<\/span>;\r\n    <span class=\"keyword\">for<\/span> n = 2:6\r\n        s = [s <span class=\"string\">'R'<\/span> LR-fliplr(s)];\r\n        disp(s)\r\n    <span class=\"keyword\">end<\/span>\r\n<\/pre><pre class=\"codeoutput\">R\r\nRRL\r\nRRLRRLL\r\nRRLRRLLRRRLLRLL\r\nRRLRRLLRRRLLRLLRRRLRRLLLRRLLRLL\r\nRRLRRLLRRRLLRLLRRRLRRLLLRRLLRLLRRRLRRLLRRRLLRLLLRRLRRLLLRRLLRLL\r\n<\/pre><h4>Folds<a name=\"6375f303-7763-4cee-86f0-b09415e3adfb\"><\/a><\/h4><p>The following figures are all from my new MATLAB program, <tt>dragon<\/tt>. The computations are based on a growing and shrinking vector <tt>z<\/tt> of points in the complex plane.<\/p><p>Start with<\/p><pre>  z = [0 1]<\/pre><p>This isn't complex yet, but it soon will be. When we plot <tt>z<\/tt>, we get a single black line, representing an unfolded strip of paper.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_0_1.jpg\" alt=\"\"> <\/p><p>Let's fold the paper once.  This is done with the help of the complex number<\/p><pre>  w = (1+i)\/2<\/pre><p>In polar form, $w$ is $e^{i \\pi\/4}\/\\sqrt{2}$.  So complex multiplication by $w$ rotates by $45^\\circ$ and scales by $1\/\\sqrt{2}$.<\/p><p>In MATLAB, <tt>w'<\/tt> is the complex conjugate of <tt>w<\/tt>. This is used in the \"fold\" operation for any vector <tt>z<\/tt>.<\/p><pre>  zleft = w*z\r\n  zright = 1 - w'*fliplr(z)\r\n  z = [zleft zright]<\/pre><p>Folding turns <tt>[0 1]<\/tt> into<\/p><pre>  [0 w w 1]<\/pre><p>When we plot any vector, we break it in half, then plot the left half in black and the right half in blue.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_1_1.jpg\" alt=\"\"> <\/p><p>The black line has been rotated $45^\\circ$ to the left and a blue line, rotated $45^\\circ$ to the right, appended.<\/p><p>Fold it again.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_2_1.jpg\" alt=\"\"> <\/p><p>The black line becomes a black right angle and the blue line becomes a blue \"left angle\".<\/p><p>Two more folds produce a degree four Dragon Curve.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_4_1.jpg\" alt=\"\"> <\/p><p>A total of eight folds gives degree eight.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_8_1.jpg\" alt=\"\"> <\/p><p>And after a total of eighteen folds, we have our dragon.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_18_1.jpg\" alt=\"\"> <\/p><p>We could keep on folding, but we now have $2^{18}$ short line segments and have reached the limits of screen resolution.  More folds do not change any more pixels.<\/p><h4>Rotations<a name=\"8525bb96-7ceb-4a47-969d-643ac71a4b37\"><\/a><\/h4><p>Let's do a different kind of rotation.  Rotate the entire dragon by $90^\\circ$, superimpose it on the original, and plot the four halves with four colors.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_18_2.jpg\" alt=\"\"> <\/p><p>Do it twice more.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_18_4.jpg\" alt=\"\"> <\/p><h4>Translates<a name=\"af82d7d1-33c6-4d38-8166-6704715e0796\"><\/a><\/h4><p>We could now do translations in all four compass directions and superimpose all the dragons, but I won't show that. It turns out that as both the degrees and the translates go to infinity, the curves, which are intricately intertwined, never intersect, and completely cover and tile the complex plane.<\/p><h4>Pendant<a name=\"23825097-195c-4ad1-b0db-ca1eef257b07\"><\/a><\/h4><p>I found this at an on-line shopping center named Etsy, in the \"Fractal and Geeky Jewelry\" section.  It's from an outfit named DragonNerd in Winnipeg.  Count the number of bends to determine the degree.<\/p><p>The last time I blogged about jewelry was in my piece about <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2016\/09\/05\/the-pentium-papers-my-first-matlab-central-contribution\/\">the Pentium Affair<\/a>.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_pendant.jpg\" alt=\"\"> <\/p><p>Image credit: <a href=\"http:\/\/www.etsy.com\/shop\/DragonNerd\">http:\/\/www.etsy.com\/shop\/DragonNerd<\/a><\/p><h4>Dragon<a name=\"3f81a11a-b41e-498b-a4d5-4839ff1a511b\"><\/a><\/h4><p>All the figures above are from my new program, <tt>dragon<\/tt>, available from <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/66744-dragon\">MATLAB Central<\/a> and also included in <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a>.<\/p><p><tt>dragon<\/tt> provides four pushbuttons<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_buttons.jpg\" alt=\"\"> <\/p><p>These buttons<\/p><div><ul><li>Unwind the rotations<\/li><li>Reduce the degree<\/li><li>Increase the degree<\/li><li>Superimpose  rotations<\/li><\/ul><\/div><h4>Videos<a name=\"4fcafb93-cd8f-48a6-94ff-e35e9b78de50\"><\/a><\/h4><p>The Web is full of stuff about the Dragon Curve.  Just ask Google and Wikipedia.<\/p><p>I highly recommend two videos from <a href=\"https:\/\/www.youtube.com\/channel\/UCoxcjq-8xIDTYp3uz647V5A\">Numberphile<\/a>. In one, Don Knuth tells about a wrong turn he made in the Dragon Curve ceramic displayed in his home, <a href=\"https:\/\/www.youtube.com\/watch?v=v678Em6qyzk\">https:\/\/www.youtube.com\/watch?v=v678Em6qyzk<\/a>.<\/p><p>In the other, the popular British author, Rob Eastaway, describes the appearance of the Curve in Michael Crichton's <i>Jurassic Park<\/i>, <a href=\"https:\/\/www.youtube.com\/watch?v=wCyC-K_PnRY\">https:\/\/www.youtube.com\/watch?v=wCyC-K_PnRY<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_a0c077aaad3349dea071b4536fd9bcc9() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='a0c077aaad3349dea071b4536fd9bcc9 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' a0c077aaad3349dea071b4536fd9bcc9';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2018 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_a0c077aaad3349dea071b4536fd9bcc9()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2018a<br><\/p><\/div><!--\r\na0c077aaad3349dea071b4536fd9bcc9 ##### SOURCE BEGIN #####\r\n%% The Dragon Curve\r\n% Let me tell you about a beautiful, fractal curve, the Dragon Curve.\r\n% Download my new |dragon| program from the \r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/66744-dragon\r\n% File Exchange> and follow along.\r\n%\r\n% <<dragon_movie.gif>>\r\n\r\n%% Folding paper\r\n% Start with a long, narrow strip of paper, like the one in the\r\n% following photograph.  Fold it in half once, end over end.\r\n% Then fold it a second time, being careful to fold in the same\r\n% direction, right over left or left over right, as the first.\r\n% Then a third fold, and a fourth.  Unfold the strip so that all the\r\n% folds form the right angles pictured.  You will have created a \r\n% Dragon Curve of degree four.\r\n%\r\n% <<dragon_folds.jpg>>\r\n%\r\n% Image credit: http:\/\/www.cutoutfoldup.com\/216-dragon-curve.php\r\n\r\n%%\r\n% How many times do you imagine you could fold the paper before it is too \r\n% thick to fold again?  Probably five, maybe six.\r\n\r\n%% Signature\r\n% The degree one curve has one right angle; let's denote that by R.\r\n% The degree two curve has two right angles, followed by a left;\r\n% that's RRL.  The degree three signature is RRLRRLL.\r\n\r\n%%\r\n% Can you read off the signature of degree four from the photo?\r\n% Do you see the pattern?  Probably not yet.\r\n\r\n%%\r\n% The number of segments between folds doubles with each increase\r\n% in degree.   Here's code to display the signatures of degrees one\r\n% through six.   That's all I can display in one column of this blog post.\r\n%\r\n% The key operation in the code is |LR-fliplr(s)|.\r\n% That flips the string |s| end to end and replaces all the R's by L's\r\n% and the L's by R's.\r\n\r\n%%\r\n    s = 'R';\r\n    disp(s)\r\n    LR = 'L'+'R';\r\n    for n = 2:6\r\n        s = [s 'R' LR-fliplr(s)];\r\n        disp(s)\r\n    end\r\n\r\n%% Folds\r\n% The following figures are all from my new MATLAB program, |dragon|.\r\n% The computations are based on a growing and shrinking vector |z|\r\n% of points in the complex plane.  \r\n\r\n%%\r\n% Start with\r\n%\r\n%    z = [0 1]\r\n   \r\n%%\r\n% This isn't complex yet, but it soon will be.  \r\n% When we plot |z|, we get a single black line, representing an\r\n% unfolded strip of paper.\r\n%\r\n% <<dragon_0_1.jpg>>\r\n\r\n%%\r\n% Let's fold the paper once.  This is done with the help of the\r\n% complex number\r\n% \r\n%    w = (1+i)\/2\r\n\r\n%%\r\n% In polar form, $w$ is $e^{i \\pi\/4}\/\\sqrt{2}$.  So complex multiplication\r\n% by $w$ rotates by $45^\\circ$ and scales by $1\/\\sqrt{2}$.\r\n%\r\n% In MATLAB, |w'| is the complex conjugate of |w|.\r\n% This is used in the \"fold\" operation for any vector |z|.\r\n%\r\n%    zleft = w*z\r\n%    zright = 1 - w'*fliplr(z)\r\n%    z = [zleft zright]\r\n\r\n%%\r\n% Folding turns |[0 1]| into\r\n%\r\n%    [0 w w 1]\r\n\r\n%%\r\n% When we plot any vector, we break it in half, then plot the left half\r\n% in black and the right half in blue.\r\n%\r\n% <<dragon_1_1.jpg>>\r\n\r\n%%\r\n% The black line has been rotated $45^\\circ$ to the left and a blue\r\n% line, rotated $45^\\circ$ to the right, appended.\r\n\r\n%%\r\n% Fold it again.\r\n%\r\n% <<dragon_2_1.jpg>>\r\n%\r\n% The black line becomes a black right angle and the blue line becomes\r\n% a blue \"left angle\".\r\n\r\n%%\r\n% Two more folds produce a degree four Dragon Curve.\r\n%\r\n% <<dragon_4_1.jpg>>\r\n\r\n%%\r\n% A total of eight folds gives degree eight.\r\n%\r\n% <<dragon_8_1.jpg>>\r\n\r\n%%\r\n% And after a total of eighteen folds, we have our dragon.\r\n%\r\n% <<dragon_18_1.jpg>>\r\n\r\n%%\r\n% We could keep on folding, but we now have $2^{18}$ short line segments\r\n% and have reached the limits of screen resolution.  More folds do not\r\n% change any more pixels.\r\n\r\n%% Rotations\r\n% Let's do a different kind of rotation.  Rotate the entire dragon\r\n% by $90^\\circ$, superimpose it on the original, and plot the four\r\n% halves with four colors.\r\n%\r\n% <<dragon_18_2.jpg>>\r\n\r\n%%\r\n% Do it twice more.\r\n%\r\n% <<dragon_18_4.jpg>>\r\n\r\n%% Translates\r\n% We could now do translations in all four compass directions and\r\n% superimpose all the dragons, but I won't show that.\r\n% It turns out that as both the degrees and the translates\r\n% go to infinity, the curves, which are intricately intertwined,\r\n% never intersect, and completely cover and tile the complex plane.\r\n\r\n%% Pendant\r\n% I found this at an on-line shopping center named Etsy, in the \r\n% \"Fractal and Geeky Jewelry\" section.  It's from an outfit named\r\n% DragonNerd in Winnipeg.  Count the number of bends to determine \r\n% the degree.\r\n%\r\n% The last time I blogged about jewelry was in my piece about\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2016\/09\/05\/the-pentium-papers-my-first-matlab-central-contribution\/\r\n% the Pentium Affair>.\r\n%\r\n% <<dragon_pendant.jpg>>\r\n%\r\n% Image credit: http:\/\/www.etsy.com\/shop\/DragonNerd\r\n\r\n%% Dragon\r\n% All the figures above are from my new program, |dragon|, available from\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/66744-dragon\r\n% MATLAB Central> and also included in\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory>.  \r\n%\r\n% |dragon| provides four pushbuttons\r\n%\r\n% <<dragon_buttons.jpg>>\r\n%\r\n% These buttons\r\n%\r\n% * Unwind the rotations\r\n% * Reduce the degree\r\n% * Increase the degree\r\n% * Superimpose  rotations\r\n\r\n%% Videos\r\n% The Web is full of stuff about the Dragon Curve.  Just ask Google\r\n% and Wikipedia.\r\n%\r\n% I highly recommend two videos from\r\n% <https:\/\/www.youtube.com\/channel\/UCoxcjq-8xIDTYp3uz647V5A\r\n% Numberphile>. \r\n% In one, Don Knuth tells about a wrong turn he made in the Dragon Curve \r\n% ceramic displayed in his home, \r\n% <https:\/\/www.youtube.com\/watch?v=v678Em6qyzk>.\r\n%\r\n% In the other, the popular British author, Rob Eastaway, describes\r\n% the appearance of the Curve in Michael Crichton's _Jurassic Park_,\r\n% <https:\/\/www.youtube.com\/watch?v=wCyC-K_PnRY>.\r\n\r\n\r\n\r\n##### SOURCE END ##### a0c077aaad3349dea071b4536fd9bcc9\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/dragon_movie.gif\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>Let me tell you about a beautiful, fractal curve, the Dragon Curve. Download my new <tt>dragon<\/tt> program from the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/66744-dragon\">File Exchange<\/a> and follow along.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2018\/04\/06\/the-dragon-curve\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[18,5,23],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3212"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=3212"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3212\/revisions"}],"predecessor-version":[{"id":3244,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/3212\/revisions\/3244"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=3212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=3212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=3212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}