Dragon curve
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
[edit] ALGOL 68
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)
Output:
 |
Note: each Dragon curve is composed of many smaller dragon curves (shown in a different colour).
[edit] AutoHotkey
[edit] BASIC
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
[edit] BBC BASIC
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
[edit] C
See: Dragon curve/C
[edit] 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).
#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;
}
[edit] 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.
(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))))
[edit] D
[edit] 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°
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);
}
- Output:
- - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - - - - - -
| | | | | | | | | | | | | | | |
- - - - - - - - - - - - - -
| | | | | | | | | | | |
- - - - - - - - - - - -
| | | | | | | | | | | |
- - - - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - - - -
| | | | | | | |
- - - - - -
| | | |
- - - -
| | | |
- -
[edit] With QD
See: Dragon curve/D/QD
[edit] With DFL
See: Dragon curve/D/DFL
[edit] F#
Using for visualization: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
[edit] 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
[edit] 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.
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])
}
Original version written to Bitmap task:
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])
}
[edit] 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
For plotting I use the gnuplot interface module from hackageDB
Use:
plotPath [] . map (\[x,y] -> (x,y)) $ dragoncurve!!13
[edit] HicEst
A straightforward approach, since HicEst does not know recursion (rarely needed in daily work)
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
[edit] 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.
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
[edit] J
require 'plot'
start=: 0 0,: 1 0
step=: ],{: +"1 (0 _1,: 1 0) +/ .*~ |.@}: -"1 {:
plot <"1 |: step^:13 start
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:
([:pd[:<"1|:)every'reset';|.'show';step&.>^:(i.17)<start
The curve can also be represented as a limiting set of the iterated function system
Giving the code
require 'plot'
f1=.*&(-:1j1)
f2=.[: -. *&(-:1j_1)
plot (f1,}.@|.@f2)^:12 ]0 1
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.
[edit] 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);
}
}
[edit] 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.
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
};
}());
My current demo page includes the following to invoke this:
...
<script src='./dragon.js'></script>
...
<div>
<svg xmlns='http://www.w3.org/2000/svg' id='fractal'></svg>
</div>
<script>
DRAGON.fractal('fractal', [100,300], [500,300], 15, false, 700);
</script>
...
[edit] Liberty BASIC
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
[edit] 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
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
[edit] 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.
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()
Output:
**** ****
* * * *
* * * *
**** *******
* *
* *
**** **** ****
* * *
* * *
**********
* * *
* * *
*******
*
*
**** ****
* * *
* * *
********** ****
* * * * *
* * * * *
**** ****************
* * * * * * *
* * * * * * *
*******************
* * * * *
* * * * *
******* ******* ****
* * * *
* * * *
******* **** **** ****
* * * * * *
* * * * * *
**** ********** ****
* * * *
* * * *
********** **** *******
* * * * * * * *
* * * * * * * *
******* ********** ****
* * * *
* * * *
******* *******
* * * *
* * * *
**** ****
[edit] Mathematica
Two functions: one that makes 2 lines from 1 line. And another that applies this function to all existing lines:
FoldOutLine[{a_,b_}]:={{a,#},{b,#}}&[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]]
[edit] 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.
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
The resulting character, magnified by 2, looks like:
[edit] OCaml
Example solution, using an OCaml class and displaying the result in a Tk canvas, mostly inspired by the Tcl solution.
(* 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 ();
;;
Here is another OCaml solution, in a functional rather than OO style:
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 ()
producing:
Run an example with:
ocaml -I +labltk labltk.cma dragon.ml
[edit] Perl 6
Iterative algorithm. Prints in SVG format.
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>";
[edit] Pascal
using Compas (Pascal with Logo-expansion):
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;
main program:
begin
init;
penup;
back(100);
pendown;
dcr(step,direction,length);
close;
end.
[edit] PicoLisp
This uses the 'brez' line drawing function from Bitmap/Bresenham's line algorithm#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 400 x 300
(dragon Img 10 45.0) # Build dragon curve
(out "img.pbm" # Write to bitmap file
(prinl "P1")
(prinl 300 " " 200)
(mapc prinl Img) ) )
[edit] 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
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).
%!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
- See also
[edit] 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.
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].
Output :
1 ?- dragonCurve(13). true
[edit] 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
[edit] 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)
A more pythonic version:
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
Other version:
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
[edit] RapidQ
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
[edit] 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
[edit] Run BASIC
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
[edit] 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;
Original source: [1]
[edit] 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”.
<?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"/>
<!-- useful for studying the transformation stages:
<line x1="0.1" y1="0" x2="0.9" y2="0.1"/> -->
</g>
<!-- These are identical except for the id and href. -->
<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>
[edit] 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
[edit] TI-89 BASIC
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]])
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.
[edit] 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.
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
Categories:
- 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
