Dragon Curve

If you have a design you're proud of, share the cfdg file here. It's also a good place to ask for feedback and collaborate.

Moderators: MtnViewJohn, chris, mtnviewmark

Post Reply
andrewborrell
Posts: 8
Joined: Wed Apr 04, 2007 1:50 pm

Dragon Curve

Post by andrewborrell »

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

User avatar
Nom
Posts: 30
Joined: Tue Jan 30, 2007 6:45 am

Post by Nom »

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 :]

shevegen
Posts: 57
Joined: Wed Jul 06, 2005 5:38 am

Post by shevegen »

This recursiveness looks difficult

Pure Pandemonium
Posts: 2
Joined: Tue May 15, 2007 5:05 pm

Post by Pure Pandemonium »

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 }
}

andrewborrell
Posts: 8
Joined: Wed Apr 04, 2007 1:50 pm

Post by andrewborrell »

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.

Post Reply