Wednesday, January 26, 2011

Implementing Dragon Curve in Mathematica

The algorithm for getting a folding paper fractal AKA Dragon Curve is straightforward. We start with a single bend, let's say C (for clockwise). After we fold the paper in the same way once again, and then unfold it back, we can see that the number of bends doubled, so that now it is C-C-A. The next step gives us CCA-C-CAA pattern, then CCACCAA-C-CCAACAA, and so on. One can derive the following algorithm:
  1. Let's say we have some pattern P (at the beginning P = {C})
  2. Let Q be a reversed and inverted P (e.g. if P = {CACC}, then Q = {AACA})
  3. Obtain new value for P by concatenation: P = PCQ
  4. Repeat until the required depth is reached
This is exactly what CalculateCurve function does:



It takes two arguments - depth (which is self-explanatory), and folding, which is a function returning the folding direction (1 or -1) on the given step / depth.

To understand the code better, let's extract f = #1~Join~{folding[#2]}~Join~Reverse[-#1]&;
Clearly f performs steps 2 and 3 of the algorithm described. Then Fold[f, {folding[0]}, Range[0, depth]] is equivalent to f[f[f[{folding[0]}, 0], 1], 2] and so on.

For the standard Dragon fractal the paper is always folded in the same direction, so that folding function is just a constant, e.g. -1. In this case a sample output of CalculateCurve with depth 2 looks like {-1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1}. Now in order to get the graphical representation of this sequence, we need to implement some kind of the simple automata.



Again, for simplicity let's define f = (a += #; {x, y} += {Sin[a angle], Cos[a angle]})&; It is easy to see that this function increments the current "direction angle" by 1 or -1, and then it appends the increment in the current direction to the {x, y} coordinates (increment angle is most often PI / 2, but other values sometimes give interesting results as well). Note that the current {x, y} value is returned as a result. Applying this function to the folding sequence (f /@ CalculateCurve[depth, folding]) yields a list of bend point coordinates. It is then interpolated with B-splines of the 2nd degree, and output as Graphics.

Together with controls for changing fractal depth and bending angle the code can be made as short as this:



and in this form it can be considered as a shorter alternative to the code from the Paperfolding Dragon Curve demo.

Some other examples of the growing Dragon Curves:



You can download complete notebook here.

Lecture 4 Post

The `Levenberg-Marquardt' minimization came up. I found a link to it for those that are interested.

We covered the various bifurcations that can happen in 1-D mappings. This is discussed in the book and notes. In addition there are 1-D maps on the circle. This is discussed later in the book, (page 218) and hopefully we will get a chance to cover it.

I discussed fixed point creation in maps of the interval. Pitchfork, inverse pitch fork and tangent bifurcations are the generic methods that fixed points appear as a function of control parameter. The period doubling transition was discovered by Cvitanovic and Feigenbaum.

Various examples of mappings were shown to see the range of behavior that can occur. This included the ``standard map'', ``maps of the torus'', "Henon map." Standard map and Henon map can be found in the textbook and particularly the standard map has been intensively studied with key advances made by Greene and Mackay. References on the torus map can be found on the net. Computer code is linked
on the home page.

Tuesday, January 25, 2011

Dragon curve and its relatives

Take a strip of paper; fold it; do it again and again. Sometimes up ("u") and sometimes
down "d". Label the sequence of folds "ududud" for instance. Unravel the paper.
It will have in this case 2^6 folds. Make each fold 90 degrees and plot the results.



Blog for TIF 155 / FIM 770 Dynamical systems

I am going to test to see if a blog might be a good thing for the course