Playing with Fractals

If you are a lover of fractals, analytical geometry and programming, in this article you will learn how to draw fractals using Java Script.

Fractals are geometric figures formed by repetitions of the same pattern a large number of times. A fractal gives us a graphical representation of what is commonly known in programming as recursion. In this post we will program some of the most famous fractals.

Auxiliary functions

Before getting into the matter, I will show you some complementary functions and libraries that were used to simplify the algorithms.

The external library Victor was used, which has a set of necessary functions when working with vectors.
The quque class was created, which consists of a very basic implementation of what a queue would be.

export const queue = function() {
    this.q = []

    this.push = function(ele) {
        this.q.push(ele)
    }

    this.empty = function() {
        return this.q.length === 0
    }

    this.top = function() {
        if(!this.empty())
            return this.q[0]
        return null
    }

    this.pop = function() {
        if(!this.empty())
            return this.q.shift()
        return null
    }
}

A paint.js file was created which contains a set of methods to simplify the process when "drawing" on the html canvas.

export const resetCanvas = (ctx, width, height) => {
    ctx.fillStyle = '#071a52'
    ctx.fillRect(0, 0, width, height)
    ctx.strokeStyle = "#f0f0f0"
}

export const drawLineVector = (ctx, v) => {

    for(let i = 0; i < v.length - 1; i++){
        ctx.beginPath()
        ctx.moveTo(v[i].x, v[i].y)
        ctx.lineTo(v[i+1].x, v[i+1].y)
        ctx.stroke()
        ctx.closePath()
    }
}

export const drawLine2Point = (ctx, p1, p2) => {
    ctx.beginPath()
    ctx.moveTo(p1.x, p1.y)
    ctx.lineTo(p2.x, p2.y)
    ctx.stroke()
    ctx.closePath()
}

Sierpinski triangle

As shown in the figure, the fractal is achieved by repeating the same triangle with smaller dimensions.

The following figure will help us understand the mathematical process:

We create the triangle P1P2P3
We calculate the midpoints P1', P2' and P3'
We create the triangles P1P1'P3', P1'P2P2'and P2'P3P3'
We repeat the process with the new triangles created.

Here is the code:

We import the necessary dependencies.

import Victor from 'victor'
import {drawLine2Point} from './paint'

We create a class Triangle

const Triangle = function(p1, p2, p3, tag) {
    this.p1 = p1
    this.p2 = p2
    this.p3 = p3
    this.tag = tag
    this.generated = false

    this.show = function(ctx){
        if(this.tag === 'root'){
            drawLine2Point(ctx, this.p1, this.p2)
            drawLine2Point(ctx, this.p2, this.p3)
            drawLine2Point(ctx, this.p3, this.p1)
        }else if(this.tag === 't1'){
            drawLine2Point(ctx, this.p2, this.p3)
        }else if(this.tag === 't2'){
            drawLine2Point(ctx, this.p3, this.p1)
        }else if(this.tag === 't3'){
            drawLine2Point(ctx, this.p1, this.p2)
        }
    }

    this.T1 = function() {
        let t1_p1 = new Victor(this.p1.x, this.p1.y)
        let t1_p2 = new Victor((this.p1.x + this.p2.x) / 2, (this.p1.y + this.p2.y) / 2)
        let t1_p3 = new Victor((this.p1.x + this.p3.x) / 2, (this.p1.y + this.p3.y) / 2)
        let t1 = new Triangle(t1_p1, t1_p2, t1_p3, 't1')
        return t1
    }

    this.T2 = function() {
        let t2_p1 = new Victor((this.p1.x + this.p2.x) / 2, (this.p1.y + this.p2.y) / 2)
        let t2_p2 = new Victor(this.p2.x, this.p2.y)
        let t2_p3 = new Victor((this.p2.x + this.p3.x) / 2, (this.p2.y + this.p3.y) / 2)
        let t2 = new Triangle(t2_p1, t2_p2, t2_p3, 't2')
        return t2
    }

    this.T3 = function() {
        let t3_p1 = new Victor((this.p1.x + this.p3.x) / 2, (this.p1.y + this.p3.y) / 2)
        let t3_p2 = new Victor((this.p2.x + this.p3.x) / 2, (this.p2.y + this.p3.y) / 2)
        let t3_p3 = new Victor(this.p3.x, this.p3.y)
        let t3 = new Triangle(t3_p1, t3_p2, t3_p3, 't3')
        return t3
    }
}

Finally we create the function that generates the fractal:

export const Sierpinski = (ctx, p1, p2, p3, n) => {
    let T = []
    let root = new Triangle(p1, p2, p3, 'root')
    T[0] = root

    while(n--){
        for(let i = T.length - 1; i >= 0; i--){
            if(!T[i].generated){
                T.push(T[i].T1())
                T.push(T[i].T2())
                T.push(T[i].T3())
                T[i].generated = true
            }
        }
    }

    for(let i = 0; i < T.length; i++){
        T[i].show(ctx)
    }
}

This function receives 5 parameters:

ctx Reference to the context of the canvas object canvas.getContext('2d')
p1 Object of type Victor that contains the coordinates of point p1.
p2 Object of type Victor that contains the coordinates of point p2.
p3 Object of type Victor that contains the coordinates of point p3.
n Integer representing the number of levels.

This is how our fractal will look:

Dragon curve

This fractal is built following the following steps:

Given a segment AB, an isosceles right triangle with base AB is constructed.
Segment AB is deleted.
The procedure is repeated a certain number of times.

The following image shows the process for the first 3 levels.

Here is the code:

We import the necessary dependencies:

import Victor from 'victor'
import {queue} from './queue'
import {drawLine2Point} from './paint'

We create an auxiliary function that returns the point between A and B that forms an isosceles and right triangle:

const mP = (p1, p2) => {

    return new Victor(
        (p1.x + p2.x + p1.y - p2.y) / 2, 
        (p2.x - p1.x + p1.y + p2.y) / 2)
}

We create the function that generates the fractal using a BFS algorithm.

let Q = new queue();

export const dragon_bfs = (ctx, a, b, n) => {
    let line = {
        p1: a,
        p2: b
    }

    if(!n){
        drawLine2Point(ctx, line.p1, line.p2)
    }else{
        Q.push(line)
        let N = Math.pow(2, n) - 1

        while(N){
            let l = Q.top()
            Q.pop()

            let l1 = {
                p1: l.p1,
                p2: mP(l.p1, l.p2)
            } 

            let l2 = {
                p1: l.p2,
                p2: mP(l.p1, l.p2)
            }
            Q.push(l1)
            Q.push(l2)
            N--
        }
        N = Math.pow(2, n)

        while(N){
            drawLine2Point(ctx, Q.top().p1, Q.top().p2)
            Q.pop()
            N--
        }
    }
}

This function receives 4 parameters:

ctx Reference to the context of the canvas object canvas.getContext('2d')
a Object of type Victor that contains the coordinates of point a.
b Object of type Victor that contains the coordinates of point b.
n Integer representing the number of levels.

This is how our fractal will look:

Von Kock's curve

Discovered by the mathematician Helge Von Koch in 1904. The curve is constructed as follows:

Given a segment AB is divided into three equal parts (3 segments).
With the middle segment we build an equilateral triangle.
The process is repeated for each of the smaller segments.

Let's see the process in the following figure:

Let's see for the first two levels:

Here is the code:

We import the dependencies

import {drawLineVector} from './paint'

We will create two helper functions.

The first to determine the points at 1/3 and 2/3 of the segment AB.

const getPoint = (a, b, t) => {
    return {
        x: a.x * (1 - t) + b.x * t,
        y: a.y * (1 - t) + b.y * t 
    }
}

This function receives 3 parameters: the points a and b of the segment to be partitioned and a proportion t, in such a way that when t=1/3 returns the point at 1/3 of the segment and when t=2/3 returns the point 2/3 of the segment.

The second function receives three parameters: a point p, a point c and an angle differential da (in radians). What it does is rotate point p gives radians about the circle with center c and radius equal to the distance between point p and point c.

const getCirPoint = (p, c, da) => {
    let dx = p.x - c.x
    let dy = p.y - c.y
    let r = Math.sqrt(dx*dx + dy*dy)
    let a = Math.atan2(dy, dx)
    a -= da

    let q = {
        x: c.x + r * Math.cos(a),
        y: c.y + r * Math.sin(a)
    }

    return q
}

Finally the function that generates the curve:

const pi = Math.PI

export const vonKock = (ctx, a, b, n) => {
    let P = [a, a, a, a, b]

    P[1] = getPoint(P[0], P[4], 1.0/3.0)
    P[3] = getPoint(P[0], P[4], 2.0/ 3.0)
    P[2] = getCirPoint(P[3], P[1], pi / 3.0)

    if(n <= 1){
        drawLineVector(ctx, P, true)
    }else{
        for(let i = 0; i < P.length - 1; i++)
            vonKock(ctx, P[i], P[i + 1], n-1)
    }
}

This function receives 4 parameters:

ctx Reference to the context of the canvas object (canvas.getContext('2d'))
a Object of type Victor that contains the coordinates of point a.
b Object of type Victor that contains the coordinates of point b.
n Integer representing the number of levels.

Here is another implementation that returns the same result:

const pi = Math.PI
export const vonKock = (ctx, a, b, n) => {
    let P = [a, a, a, a, b]

    P[1] = {
        x: a.x + (b.x - a.x) / 3,
        y: a.y + (b.y - a.y) / 3
    }

    P[3] = {
        x: b.x + (a.x - b.x) / 3,
        y: b.y + (a.y - b.y) / 3
    }

    P[2] = {
        x: (P[1].x + P[3].x) * Math.cos(pi/3) + (P[3].y - P[1].y)*Math.sin(pi/3),
        y: (P[1].y + P[3].y) * Math.cos(pi/3) - (P[3].x - P[1].x)*Math.sin(pi/3)
    }

    if(n <= 1){
        drawLineVector(ctx, P)
    }else{
        for(let i = 0; i < P.length - 1; i++)
            vonKock(ctx, P[i], P[i + 1], n-1)
    }
}

This is how our fractal will look:

Drawing trees

Now we will create fractals in the shape of trees.

To create this type of fractals we proceed as follows.

Given a segment AB, two smaller copies are created.
The new segments are rotated with a certain angle.
The two segments are translated until they coincide with point B.
The process is repeated for each segment.

The following figure shows the mentioned process.

By varying the new size and each angle of rotation you can create an infinite number of different trees.

Let's see the code:

We import the necessary dependencies

import Victor from 'victor'
import {drawLine2Point} from './paint'

We create a class Branch which will be a representation of a branch of the tree and has the following properties:

start An object of type Victor that represents the point where the branch begins.
end An object of type Victor that represents the point where the branch ends.
al Rotation angle (in radians) of the left (child) branch.
ar Angle of rotation (in radians) of the right branch (child).
divl Left Bundle Branch Growth Factor (child),
divr Right Branch (child) Growth Factor.

const Branch = function(start, end, al, ar, divl, divr) {
    this.start = start
    this.end = end
    this.left_angle = al
    this.right_angle = ar
    this.divl = divl
    this.divr = divr
    this.completed = false

    this.show = function(ctx) {
        drawLine2Point(ctx, this.start, this.end)
    }

    this.branchA = function() {
        let dir = new Victor(this.end.x, this.end.y).subtract(this.start) 
        dir.rotate(this.right_angle)
        dir.divide(new Victor(this.divr, this.divr))
        dir.add(this.end)

        let right = new Branch(this.end, dir, this.left_angle, this.right_angle, this.divl, this.divr)
        return right
    }

    this.branchB = function() {
        let dir = new Victor(this.end.x, this.end.y).subtract(this.start) 
        dir.rotate(this.left_angle)
        dir.divide(new Victor(this.divl, this.divl))
        dir.add(this.end)

        let left = new Branch(this.end, dir, this.left_angle, this.right_angle, this.divl, this.divr)
        return left
    }
}

Finally the code that generates the tree:

export const generateTree = (ctx, p1, p2, al, ar, divl, divr, n) => {
    let T = []
    let root = new Branch(p1, p2, al, ar, divl, divr)
    T[0] = root    

    while(n--){
        for(let i = T.length - 1; i >= 0; i--){
            if(!T[i].completed){
                T.push(T[i].branchA())
                T.push(T[i].branchB())
            }
            T[i].completed = true
        }
    }

    for(let i = 0; i< T.length; i++){
        T[i].show(ctx)
    }
}

This function receives 8 parameters:

ctx Reference to the context of the canvas object canvas.getContext('2d')
p1 Object of type Victor that contains the coordinates of the starting point of the trunk.
p2 Object of type Victor that contains the coordinates of the point where the stem ends.
al Angle of rotation (in radians) of the left branches.
ar Angle of rotation (in radians) of the right branches.
divl Left Branch Growth Factor.
divr Right branch growth factor.
n Integer representing the number of levels.

It should be noted that the growth factor must be in the range of 0 to 1 for everything to make sense.

This is how our fractal will look:

L-System

Finally, I will tell you about an algorithm that generalizes everything we have seen up to now, since with it you can obtain any possible fractal. The algorithm finds a great application when it comes to generating video game maps (both trees and terrain).

An L-System consists of an alphabet with which character strings are generated following certain rules and starting with an initial string called axion Let's see an example:

axion = "A"
rule1 = {key:"A", value:"AB"} //A =>> AB
rule2 = {key:"B", value:"C"} //B ==> C

//It generates
//1. A
//2. AB
//3. ABA
//4. ABAAB
//5. ABAABABA
//.......

Given this, a small interpreter can be built if we define some rules, for example:

If our string only contains the characters F [ ] + -, we can define that:

F Draw a vertical line
[ Saves the reference of the last point of the drawn segment to a stack.
] Pop point from the stack.
+ Rotate n degrees clockwise the segment to draw.
- Rotate n degrees counterclockwise the segment to draw.

With this defined all we have to do is correctly select the axion rules and angles to generate any desired shape.

For the programming we will create 3 functions, one that generates the pattern, another that interprets the generated pattern and the function that draws the figure.

First we import the dependencies.

import Victor from 'victor'
import {drawLine2Point} from './paint'

Function that generates the pattern:

const create_pattern = (sentence, rules) => {
    let nextSentece = ''
    for(let i = 0; i < sentence.length; i++){
        let current = sentence.charAt(i)
        let found = false
        for(let r = 0; r < rules.length; r++){
            if(current === rules[r].a){
                found = true
                nextSentece += rules[r].b
                break
            }
        } 
        if(!found)
            nextSentece += current
    }

    return nextSentece
}

Interpreter function

const interpreter = (ctx, sentence, a, b, angle) => {
    let stack = []

    let l = {
        p1: a,
        p2: b
    }


    for(let i = 0; i < sentence.length; i++){
        let current = sentence.charAt(i)

        if(current === 'F'){
            drawLine2Point(ctx, l.p1, l.p2)
            let newp1 = l.p2
            let newp2 = new Victor(l.p2.x, l.p2.y).subtract(l.p1)
            newp2.add(l.p2)

            l = {
                p1: newp1,
                p2: newp2
            }
        }else if(current === '+'){
            let newp1 = l.p1
            let newp2 = new Victor(l.p2.x, l.p2.y).subtract(l.p1)
            newp2.rotate(angle)
            newp2.add(newp1)
            l = {
                p1: newp1,
                p2: newp2
            }
        }else if(current === '-'){
            let newp1 = l.p1
            let newp2 = new Victor(l.p2.x, l.p2.y).subtract(l.p1)
            newp2.rotate(-angle)
            newp2.add(newp1)
            l = {
                p1: newp1,
                p2: newp2
            }
        }else if(current === '['){
            stack.push(l)
        }else if(current === ']'){
            l = stack.pop()
        }
    }
}

Finally the function that draws the fractal:

export const Lsystem = (ctx, axion, rules, a, b, angle, factor_scale, n) => {
    let sentence = axion
    let scale = 1
    while(n--){
        sentence = create_pattern(sentence, rules)
        scale *= factor_scale
    }

    let dir = new Victor(b.x, b.y).subtract(a) 
    dir.divide(new Victor(scale, scale))
    dir.add(a)
    interpreter(ctx, sentence, a, dir, angle)
}

This function receives 8 parameters: