Dragon curve
You are encouraged to solve this task according to the task description, using any language you may know.
Create and display a dragon curve fractal. (You may either display the curve directly or write it to an image file.)
ALGOL 68
<lang algol68>REAL sqrt 2 = sqrt(2), degrees = pi/180, width = 800-15, height = 600-15;
PROC raise exception = ([]STRING args)VOID: (
putf(stand error, ($gx$, args, $l$)); stop
);
STRUCT (REAL x, y, heading, BOOL pen down) turtle;
PROC turtle init = VOID: (
draw erase (window); turtle := (0.5, 0.5, 0, TRUE); draw move (window, x OF turtle, y OF turtle); draw colour name(window, "white")
);
PROC turtle left = (REAL left turn)VOID:
heading OF turtle +:= left turn;
PROC turtle right = (REAL right turn)VOID:
heading OF turtle -:= right turn;
PROC turtle forward = (REAL distance)VOID:(
x OF turtle +:= distance * cos(heading OF turtle) / width * height; y OF turtle +:= distance * sin(heading OF turtle); IF pen down OF turtle THEN draw line ELSE draw move FI (window, x OF turtle, y OF turtle)
);
STRUCT ( INT count, depth, current shade, upb lines, upb colours ) morph;
PROC morph init = (INT depth)VOID: (
count OF morph := 0; depth OF morph := depth; current shade OF morph := -1; upb lines OF morph := 2**depth; upb colours OF morph := 16
);
PROC morph colour = VOID: (
INT colour sectors = 3; # RGB #
INT candidate shade = ENTIER ( count OF morph / upb lines OF morph * upb colours OF morph );
IF candidate shade /= current shade OF morph THEN
current shade OF morph := candidate shade;
REAL colour sector = colour sectors * candidate shade / upb colours OF morph - 0.5;
REAL shade = colour sector - ENTIER colour sector;
CASE ENTIER colour sector + 1 # of 3 # IN
draw colour (window, 1 - shade, shade, 0),
draw colour (window, 0, 1 - shade, shade)
OUT
draw colour (window, shade, 0, 1 - shade)
ESAC
FI;
count OF morph +:= 1
);
PROC dragon init = VOID: (
pen down OF turtle := FALSE; turtle forward(23/64); turtle right(90*degrees); turtle forward (1/8); turtle right(90*degrees); pen down OF turtle := TRUE
);
PROC dragon = (REAL in step, in length, PROC(REAL)VOID zig, zag)VOID: (
IF in step <= 0 THEN morph colour; turtle forward(in length) ELSE REAL step = in step - 1; REAL length = in length / sqrt 2;
zig(45*degrees); dragon(step, length, turtle right, turtle left); zag(90*degrees); dragon(step, length, turtle left, turtle right); zig(45*degrees) FI
);
PROC window init = VOID: (
STRING aspect; FILE f; associate(f, aspect); putf(f, ($g(-4)"x"g(-3)$, width, height));
IF NOT draw device (window, "X", aspect)THEN
raise exception("cannot initialise X draw device") FI;
IF open (window, "Dragon Curve", stand draw channel) /= 0 THEN
raise exception("cannot open Dragon Curve window") FI
);
FILE window; window init;
INT cycle length = 18; FOR snap shot TO cycle length DO INT depth := (snap shot - 2) MOD cycle length; turtle init; dragon init; morph init(depth);
- move to initial turtle location #
dragon(depth, 7/8, turtle right, turtle left);
draw show (window);
VOID(system("sleep 1"))
OD;
close (window)</lang> Output:
 |
Note: each Dragon curve is composed of many smaller dragon curves (shown in a different colour).
AutoHotkey
BASIC
<lang 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</lang>
BBC BASIC
<lang bbcbasic> MODE 8
MOVE 800,400
GCOL 11
PROCdragon(512, 12, 1)
END
DEF PROCdragon(size, split%, d)
PRIVATE angle
IF split% = 0 THEN
DRAW BY -COS(angle)*size, SIN(angle)*size
ELSE
angle += d*PI/4
PROCdragon(size/SQR(2), split%-1, 1)
angle -= d*PI/2
PROCdragon(size/SQR(2), split%-1, -1)
angle += d*PI/4
ENDIF
ENDPROC</lang>
C
See: Dragon curve/C
Also
C code that writes PNM of dragon curve. run as a.out [depth] > dragon.pnm. Sample image was with depth 9 (512 pixel length).
<lang C>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <math.h>
/* x, y: coordinates of current point; dx, dy: direction of movement.
* Think turtle graphics. They are divided by scale, so as to keep * very small coords/increments without losing precission. clen is * the path length travelled, which should equal to scale at the end * of the curve. */
long long x, y, dx, dy, scale, clen; typedef struct { double r, g, b; } rgb; rgb ** pix;
/* for every depth increase, rotate 45 degrees and scale up by sqrt(2)
* Note how coords can still be represented by integers. */
void sc_up() { long long tmp = dx - dy; dy = dx + dy; dx = tmp; scale *= 2; x *= 2; y *= 2; }
/* Hue changes from 0 to 360 degrees over entire length of path; Value
* oscillates along the path to give some contrast between segments * close to each other spatially. RGB derived from HSV gets *added* * to each pixel reached; they'll be dealt with later. */
void h_rgb(long long x, long long y) { rgb *p = &pix[y][x];
- define SAT 1
double h = 6.0 * clen / scale; double VAL = 1 - (cos(3.141592653579 * 64 * clen / scale) - 1) / 4; double c = SAT * VAL; double X = c * (1 - fabs(fmod(h, 2) - 1));
switch((int)h) { case 0: p->r += c; p->g += X; return; case 1: p->r += X; p->g += c; return; case 2: p->g += c; p->b += X; return; case 3: p->g += X; p->b += c; return; case 4: p->r += X; p->b += c; return; default: p->r += c; p->b += X; } }
/* string rewriting. No need to keep the string itself, just execute
* its instruction recursively. */
void iter_string(char * str, int d) { long tmp;
- define LEFT tmp = -dy; dy = dx; dx = tmp
- define RIGHT tmp = dy; dy = -dx; dx = tmp
while (*str != '\0') { switch(*(str++)) { case 'X': if (d) iter_string("X+YF+", d - 1); continue; case 'Y': if (d) iter_string("-FX-Y", d - 1); continue; case '+': RIGHT; continue; case '-': LEFT; continue; case 'F':
/* draw: increment path length; add color; move. Here
* is why the code does not allow user to choose arbitrary
* image size: if it's not a power of two, aliasing will
* occur and grid-like bright or dark lines will result
* when normalized later. It can be gotten rid of, but that
* involves computing multiplicative order and would be a huge
* bore.
*/
clen ++; h_rgb(x/scale, y/scale); x += dx; y += dy; continue; } } }
void dragon(long leng, int depth) { long i, d = leng / 3 + 1; long h = leng + 3, w = leng + d * 3 / 2 + 2;
/* allocate pixel buffer */ rgb *buf = malloc(sizeof(rgb) * w * h); pix = malloc(sizeof(rgb *) * h); for (i = 0; i < h; i++) pix[i] = buf + w * i; memset(buf, 0, sizeof(rgb) * w * h);
/* init coords; scale up to desired; exec string */
x = y = d; dx = leng; dy = 0; scale = 1; clen = 0; for (i = 0; i < depth; i++) sc_up(); iter_string("FX", depth);
/* write color PNM file */ unsigned char *fpix = malloc(w * h * 3); double maxv = 0, *dbuf = (double*)buf;
/* find highest value among pixels; normalize image according
* to it. Highest value would be at points most travelled, so
* this ends up giving curve edge a nice fade -- it's more apparaent
* if we increase iteration depth by one or two.
*/
for (i = 3 * w * h - 1; i >= 0; i--) if (dbuf[i] > maxv) maxv = dbuf[i]; for (i = 3 * h * w - 1; i >= 0; i--) fpix[i] = 255 * dbuf[i] / maxv;
printf("P6\n%ld %ld\n255\n", w, h); fflush(stdout); /* printf and fwrite may treat buffer differently */ fwrite(fpix, h * w * 3, 1, stdout); }
int main(int c, char ** v) { int size, depth;
depth = (c > 1) ? atoi(v[1]) : 10; size = 1 << depth;
fprintf(stderr, "size: %d depth: %d\n", size, depth); dragon(size, depth * 2);
return 0; }</lang>
Common Lisp
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. <lang lisp>(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))))</lang>
D
Text mode
A textual 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°
<lang d>import std.stdio, std.string, std.conv, std.algorithm;
struct Board {
enum char spc = ' '; char[][] b = ' '; // set at least 1x1 board int shiftx, shifty;
void clear() pure nothrow {
shiftx = shifty = 0;
b = '\0';
}
void check(in int x, in int y) pure nothrow {
while (y + shifty < 0) {
auto newr = new char[b[0].length];
newr[] = spc;
b = newr ~ b;
shifty++;
}
while (y + shifty >= b.length) {
auto newr = new char[b[0].length];
newr[] = spc;
b ~= newr;
}
while (x + shiftx < 0) {
foreach(ref c; b)
c = [spc] ~ c;
shiftx++;
}
while (x + shiftx >= b[0].length)
foreach(ref c; b)
c ~= [spc];
}
char opIndexAssign(in char value, in int x, in int y)
pure nothrow {
check(x, y);
b[y + shifty][x + shiftx] = value;
return value;
}
string toString() const /*pure nothrow*/ {
return join(map!text(b), "\n");
}
}
struct Turtle {
static struct TState {
int[2] xy;
int heading;
}
enum int[2][] dirs = [[1,0],[1,1],[0,1],[-1,1],
[-1,0],[-1,-1],[0,-1],[1,-1]];
enum string trace = r"-\|/-\|/";
TState t;
void reset() pure nothrow {
t = typeof(t).init;
}
void turn(in int dir) pure nothrow {
t.heading = (t.heading + 8 + dir) % 8;
}
void forward(ref Board b) pure /*nothrow*/ {
with (t) {
xy[] += dirs[heading][];
b[xy[0], xy[1]] = trace[heading];
xy[] += dirs[heading][];
b[xy[0], xy[1]] = b.spc;
}
}
}
void dragonX(in int n, ref Turtle t, ref Board b) pure /*nothrow*/ {
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(in int n, ref Turtle t, ref Board b) pure /*nothrow*/ {
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;
// Seed : FX
t.forward(b); // <- F
dragonX(7, t, b); // <- X
writeln(b);
}</lang>
- Output:
- - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - - - - - -
| | | | | | | | | | | | | | | |
- - - - - - - - - - - - - -
| | | | | | | | | | | |
- - - - - - - - - - - -
| | | | | | | | | | | |
- - - - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - -
| | | |
- - - -
| | | |
- -
With QD
See: Dragon curve/D/QD
With DFL
See: Dragon curve/D/DFL
F#
Using
for visualization:
<lang fsharp>open System.Windows open System.Windows.Media
let m = Matrix(0.0, 0.5, -0.5, 0.0, 0.0, 0.0)
let step segs =
seq { for a: Point, b: Point in segs do
let x = a + 0.5 * (b - a) + (b - a) * m
yield! [a, x; b, x] }
let rec nest n f x =
if n=0 then x else nest (n-1) f (f x)
[<System.STAThread>] do
let path = Shapes.Path(Stroke=Brushes.Black, StrokeThickness=0.001)
path.Data <-
PathGeometry
[ for a, b in nest 13 step (seq [Point(0.0, 0.0), Point(1.0, 0.0)]) ->
PathFigure(a, [(LineSegment(b, true) :> PathSegment)], false) ]
(Application()).Run(Window(Content=Controls.Viewbox(Child=path))) |> ignore</lang>
Forth
<lang forth>include turtle.fs
2 value dragon-step
- dragon ( depth dir -- )
over 0= if dragon-step fd 2drop exit then dup rt over 1- 45 recurse dup 2* lt over 1- -45 recurse rt drop ;
home clear 10 45 dragon</lang>
Forth
Basically the same code as the BigForth version.
<lang forth>include lib/graphics.4th include lib/gturtle.4th
2 constant dragon-step
- dragon ( depth dir -- )
over 0= if dragon-step forward 2drop exit then dup right over 1- 45 recurse dup 2* left over 1- -45 recurse right drop ;
150 pic_width ! 210 pic_height ! color_image
clear-screen 50 95 turtle! xpendown 13 45 dragon s" 4tHdragon.ppm" save_image</lang>
Go
Version using standard image libriary is an adaptation of the version below using the Bitmap task. The only major change is that line drawing code was needed. See comments in code. <lang go>package main
import (
"fmt" "image" "image/color" "image/draw" "image/png" "math" "os"
)
// separation of the the two endpoints // make this a power of 2 for prettiest output const sep = 512 // depth of recursion. adjust as desired for different visual effects. const depth = 14
var s = math.Sqrt2 / 2 var sin = []float64{0, s, 1, s, 0, -s, -1, -s} var cos = []float64{1, s, 0, -s, -1, -s, 0, s} var p = color.NRGBA{64, 192, 96, 255} var b *image.NRGBA
func main() {
width := sep * 11 / 6
height := sep * 4 / 3
bounds := image.Rect(0, 0, width, height)
b = image.NewNRGBA(bounds)
draw.Draw(b, bounds, image.NewUniform(color.White), image.ZP, draw.Src)
dragon(14, 0, 1, sep, sep/2, sep*5/6)
f, err := os.Create("dragon.png")
if err != nil {
fmt.Println(err)
return
}
if err = png.Encode(f, b); err != nil {
fmt.Println(err)
}
if err = f.Close(); err != nil {
fmt.Println(err)
}
}
func dragon(n, a, t int, d, x, y float64) {
if n <= 1 {
// Go packages used here do not have line drawing functions
// so we implement a very simple line drawing algorithm here.
// We take advantage of knowledge that we are always drawing
// 45 degree diagonal lines.
x1 := int(x + .5)
y1 := int(y + .5)
x2 := int(x + d*cos[a] + .5)
y2 := int(y + d*sin[a] + .5)
xInc := 1
if x1 > x2 {
xInc = -1
}
yInc := 1
if y1 > y2 {
yInc = -1
}
for x, y := x1, y1; ; x, y = x+xInc, y+yInc {
b.Set(x, y, p)
if x == x2 {
break
}
}
return
}
d *= s
a1 := (a - t) & 7
a2 := (a + t) & 7
dragon(n-1, a1, 1, d, x, y)
dragon(n-1, a2, -1, d, x+d*cos[a1], y+d*sin[a1])
}</lang> Original version written to Bitmap task: <lang go>package main
// Files required to build supporting package raster are found in: // * Bitmap // * Write a PPM file
import (
"math" "raster"
)
// separation of the the two endpoints // make this a power of 2 for prettiest output const sep = 512 // depth of recursion. adjust as desired for different visual effects. const depth = 14
var s = math.Sqrt2 / 2 var sin = []float64{0, s, 1, s, 0, -s, -1, -s} var cos = []float64{1, s, 0, -s, -1, -s, 0, s} var p = raster.Pixel{64, 192, 96} var b *raster.Bitmap
func main() {
width := sep * 11 / 6
height := sep * 4 / 3
b = raster.NewBitmap(width, height)
b.Fill(raster.Pixel{255, 255, 255})
dragon(14, 0, 1, sep, sep/2, sep*5/6)
b.WritePpmFile("dragon.ppm")
}
func dragon(n, a, t int, d, x, y float64) {
if n <= 1 {
b.Line(int(x+.5), int(y+.5), int(x+d*cos[a]+.5), int(y+d*sin[a]+.5), p)
return
}
d *= s
a1 := (a - t) & 7
a2 := (a + t) & 7
dragon(n-1, a1, 1, d, x, y)
dragon(n-1, a2, -1, d, x+d*cos[a1], y+d*sin[a1])
}</lang>
Haskell
<lang haskell>import Data.List import Graphics.Gnuplot.Simple
-- diamonds -- pl = [[0,1],[1,0]]
pl = [[0,0],[0,1]] r_90 = [[0,1],[-1,0]]
ip :: [Int] -> [Int] -> Int ip xs = sum . zipWith (*) xs matmul xss yss = map (\xs -> map (ip xs ). transpose $ yss) xss
vmoot xs = (xs++).map (zipWith (+) lxs). flip matmul r_90.
map (flip (zipWith (-)) lxs) .reverse . init $ xs where lxs = last xs
dragoncurve = iterate vmoot pl</lang> For plotting I use the gnuplot interface module from hackageDB
Use:
plotPath [] . map (\[x,y] -> (x,y)) $ dragoncurve!!13
HicEst
A straightforward approach, since HicEst does not know recursion (rarely needed in daily work) <lang hicest> CHARACTER dragon
1 DLG(NameEdit=orders,DNum, Button='&OK', TItle=dragon) ! input orders WINDOW(WINdowhandle=wh, Height=1, X=1, TItle='Dragon curves up to order '//orders)
IF( LEN(dragon) < 2^orders) ALLOCATE(dragon, 2^orders)
AXIS(WINdowhandle=wh, Xaxis=2048, Yaxis=2048) ! 2048: black, linear, noGrid, noScales dragon = ' ' NorthEastSouthWest = 0 x = 0 y = 1 LINE(PenUp, Color=1, x=0, y=0, x=x, y=y) last = 1
DO order = 1, orders
changeRtoL = LEN_TRIM(dragon) + 1 + (LEN_TRIM(dragon) + 1)/2
dragon = TRIM(dragon) // 'R' // TRIM(dragon)
IF(changeRtoL > 2) dragon(changeRtoL) = 'L'
DO last = last, LEN_TRIM(dragon)
NorthEastSouthWest = MOD( NorthEastSouthWest-2*(dragon(last)=='L')+5, 4 )
x = x + (NorthEastSouthWest==1) - (NorthEastSouthWest==3)
y = y + (NorthEastSouthWest==0) - (NorthEastSouthWest==2)
LINE(Color=order, X=x, Y=y)
ENDDO
ENDDO
GOTO 1 ! this is to stimulate a discussion
END</lang>
Icon and Unicon
The following implements a Heighway Dragon using the Lindenmayer system. It's based on the linden program in the Icon Programming Library. <lang Icon>link linddraw,wopen
procedure main()
gener := 12 # generations w := h := 800 # window size rewrite := table() # L rewrite rules rewrite["X"] := "X+YF+" rewrite["Y"] := "-FX-Y" every (C := ) ++:= !!rewrite every /rewrite[c := !C] := c # map all rule characters
WOpen("size=" || w || "," || h, "dx=" || (w / 2), "dy=" || (h / 2)) | stop("*** cannot open window")
WAttrib("fg=blue")
linddraw(0, 0, "FX", rewrite, 5, 90.0, gener, 0)
# x,y, axiom, rules, length, angle, generations, delay
WriteImage("dragon-unicon" || ".gif") # save the image
WDone()
end</lang>
J
<lang j>require 'plot' start=: 0 0,: 1 0 step=: ],{: +"1 (0 _1,: 1 0) +/ .*~ |.@}: -"1 {: plot <"1 |: step^:13 start</lang> In English: Start with a line segment. 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 line segment is suitable for start. (For example, -start+123 works just fine though of course the resulting orientation and coordinates for the curve will be different from those obtained using start for the line segment.)
For a more colorful display, with a different color for the geometry introduced at each iteration, replace that last line of code with: <lang j>([:pd[:<"1|:)every'reset';|.'show';step&.>^:(i.17)<start</lang>
The curve can also be represented as a limiting set of the iterated function system
Giving the code <lang j>require 'plot' f1=.*&(-:1j1) f2=.[: -. *&(-:1j_1) plot (f1,}.@|.@f2)^:12 ]0 1</lang>
Where both functions are applied successively to starting complex values of 0 and 1.
Note the formatting of f2 as }.@|.@f2 . This allows the plotted path to go in the right order and removes redundant points, paralleling similar operations in the previous solution.
Java
<lang java>import java.awt.Color; import java.awt.Graphics; import java.util.*; import javax.swing.JFrame;
public class DragonCurve extends JFrame {
private List<Integer> turns; private double startingAngle, side;
public DragonCurve(int iter) {
super("Dragon Curve");
setBounds(100, 100, 800, 600);
setDefaultCloseOperation(EXIT_ON_CLOSE);
turns = getSequence(iter);
startingAngle = -iter * (Math.PI / 4);
side = 400 / Math.pow(2, iter / 2.);
}
public List<Integer> getSequence(int iterations) {
List<Integer> turnSequence = new ArrayList<Integer>();
for (int i = 0; i < iterations; i++) {
List<Integer> copy = new ArrayList<Integer>(turnSequence);
Collections.reverse(copy);
turnSequence.add(1);
for (Integer turn : copy) {
turnSequence.add(-turn);
}
}
return turnSequence;
}
@Override
public void paint(Graphics g) {
g.setColor(Color.BLACK);
double angle = startingAngle;
int x1 = 230, y1 = 350;
int x2 = x1 + (int) (Math.cos(angle) * side);
int y2 = y1 + (int) (Math.sin(angle) * side);
g.drawLine(x1, y1, x2, y2);
x1 = x2;
y1 = y2;
for (Integer turn : turns) {
angle += turn * (Math.PI / 2);
x2 = x1 + (int) (Math.cos(angle) * side);
y2 = y1 + (int) (Math.sin(angle) * side);
g.drawLine(x1, y1, x2, y2);
x1 = x2;
y1 = y2;
}
}
public static void main(String[] args) {
new DragonCurve(14).setVisible(true);
}
}</lang>
JavaScript
I'm sure this can be simplified further, but I have this working here!
Though there is an impressive SVG example further below, this uses JavaScript to recurse through the expansion and simply displays each line with SVG. It is invoked as a method DRAGON.fractal(...) as described.
<lang javascript>var DRAGON = (function () {
// MATRIX MATH // -----------
var matrix = {
mult: function ( m, v ) {
return [ m[0][0] * v[0] + m[0][1] * v[1],
m[1][0] * v[0] + m[1][1] * v[1] ];
},
minus: function ( a, b ) {
return [ a[0]-b[0], a[1]-b[1] ];
},
plus: function ( a, b ) {
return [ a[0]+b[0], a[1]+b[1] ];
}
};
// SVG STUFF // ---------
// Turn a pair of points into an SVG path like "M1 1L2 2".
var toSVGpath = function (a, b) { // type system fail
return "M" + a[0] + " " + a[1] + "L" + b[0] + " " + b[1];
};
// DRAGON MAKING // -------------
// Make a dragon with a better fractal algorithm
var fractalMakeDragon = function (svgid, ptA, ptC, state, lr, interval) {
// make a new <path>
var path = document.createElementNS('http://www.w3.org/2000/svg', 'path');
path.setAttribute( "class", "dragon");
path.setAttribute( "d", toSVGpath(ptA, ptC) );
// append the new path to the existing <svg>
var svg = document.getElementById(svgid); // call could be eliminated
svg.appendChild(path);
// if we have more iterations to go...
if (state > 1) {
// make a new point, either to the left or right
var growNewPoint = function (ptA, ptC, lr) {
var left = [[ 1/2,-1/2 ],
[ 1/2, 1/2 ]];
var right = [[ 1/2, 1/2 ],
[-1/2, 1/2 ]];
return matrix.plus(ptA, matrix.mult( lr ? left : right,
matrix.minus(ptC, ptA) ));
};
var ptB = growNewPoint(ptA, ptC, lr, state);
// then recurse using each new line, one left, one right
var recurse = function () {
// when recursing deeper, delete this svg path
svg.removeChild(path);
// then invoke again for new pair, decrementing the state
fractalMakeDragon(svgid, ptB, ptA, state-1, lr, interval);
fractalMakeDragon(svgid, ptB, ptC, state-1, lr, interval);
};
window.setTimeout(recurse, interval);
}
};
// Export these functions
// ----------------------
return {
fractal: fractalMakeDragon
// ARGUMENTS
// ---------
// svgid id of <svg> element
// ptA first point [x,y] (from top left)
// ptC second point [x,y]
// state number indicating how many steps to recurse
// lr true/false to make new point on left or right
// CONFIG
// ------
// CSS rules should be made for the following
// svg#fractal
// svg path.dragon
};
}());</lang>
My current demo page includes the following to invoke this: <lang html>... <script src='./dragon.js'></script> ...
<svg xmlns='http://www.w3.org/2000/svg' id='fractal'></svg>
<script>
DRAGON.fractal('fractal', [100,300], [500,300], 15, false, 700);
</script> ...</lang>
Liberty BASIC
<lang lb>nomainwin
mainwin 50 20
WindowHeight =620 WindowWidth =690
open "Graphics library" for graphics as #a
#a, "trapclose [quit]"
#a "down"
Turn$ ="R" Pace =100 s = 16
[again]
print Turn$
#a "cls ; home ; north ; down ; fill black"
for i =1 to len( Turn$)
v =255 *i /len( Turn$)
#a "color "; v; " 120 "; 255 -v
#a "go "; Pace
if mid$( Turn$, i, 1) ="R" then #a "turn 90" else #a "turn -90"
next i
#a "color 255 120 0" #a "go "; Pace #a "flush"
FlippedTurn$ =""
for i =len( Turn$) to 1 step -1
if mid$( Turn$, i, 1) ="R" then FlippedTurn$ =FlippedTurn$ +"L" else FlippedTurn$ =FlippedTurn$ +"R"
next i
Turn$ =Turn$ +"R" +FlippedTurn$
Pace =Pace /1.35
scan
timer 1000, [j] wait
[j]
timer 0
if len( Turn$) <40000 then goto [again]
wait
[quit]
close #a end</lang>
Logo
<lang logo>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</lang> The program can be started using dcr 4 300 or dcl 4 300.
Or removing duplication: <lang logo>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</lang> 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. <lang logo>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</lang>
Lua
Could be made much more compact, but this was written for speed. It has two rendering modes, one which renders the curve in text mode (default,) and one which just dumps all the coordinates for use by an external rendering application. <lang Lua>function dragon()
local l = "l"
local r = "r"
local inverse = {l = r, r = l}
local field = {r}
local num = 1
local loop_limit = 6 --increase this number to render a bigger curve
for discard=1,loop_limit do
field[num+1] = r
for i=1,num do
field[i+num+1] = inverse[field[num-i+1]]
end
num = num*2+1
end
return field
end
function render(field, w, h, l)
local x = 0
local y = 0
local points = {}
local highest_x = 0
local highest_y = 0
local lowest_x = 0
local lowest_y = 0
local l = "l"
local r = "r"
local u = "u"
local d = "d"
local heading = u
local turn = {r = {r = d, d = l, l = u, u = r}, l = {r = u, u = l, l = d, d = r}}
for k, v in ipairs(field) do
heading = turn[v][heading]
for i=1,3 do
points[#points+1] = {x, y}
if heading == l then
x = x-w
elseif heading == r then
x = x+w
elseif heading == u then
y = y-h
elseif heading == d then
y = y+h
end
if x > highest_x then
highest_x = x
elseif x < lowest_x then
lowest_x = x
end
if y > highest_y then
highest_y = y
elseif y < lowest_y then
lowest_y = y
end
end
end
points[#points+1] = {x, y}
highest_x = highest_x - lowest_x + 1
highest_y = highest_y - lowest_y + 1
for k, v in ipairs(points) do
v[1] = v[1] - lowest_x + 1
v[2] = v[2] - lowest_y + 1
end
return highest_x, highest_y, points
end
function render_text_mode()
local width, height, points = render(dragon(), 1, 1, 1)
local rows = {}
for i=1,height do
rows[i] = {}
for j=1,width do
rows[i][j] = ' '
end
end
for k, v in ipairs(points) do
rows[v[2]][v[1]] = "*"
end
for i=1,height do
print(table.concat(rows[i], ""))
end
end
function dump_points()
local width, height, points = render(dragon(), 4, 4, 1)
for k, v in ipairs(points) do
print(unpack(v))
end
end
--replace this line with dump_points() to output a list of coordinates: render_text_mode() </lang> Output:
**** ****
* * * *
* * * *
**** *******
* *
* *
**** **** ****
* * *
* * *
**********
* * *
* * *
*******
*
*
**** ****
* * *
* * *
********** ****
* * * * *
* * * * *
**** ****************
* * * * * * *
* * * * * * *
*******************
* * * * *
* * * * *
******* ******* ****
* * * *
* * * *
******* **** **** ****
* * * * * *
* * * * * *
**** ********** ****
* * * *
* * * *
********** **** *******
* * * * * * * *
* * * * * * * *
******* ********** ****
* * * *
* * * *
******* *******
* * * *
* * * *
**** ****
Mathematica
Two functions: one that makes 2 lines from 1 line. And another that applies this function to all existing lines: <lang Mathematica>FoldOutLine[{a_,b_}]:=Template:A,&[a+0.5(b-a)+{{0.,0.5},{-0.5,0.}}.(b-a)] NextStep[in_]:=Flatten[FoldOutLine/@in,1] lines={{{0.,0.},{1.,0.}}}; Graphics[Line/@Nest[NextStep,lines,11]]</lang>
Metafont
Metafont is a language to create fonts; since fonts normally are not too big, Metafont has hard encoded limits which makes it difficult to produce large images. This is one of the reasons why Metapost came into being.
The following code produces a single character font, 25 points wide and tall (0 points in depth), and store it in the position where one could expect to find the character D.
<lang metafont>mode_setup; dragoniter := 8; beginchar("D", 25pt#, 25pt#, 0pt#);
pickup pencircle scaled .5pt;
x1 = 0; x2 = w; y1 = y2 = .5h;
mstep := .5; sg := -1;
for i = 1 upto dragoniter:
for v = 1 step mstep until (2-mstep):
if unknown z[v+mstep]:
pair t; t := .7071[ z[v], z[v+2mstep] ]; z[v+mstep] = t rotatedaround(z[v], 45sg); sg := -1*sg;
fi endfor mstep := mstep/2; endfor draw for v:=1 step 2mstep until (2-2mstep): z[v] -- endfor z[2];
endchar; end</lang>
The resulting character, magnified by 2, looks like:
OCaml
Example solution, using an OCaml class and displaying the result in a Tk canvas, mostly inspired by the Tcl solution. <lang ocaml>(* This constant does not seem to be defined anywhere in the standard modules *) let pi = acos (-1.0);
(*
- CLASS dragon_curve_computer:
- ----------------------------
- Computes the coordinates for the line drawing the curve.
- - initial_x initial_y: coordinates for starting point for curve
- - total_length: total length for the curve
- - total_splits: total number of splits to perform
- )
class dragon_curve_computer initial_x initial_y total_length total_splits =
object(self)
val mutable current_x = (float_of_int initial_x) (* current x coordinate in curve *)
val mutable current_y = (float_of_int initial_y) (* current y coordinate in curve *)
val mutable current_angle = 0.0 (* current angle *)
(*
** METHOD compute_coords:
** ----------------------
** Actually computes the coordinates in the line for the curve
** - length: length for current iteration
** - nb_splits: number of splits to perform for current iteration
** - direction: direction for current line (-1.0 or 1.0)
** Returns: the list of coordinates for the line in this iteration
*)
method compute_coords length nb_splits direction =
(* If all splits have been done *)
if nb_splits = 0
then
begin
(* Draw line segment, updating current coordinates *)
current_x <- current_x +. length *. cos current_angle;
current_y <- current_y +. length *. sin current_angle;
[(int_of_float current_x, int_of_float current_y)]
end
(* If there are still splits to perform *)
else
begin
(* Compute length for next iteration *)
let sub_length = length /. sqrt 2.0 in
(* Turn 45 degrees to left or right depending on current direction and draw part
of curve in this direction *)
current_angle <- current_angle +. direction *. pi /. 4.0;
let coords1 = self#compute_coords sub_length (nb_splits - 1) 1.0 in
(* Turn 90 degrees in the other direction and draw part of curve in that direction *)
current_angle <- current_angle -. direction *. pi /. 2.0;
let coords2 = self#compute_coords sub_length (nb_splits - 1) (-1.0) in
(* Turn back 45 degrees to set head in the initial direction again *)
current_angle <- current_angle +. direction *. pi /. 4.0;
(* Concatenate both sub-curves to get the full curve for this iteration *)
coords1 @ coords2
end
(*
** METHOD get_coords:
** ------------------
** Returns the coordinates for the curve with the parameters set in the object initializer
*)
method get_coords = self#compute_coords total_length total_splits 1.0
end;;
(*
- MAIN PROGRAM:
- =============
- )
let () =
(* Curve is displayed in a Tk canvas *) let top=Tk.openTk() in let c = Canvas.create ~width:400 ~height:400 top in Tk.pack [c]; (* Create instance computing the curve coordinates *) let dcc = new dragon_curve_computer 100 200 200.0 16 in (* Create line with these coordinates in canvas *) ignore (Canvas.create_line ~xys: dcc#get_coords c); Tk.mainLoop ();
- </lang>
Here is another OCaml solution, in a functional rather than OO style: <lang OCaml>let zig (x1,y1) (x2,y2) = (x1+x2+y1-y2)/2, (x2-x1+y1+y2)/2 let zag (x1,y1) (x2,y2) = (x1+x2-y1+y2)/2, (x1-x2+y1+y2)/2
let rec dragon p1 p2 p3 n =
if n = 0 then [p1;p2] else (dragon p1 (zig p1 p2) p2 (n-1)) @ (dragon p2 (zag p2 p3) p3 (n-1))
let _ =
let top = Tk.openTk() in let c = Canvas.create ~width:430 ~height:300 top in Tk.pack [c]; let p1, p2 = (100, 100), (356,100) in let points = dragon p1 (zig p1 p2) p2 15 in ignore (Canvas.create_line ~xys: points c); Tk.mainLoop ()</lang>
producing:
Run an example with:
ocaml -I +labltk labltk.cma dragon.ml
Perl 6
Iterative algorithm. Prints in SVG format. <lang perl6>say "<?xml version='1.0' encoding='utf-8' standalone='no'?> <!DOCTYPE svg PUBLIC '-//W3C//DTD SVG 1.1//EN' 'http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd'> <svg width='100%' height='100%' version='1.1' xmlns='http://www.w3.org/2000/svg'>";
my $order = 10; # akin to number of recursion steps my $d_size = 1000; # size in pixels my $turn_angle = pi/2; # turn angle of each segment, 90 degrees for the canonical dragon
my $angle = pi - ($order * (pi/4)); # starting angle my $len = ($d_size/1.5) / sqrt(2)**$order; # size of each segment my ($x, $y) = ($d_size*5/6, $d_size*1/3); # starting point
for 0..2**$order-1 -> $i { # find which side to turn based on the iteration $angle += ((($i +& -$i) +< 1) +& $i) ?? -$turn_angle !! $turn_angle;
my ($dx, $dy) = ($x + $len * $angle.sin, $y - $len * $angle.cos); say "<line x1='$x' y1='$y' x2='$dx' y2='$dy' style='stroke:rgb(0,0,0);stroke-width:1'/>"; ($x, $y) = ($dx, $dy); }
say "</svg>";</lang>
Pascal
using Compas (Pascal with Logo-expansion): <lang 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;</lang> main program: <lang pascal>begin
init; penup; back(100); pendown; dcr(step,direction,length); close;
end.</lang>
PicoLisp
This uses the 'brez' line drawing function from Bitmap/Bresenham's line algorithm#PicoLisp. <lang PicoLisp># Need some turtle graphics (load "@lib/math.l")
(setq
*TurtleX 100 # X position *TurtleY 75 # Y position *TurtleA 0.0 ) # Angle
(de fd (Img Len) # Forward
(let (R (*/ *TurtleA pi 180.0) DX (*/ (cos R) Len 1.0) DY (*/ (sin R) Len 1.0))
(brez Img *TurtleX *TurtleY DX DY)
(inc '*TurtleX DX)
(inc '*TurtleY DY) ) )
(de rt (A) # Right turn
(inc '*TurtleA A) )
(de lt (A) # Left turn
(dec '*TurtleA A) )
- Dragon curve stuff
(de *DragonStep . 4)
(de dragon (Img Depth Dir)
(if (=0 Depth)
(fd Img *DragonStep)
(rt Dir)
(dragon Img (dec Depth) 45.0)
(lt (* 2 Dir))
(dragon Img (dec Depth) -45.0)
(rt Dir) ) )
- Run it
(let Img (make (do 200 (link (need 300 0)))) # Create image 300 x 200
(dragon Img 10 45.0) # Build dragon curve
(out "img.pbm" # Write to bitmap file
(prinl "P1")
(prinl 300 " " 200)
(mapc prinl Img) ) )</lang>
PostScript
<lang postscript>%!PS %%BoundingBox: 0 0 550 400 /ifpendown false def /rotation 0 def /srootii 2 sqrt def /turn {
rotation add /rotation exch def
} def
/forward {
dup rotation cos mul
exch rotation sin mul
ifpendown
{ rlineto }
{ rmoveto }
ifelse
} def
/penup {
/ifpendown false def
} def
/pendown {
/ifpendown true def
} def
/dragon { % [ length, split, d ]
dup
dup 1 get 0 eq
{ 0 get forward }
{ dup 2 get 45 mul turn
dup aload pop pop
1 sub exch srootii div exch
1 3 array astore dragon pop
dup 2 get 90 mul neg turn
dup aload pop pop
1 sub exch srootii div exch
-1 3 array astore dragon
dup 2 get 45 mul turn
}
ifelse
pop
} def
150 150 moveto pendown [ 300 12 1 ] dragon stroke % 0 0 moveto 550 0 rlineto 0 400 rlineto -550 0 rlineto closepath stroke showpage %%END</lang>
Or (almost) verbatim string rewrite: (this is a 20 page document, and don't try to print it, or you might have a very angry printer). <lang postscript>%!PS-Adobe-3.0 %%BoundingBox 0 0 300 300
/+ { 90 rotate } def /- {-90 rotate } def /!1 { dup 1 sub dup 0 eq not } def
/F { 180 0 rlineto } def /X { !1 { X + Y F + } if pop } def /Y { !1 { - F X - Y } if pop } def
/dragon {
gsave
70 180 moveto
dup 1 sub { 1 2 div sqrt dup scale -45 rotate } repeat
F X stroke
grestore
} def
1 1 20 { dragon showpage } for
%%EOF</lang>
- See also
Prolog
Works with SWI-Prolog which has a Graphic interface XPCE.
DCG are used to compute the list of "turns" of the Dragon Curve and the list of points.
<lang Prolog>dragonCurve(N) :-
dcg_dg(N, [left], DCL, []),
Side = 4,
Angle is -N * (pi/4),
dcg_computePath(Side, Angle, DCL, point(180,400), P, []),
new(D, window('Dragon Curve')),
send(D, size, size(800,600)),
new(Path, path(poly)),
send_list(Path, append, P),
send(D, display, Path),
send(D, open).
% compute the list of points of the Dragon Curve
dcg_computePath(Side, Angle, [left | DCT], point(X1, Y1)) -->
[point(X1, Y1)],
{ X2 is X1 + Side * cos(Angle),
Y2 is Y1 + Side * sin(Angle),
Angle1 is Angle + pi / 2
},
dcg_computePath(Side, Angle1, DCT, point(X2, Y2)).
dcg_computePath(Side, Angle, [right | DCT], point(X1, Y1)) --> [point(X1, Y1)], { X2 is X1 + Side * cos(Angle), Y2 is Y1 + Side * sin(Angle), Angle1 is Angle - pi / 2 }, dcg_computePath(Side, Angle1, DCT, point(X2, Y2)).
dcg_computePath(_Side, _Angle, [], point(X1, Y1)) -->
[ point(X1, Y1)].
% compute the list of the "turns" of the Dragon Curve
dcg_dg(1, L) --> L.
dcg_dg(N, L) --> {dcg_dg(L, L1, []), N1 is N - 1}, dcg_dg(N1, L1).
% one interation of the process dcg_dg(L) --> L, [left], inverse(L).
inverse([H | T]) --> inverse(T), inverse(H).
inverse([]) --> [].
inverse(left) --> [right].
inverse(right) --> [left].</lang> Output :
1 ?- dragonCurve(13). true
PureBasic
<lang PureBasic>#SqRt2 = 1.4142136
- SizeH = 800: #SizeV = 550
Global angle.d, px, py, imageNum
Procedure turn(degrees.d)
angle + degrees * #PI / 180
EndProcedure
Procedure forward(length.d)
Protected w = Cos(angle) * length Protected h = Sin(angle) * length LineXY(px, py, px + w, py + h, RGB(255,255,255)) px + w: py + h
EndProcedure
Procedure dragon(length.d, split, d.d)
If split = 0 forward(length) Else turn(d * 45) dragon(length / #SqRt2, split - 1, 1) turn(-d * 90) dragon(length / #SqRt2, split - 1, -1) turn(d * 45) EndIf
EndProcedure
OpenWindow(0, 0, 0, #SizeH, #SizeV, "DragonCurve", #PB_Window_SystemMenu) imageNum = CreateImage(#PB_Any, #SizeH, #SizeV, 32) ImageGadget(0, 0, 0, 0, 0, ImageID(imageNum))
angle = 0: px = 185: py = 190 If StartDrawing(ImageOutput(imageNum))
dragon(400, 15, 1) StopDrawing() SetGadgetState(0, ImageID(imageNum))
EndIf
Repeat: Until WaitWindowEvent(10) = #PB_Event_CloseWindow</lang>
Python
<lang 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)</lang>
A more pythonic version: <lang python>from turtle import right, left, forward, speed, exitonclick, hideturtle
def dragon(level=4, size=200, zig=right, zag=left):
if level <= 0:
forward(size)
return
size /= 1.41421 zig(45) dragon(level-1, size, right, left) zag(90) dragon(level-1, size, left, right) zig(45)
speed(0) hideturtle() dragon(6) exitonclick() # click to exit</lang> Other version: <lang python>from turtle import right, left, forward, speed, exitonclick, hideturtle
def dragon(level=4, size=200, direction=45):
if level:
right(direction)
dragon(level-1, size/1.41421356237, 45)
left(direction * 2)
dragon(level-1, size/1.41421356237, -45)
right(direction)
else:
forward(size)
speed(0) hideturtle() dragon(6) exitonclick() # click to exit</lang>
RapidQ
This implementation displays the Dragon Curve fractal in a GUI window. <lang rapidq>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</lang>
Ruby
<lang ruby>Point = Struct.new(:x, :y) Line = Struct.new(:start, :stop)
Shoes.app(:width => 800, :height => 600, :resizable => false) do
def split_segments(n)
dir = 1
@segments = @segments.inject([]) do |new, l|
a, b, c, d = l.start.x, l.start.y, l.stop.x, l.stop.y
mid_x = a + (c-a)/2.0 - (d-b)/2.0*dir
mid_y = b + (d-b)/2.0 + (c-a)/2.0*dir
mid_p = Point.new(mid_x, mid_y)
dir *= -1
new << Line.new(l.start, mid_p)
new << Line.new(mid_p, l.stop)
end
end
@segments = [Line.new(Point.new(200,200), Point.new(600,200))]
15.times do |n|
info "calculating frame #{n}"
split_segments(n)
end
stack do
@segments.each do |l|
line l.start.x, l.start.y, l.stop.x, l.stop.y
end
end
end</lang>
Run BASIC
<lang runbasic>graphic #g, 600,600 RL$ = "R" loc = 90 pass = 0
[loop]
- g "cls ; home ; north ; down ; fill black"
for i =1 to len(RL$)
v = 255 * i /len(RL$) #g "color "; v; " 120 "; 255 -v #g "go "; loc if mid$(RL$,i,1) ="R" then #g "turn 90" else #g "turn -90"
next i
- g "color 255 120 0"
- g "go "; loc
LR$ ="" for i =len( RL$) to 1 step -1
if mid$( RL$, i, 1) ="R" then LR$ =LR$ +"L" else LR$ =LR$ +"R"
next i
RL$ = RL$ + "R" + LR$ loc = loc / 1.35 pass = pass + 1 render #g input xxx cls
if pass < 16 then goto [loop] end</lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
include "float.s7i"; include "math.s7i"; include "draw.s7i"; include "keybd.s7i";
var float: angle is 0.0; var integer: x is 220; var integer: y is 220;
const proc: turn (in integer: degrees) is func
begin angle +:= flt(degrees) * PI / 180.0 end func;
const proc: forward (in float: length) is func
local var integer: x2 is 0; var integer: y2 is 0; begin x2 := x + trunc(cos(angle) * length); y2 := y + trunc(sin(angle) * length); lineTo(x, y, x2, y2, black); x := x2; y := y2; end func;
const proc: dragon (in float: length, in integer: split, in integer: direct) is func
begin
if split = 0 then
forward(length);
else
turn(direct * 45);
dragon(length/1.4142136, pred(split), 1);
turn(-direct * 90);
dragon(length/1.4142136, pred(split), -1);
turn(direct * 45);
end if;
end func;
const proc: main is func
begin screen(976, 654); clear(curr_win, white); KEYBOARD := GRAPH_KEYBOARD; dragon(768.0, 14, 1); ignore(getc(KEYBOARD)); end func;</lang>
Original source: [1]
SVG
SVG does not support recursion, but it does support transformations and multiple uses of the same graphic, so the fractal can be expressed linearly in the iteration count of the fractal.
This version also places circles at the endpoints of each subdivision, size varying with the scale of the fractal, so you can see the shape of each step somewhat.
Note: Some SVG implementations, particularly rsvg (as of v2.26.0), do not correctly interpret XML namespaces; in this case, replace the “l” namespace prefix with “xlink”.
<lang xml><?xml version="1.0" standalone="yes"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN"
"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:l="http://www.w3.org/1999/xlink" width="400" height="400"> <style type="text/css"><![CDATA[ line { stroke: black; stroke-width: .05; } circle { fill: black; } ]]></style>
<defs>
<g id="marks">
<circle cx="0" cy="0" r=".03"/>
<circle cx="1" cy="0" r=".03"/>
</g>
<g id="l0">
<line x1="0" y1="0" x2="1" y2="0"/>
</g>
<g id="l1"> <use l:href="#l0" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l0" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l2"> <use l:href="#l1" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l1" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l3"> <use l:href="#l2" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l2" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l4"> <use l:href="#l3" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l3" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l5"> <use l:href="#l4" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l4" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l6"> <use l:href="#l5" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l5" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l7"> <use l:href="#l6" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l6" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l8"> <use l:href="#l7" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l7" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
<g id="l9"> <use l:href="#l8" transform="matrix( .5 .5 -.5 .5 0 0)"/>
<use l:href="#l8" transform="matrix(-.5 .5 -.5 -.5 1 0)"/>
<use l:href="#marks"/></g>
</defs>
<g transform="translate(100, 200) scale(200)">
<use l:href="#marks"/> <use l:href="#l9"/>
</g>
</svg></lang>
Tcl
<lang tcl>package require Tk
set pi [expr acos(-1)] set r2 [expr sqrt(2)]
proc turn {degrees} {
global a pi
set a [expr {$a + $degrees*$pi/180}]
} proc forward {len} {
global a coords
lassign [lrange $coords end-1 end] x y
lappend coords [expr {$x + cos($a)*$len}] [expr {$y + sin($a)*$len}]
} proc dragon {len split {d 1}} {
global r2 coords
if {$split == 0} {
forward $len return
}
# This next part is only necessary to allow the illustration of progress
if {$split == 10 && [llength $::coords]>2} {
.c coords dragon $::coords update
}
incr split -1
set sublen [expr {$len/$r2}]
turn [expr {$d*45}]
dragon $sublen $split 1
turn [expr {$d*-90}]
dragon $sublen $split -1
turn [expr {$d*45}]
}
set coords {150 180} set a 0.0 pack [canvas .c -width 700 -height 500] .c create line {0 0 0 0} -tag dragon dragon 400 17 .c coords dragon $coords</lang>
TI-89 BASIC
<lang ti89b>Define dragon = (iter, xform) Prgm
Local a,b If iter > 0 Then dragon(iter-1, xform*[[.5,.5,0][–.5,.5,0][0,0,1]]) dragon(iter-1, xform*[[–.5,.5,0][–.5,–.5,1][0,0,1]]) Else xform*[0;0;1]→a xform*[0;1;1]→b PxlLine floor(a[1,1]), floor(a[2,1]), floor(b[1,1]), floor(b[2,1]) EndIf
EndPrgm
FnOff PlotsOff ClrDraw dragon(7, [[75,0,26] [0,75,47] [0,0,1]])</lang>
Valid coordinates on the TI-89's graph screen are x 0..76 and y 0..158. This and the outer size of the dragon curve were used to choose the position and scale determined by the transformation matrix initially passed to dragon such that the curve will fit onscreen no matter the number of recursions chosen. The height of the curve is 1 unit, so the vertical (and horizontal, to preserve proportions) scale is the height of the screen (rather, one less, to avoid rounding/FP error overrunning), or 75. The curve extends 1/3 unit above its origin, so the vertical translation is (one more than) 1/3 of the scale, or 26. The curve extends 1/3 to the left of its origin, or 25 pixels; the width of the curve is 1.5 units, or 1.5·76 = 114 pixels, and the screen is 159 pixels, so to center it we place the origin at 25 + (159-114)/2 = 47 pixels.
Vedit macro language
Vedit is a text editor, so obviously there is no graphics support in the macro language. However, since Vedit can edit any file, including graphics files, it is possible to do some graphics.
This implementation first creates a blank BMP file in an edit buffer, then plots the fractal in that file, and finally calls the application associated to BMP files to display the results.
The DRAGON routine combines two steps of the algorithm used in other implementations. As a result, each turn is 90 degrees and thus all lines are vertical or horizontal (or alternatively diagonal). In addition, the length is divided by 2 instead of square root of 2 on each step. This way we can avoid using any floating point calculations, trigonometric functions etc.
<lang vedit>File_Open("|(USER_MACRO)\dragon.bmp", OVERWRITE+NOEVENT) BOF Del_Char(ALL)
- 11 = 640 // width of the image
- 12 = 480 // height of the image
Call("CREATE_BMP")
- 1 = 384 // dx
- 2 = 0 // dy
- 3 = 6 // depth of recursion
- 4 = 1 // flip
- 5 = 150 // x
- 6 = 300 // y
Call("DRAGON") Buf_Close(NOMSG)
Sys(`start "" "|(USER_MACRO)\dragon.bmp"`, DOS+SUPPRESS+SIMPLE+NOWAIT) return
///////////////////////////////////////////////////////////////////// // // Dragon fractal, recursive //
- DRAGON:
if (#3 == 0) {
Call("DRAW_LINE")
} else {
#1 /= 2
#2 /= 2
#3--
if (#4) {
Num_Push(1,4) #4=1; #7=#1; #1=#2; #2=-#7; Call("DRAGON") Num_Pop(1,4) Num_Push(1,4) #4=0; Call("DRAGON") Num_Pop(1,4) Num_Push(1,4) #4=1; #7=#1; #1=-#2; #2=#7; Call("DRAGON") Num_Pop(1,4) Num_Push(1,4) #4=0; Call("DRAGON") Num_Pop(1,4)
} else {
Num_Push(1,4) #4=1; Call("DRAGON") Num_Pop(1,4) Num_Push(1,4) #4=0; #7=#1; #1=-#2; #2=#7; Call("DRAGON") Num_Pop(1,4) Num_Push(1,4) #4=1; Call("DRAGON") Num_Pop(1,4) Num_Push(1,4) #4=0; #7=#1; #1=#2; #2=-#7; Call("DRAGON") Num_Pop(1,4)
}
} return
///////////////////////////////////////////////////////////////////// // // Daw a horizontal, vertical or diagonal line. #1 = dx, #2 = dy //
- DRAW_LINE:
while (#1 || #2 ) {
#21 = (#1>0) - (#1<0) #22 = (#2>0) - (#2<0) #5 += #21; #1 -= #21 #6 += #22; #2 -= #22 Goto_Pos(1078 + #5 + #6*#11) IC(255, OVERWRITE) // plot a pixel
} return
///////////////////////////////////////////////////////////////////// // // Create a bitmap file //
- CREATE_BMP:
// BITMAPFILEHEADER: IT("BM") // bfType
- 10 = 1078+#11*#12 // file size
Call("INS_4BYTES") IC(0, COUNT, 4) // reserved
- 10 = 1078; Call("INS_4BYTES") // offset to bitmap data
// BITMAPINFOHEADER:
- 10 = 40; Call("INS_4BYTES") // size of BITMAPINFOHEADER
- 10 = #11; Call("INS_4BYTES") // width of image
- 10 = #12; Call("INS_4BYTES") // height of image
IC(1) IC(0) // number of bitplanes = 1 IC(8) IC(0) // bits/pixel = 8 IC(0, COUNT, 24) // compression, number of colors etc.
// Color table - create greyscale palette for (#1 = 0; #1 < 256; #1++) {
IC(#1) IC(#1) IC(#1) IC(0)
}
// Pixel data - init to black for (#1 = 0; #1 < #12; #1++) {
IC(0, COUNT, #11)
} return
// // Write 32 bit binary value from #10 in the file //
- INS_4BYTES:
for (#1 = 0; #1 < 4; #1++) {
Ins_Char(#10 & 0xff) #10 = #10 >> 8
} return</lang>
- Recursion
- Programming Tasks
- Fractals
- ALGOL 68
- AutoHotkey
- BASIC
- BBC BASIC
- C
- Common Lisp
- CLIM
- D
- F Sharp
- Windows Presentation Foundation
- Forth
- Go
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Liberty BASIC
- Logo
- Lua
- Mathematica
- Metafont
- OCaml
- Tk
- Perl 6
- Pascal
- PicoLisp
- PostScript
- Prolog
- PureBasic
- Python
- Turtle
- RapidQ
- Ruby
- Shoes
- Run BASIC
- Seed7
- SVG
- SVG examples needing attention
- Examples needing attention
- Tcl
- TI-89 BASIC
- Vedit macro language