Dragon curve

From Rosetta Code
Revision as of 17:53, 18 November 2008 by Rdm (talk | contribs) (minor wording clarification on J entry)
This page uses content from Wikipedia. The original article was at Drachenkurve. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)
Task
Dragon curve
You are encouraged to solve this task according to the task description, using any language you may know.

Create a dragon curve fractal.

BASIC

Works with: FreeBASIC
Works with: QuickBasic version 4.5

<qbasic> DIM SHARED angle AS Double

SUB turn (degrees AS Double) 

   angle = angle + degrees*3.14159265/180

END SUB

SUB forward (length AS Double) 

   LINE - STEP (cos(angle)*length, sin(angle)*length), 7

END SUB

SUB dragon (length AS Double, split AS Integer, d AS Double) 

   IF split=0 THEN
       forward length
   ELSE

turn d*45 dragon length/1.4142136, split-1, 1 turn -d*90 dragon length/1.4142136, split-1, -1 turn d*45 

   END IF

END SUB

' Main program

SCREEN 12 angle = 0 PSET (150,180), 0 dragon 400, 12, 1 SLEEP </qbasic>

Common Lisp

Library: CLIM

This implementation uses nested transformations rather than turtle motions. with-scaling, etc. establish transformations for the drawing which occurs within them.

The recursive dragon-part function draws a curve connecting (0,0) to (1,0); if depth is 0 then the curve is a straight line. bend-direction is either 1 or -1 to specify whether the deviation from a straight line should be to the right or left. 

(defpackage #:dragon
  (:use #:clim-lisp #:clim)
  (:export #:dragon #:dragon-part))
(in-package #:dragon)

(defun dragon-part (depth bend-direction)
  (if (zerop depth)
      (draw-line* *standard-output* 0 0 1 0)
      (with-scaling (t (/ (sqrt 2)))
        (with-rotation (t (* pi -1/4 bend-direction))
          (dragon-part (1- depth) 1)
          (with-translation (t 1 0)
            (with-rotation (t (* pi 1/2 bend-direction))
              (dragon-part (1- depth) -1)))))))

(defun dragon (&optional (depth 7) (size 100))
  (with-room-for-graphics ()
    (with-scaling (t size)
      (dragon-part depth 1))))

D

A text version of Dragon curve.
The Dragon curve drawn using an L-system.

  • variables : X Y F
  • constants : + −
  • start  : FX
  • rules  : (X → X+YF+),(Y → -FX-Y)
  • angle  : 90°
<d>

module txdraco ; // text dragon curve import std.stdio ;

const int[][] dirs = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]] ; const char[] trace = r"-\|/-\|/" ;

struct Board { 

 char[][] b = 0 ; // set at least 1x1 board
 int shiftx = 0 ;
 int shifty = 0 ;
 const char spc = ' ' ;  
 void clear() {  shiftx = shifty = 0 ; b = 0 ; } 
 void check(int x, int y) {
   while( y + shifty < 0) {
     char[] newr = new char[b[0].length] ; 
     newr[] = spc ;
     b = newr ~ b ;
     shifty++ ;
   }
   while( y + shifty >= b.length) {
     char[] newr = new char[b[0].length] ;     
     newr[] = spc ;
     b ~= newr ;     
   }
   while( x + shiftx < 0) {
     foreach(inout c ; b) 
       c = [spc] ~ c ;
     shiftx++ ;
   }
   while ( x + shiftx >= b[0].length ) 
     foreach(inout c ; b) 
       c ~= [spc] ;
 } 
 char opIndexAssign(char value, int x, int y) {
   check(x,y) ;
   b[y + shifty][x + shiftx] = value ;
   return value ;
 } 
 string toString() {
   string s ;
   foreach(c ; b)
     s ~= std.format.format("%s\n",  c) ;
   return s ;
 }

} struct TState { 

 int x = 0, y = 0, heading = 0;

} struct Turtle { 

 TState t ;
 void reset() { t.x = t.y = t.heading = 0 ; } 
 void turn(int dir) { t.heading = (t.heading + 8 + dir) % 8 ; }
 void forward(inout Board b) {
   with(t) {
     x += dirs[heading][0] ;
     y += dirs[heading][1] ;
     b[x,y] = trace[heading] ;
     x += dirs[heading][0] ;
     y += dirs[heading][1] ;
     b[x,y] = b.spc ;
   }
 }

} void dragonX(int n, inout Turtle t, inout Board b) { 

 if(n >= 0) {  // X -> X+YF+
   dragonX(n - 1, t, b) ;
   t.turn(2) ;
   dragonY(n - 1, t, b) ;
   t.forward(b) ;
   t.turn(2) ;
 }

} void dragonY(int n, inout Turtle t, inout Board b) { 

 if(n >= 0) {  // Y -> -FX-Y
   t.turn(-2) ;
   t.forward(b) ;
   dragonX(n - 1, t, b) ;
   t.turn(-2) ;
   dragonY(n - 1, t, b) ;
 }

} void main() { 

 Turtle t ;
 Board b ;
                      // initiator : FX
 t.forward(b) ;       // <- F
 dragonX(8, t, b) ;   // <- X 
 writefln(b) ;

}</d>

J

require 'plot'
start=: 0 0, 1 0,: 1 1
step=: ],{: +"1 (2 2$0 _1 1 0) +/ .*~ |.@}: -"1 {:
plot<"1|:step^:12 start

In english: Start with an L shaped geometry. For each step of iteration, retrace that geometry backwards, but oriented 90 degrees about its original end point. To show the curve you need to pick some arbitrary number of iterations.

Any L-shaped set of points is suitable for start. (For example, -start+123 works just fine though of course the orientation and coordinates will be different.)

For a more colorful display, with a different color for the geometry introduced at each iteration, replace that last line with: 

([:pd[:<"1|:)every'reset';|.'show';step&.>^:(i.16)<start


to dcr :step :length
  make "step :step - 1
  make "length :length / 1.41421
  if :step > 0 [rt 45 dcr :step :length lt 90 dcl :step :length rt 45]
  if :step = 0 [rt 45 fd :length lt 90 fd :length rt 45]
end

to dcl :step :length
  make "step :step - 1
  make "length :length / 1.41421
  if :step > 0 [lt 45 dcr :step :length rt 90 dcl :step :length lt 45]
  if :step = 0 [lt 45 fd :length rt 90 fd :length lt 45]
end

The program can be started using dcr 4 300 or dcl 4 300.

Or removing duplication: 

to dc :step :length :dir
  if :step = 0 [fd :length stop]
  rt :dir
  dc :step-1 :length/1.41421  45
  lt :dir lt :dir
  dc :step-1 :length/1.41421 -45
  rt :dir
end
to dragon :step :length
  dc :step :length 45
end

An alternative approach by using sentence-like grammar using four productions o->on, n->wn, w->ws, s->os. O, S, N and W mean cardinal points. 

to O :step :length
  if :step=1 [Rt 90 fd :length Lt 90] [O (:step - 1) (:length / 1.41421) N (:step - 1) (:length / 1.41421)]
end

to N :step :length
  if :step=1 [fd :length] [W (:step - 1) (:length / 1.41421) N (:step - 1) (:length / 1.41421)]
end

to W :step :length
  if :step=1 [Lt 90 fd :length Rt 90] [W (:step - 1) (:length / 1.41421) S (:step - 1) (:length / 1.41421)]
end 

to S :step :length
  if :step=1 [Rt 180 fd :length Lt 180] [O (:step - 1) (:length / 1.41421) S (:step - 1) (:length / 1.41421)]
end

Pascal

using Compas (Pascal with Logo-expansion):

<pascal> 

procedure dcr(step,dir:integer;length:real);
 begin;
  step:=step -1;
  length:= length/sqrt(2);
  if dir > 0 then
   begin
     if step > 0 then
     begin
       turnright(45);
       dcr(step,1,length);
       turnleft(90);
       dcr(step,0,length);
       turnright(45);
     end
     else
     begin
       turnright(45);
       forward(length);
       turnleft(90);
       forward(length);
       turnright(45);
     end;
   end
  else
   begin
     if step > 0 then
     begin
       turnleft(45);
       dcr(step,1,length);
       turnright(90);
       dcr(step,0,length);
       turnleft(45);
     end
     else
     begin
       turnleft(45);
       forward(length);
       turnright(90);
       forward(length);
       turnleft(45);
     end;
   end;
end;

</pascal> main program:

<pascal> 

begin
 init;
 penup;
 back(100);
 pendown;
 dcr(step,direction,length);
 close;
end.

</pascal>

Python

Translation of: Logo
Library: turtle

<python> from turtle import *

def dragon(step, length): 

   dcr(step, length)

def dcr(step, length): 

   step -= 1
   length /= 1.41421
   if step > 0:
       right(45)
       dcr(step, length)
       left(90)
       dcl(step, length)
       right(45)
   else:
       right(45)
       forward(length)
       left(90)
       forward(length)
       right(45)

def dcl(step, length): 

   step -= 1
   length /= 1.41421

   if step > 0:
       left(45)
       dcr(step, length)
       right(90)
       dcl(step, length)
       left(45)
   else:
       left(45)
       forward(length)
       right(90)
       forward(length)
       left(45)

</python>

This is an idiomatic python version: <python> from turtle import *

def dragon(step, length, zig=right, zag=left): 

   if step <= 0:
       forward(length)
       return

   step -= 1
   length /= 1.41421

   zig(45)
   dragon(step, length, right, left)
   zag(90)
   dragon(step, length, left, right)
   zig(45)

</python>

RapidQ

Translation of: BASIC

This implementation displays the Dragon Curve fractal in a GUI window. 

DIM angle AS Double
DIM x  AS Double, y AS Double
DECLARE SUB PaintCanvas

CREATE form AS QForm
    Width  = 800
    Height = 600
    CREATE canvas AS QCanvas
        Height = form.ClientHeight
        Width  = form.ClientWidth
        OnPaint = PaintCanvas
    END CREATE
END CREATE

SUB turn (degrees AS Double)
    angle = angle + degrees*3.14159265/180
END SUB
 
SUB forward (length AS Double)
    x2 = x + cos(angle)*length
    y2 = y + sin(angle)*length
    canvas.Line(x, y, x2, y2, &Haaffff)
    x = x2: y = y2
END SUB

SUB dragon (length AS Double, split AS Integer, d AS Double)
    IF split=0 THEN
        forward length
    ELSE
        turn d*45
        dragon length/1.4142136, split-1, 1
        turn -d*90
        dragon length/1.4142136, split-1, -1
        turn d*45
    END IF
END SUB

SUB PaintCanvas
    canvas.FillRect(0, 0, canvas.Width, canvas.Height, &H102800)
    x = 220: y = 220: angle = 0
    dragon 384, 12, 1
END SUB

form.ShowModal
Retrieved from "https://rosettacode.org/wiki/Dragon_curve?oldid=65462"