Context Free Forums and Gallery

Posted: **Wed Apr 04, 2007 2:02 pm**

Has anyone managed to draw a dragon curve?

http://en.wikipedia.org/wiki/Dragon_curve

Specifically the Heighway dragon. I dont believe its possible. Thinking about the folding paper way of constructing it seems like it should be possible because one should be able to do something like:

rule paper{
paper {y 1 r 90 s 0.5}
paper {s 0.5}
line {}
}

But the problem is that the orientation of one of the children depends on what happens to the first one (i.e how many folds it and its own children has).

Posted: **Sat Apr 07, 2007 2:47 am**

There is a simple one line non-recursive method of implementing the above k mod 4 method of finding the turn direction in code. Treating turn n as a binary number, calculate the following boolean value:

bool turn = (((n & -n) << 1) & n) != 0;

* "n & -n" leaves you with only one bit as a '1', the rightmost '1' in the binary expansion of n;
* "<< 1" shifts the that bit one bit to the left;
* "& n" leaves you with either that single bit (if k mod 4 =1) or a zero (if k mod 4 =3).
* so "bool turn = (((n & -n) << 1) & n) != 0" is TRUE if the nth turn is R; and is FALSE if the nth turn is L.

I think you'd have to do it by hand in CF, if using the method in the wikipedia article. Not very rewarding :]

Posted: **Tue Apr 10, 2007 11:57 am**

This recursiveness looks difficult

Posted: **Wed May 16, 2007 5:55 am**

I managed to make one (see here

)

Though I cheated and used triangles. (Based on info gotten here)

I don't think it is possible otherwise, context free.

There's a much shorter version than the one in the gallery, though it leaves some ugly lines.

Code: Select all

include i_polygons.cfdg

startshape Dragon

rule Dragon {
LinedTriangle { }
Dragon { x 0.5 r 45 s .707 }
Dragon { y -0.5 r 135 s .707 }
}

rule LinedTriangle{
polygonRightTriangle { }
polygonRightTriangle { x -0.01 y 0.01 s 0.9 b 1 }
}

Posted: **Tue Aug 28, 2007 1:48 pm**

Hey nice work! I'm impressed, I thought it might be impossible. The challenge now is for someone to come up with a proof that shows that any recursion that can be expressed by:

Code: Select all

foo ()
{
  draw_something();
  transform_cursor1();   //some operation affecting scale position, skew etc..
  foo ();
  transform_cursor2();
  foo ();
  transform_cursor3();  //in these definitions cursor transforms are maintained on subroutine return
}

Can also be written in form

Code: Select all

bar ()
{
  push_cursor_state () //store cursor scale position etc
  draw_something();
  transform_cursor4 ();   //some operation affecting scale position, skew etc..
  bar ();
  transform_cursor5();
  bar ();
  pop_cursor_state () //no keeping cursor state across returns in this version
}

As is necessary to be drawn in cfdg. The definition of the dragon curve I was using, (the line segment or paper folding definition) is in the first form, whereas the triangle definition is in the second form.

Context Free Forums and Gallery

Dragon Curve

Dragon Curve