Pascal Thormeier

Posted on Oct 30, 2020 • Edited on Aug 24, 2021

Let's build a Mandelbrot set visualizer

#math #javascript #computerscience #tutorial

Writing about the Levenshtein edit distance was a lot of fun. I got to test out my whiteboard desk and share my knowledge. So I asked which algorithm I should tackle next.

As suggested by Raphi on Twitter, in this post, I'll explain roughly what the Mandelbrot set is and how to build a Mandelbrot set visualizer in JavaScript with canvas.

The Mandelbrot what?

The Mandelbrot set. As defined/discovered by Benoît Mandelbrot in 1980. It's a fractal, roughly meaning that it's an infinitely complex structure that is self-similar. It looks like this when visualized:

(Created by Prateek Rungta, found on Flickr, released under CC BY 2.0)

How is the Mandelbrot set defined?

The Mandelbrot set is the set of complex numbers $c$ for which this iteration does not diverge:

z_0 = 0 \newline z_{n+1} = z^{2}_{n} + c

For those unfamiliar with calculus or complex numbers, I'll take a quick detour of what "diverging" and "complex numbers" mean:

Converging and diverging functions

Calculus is all about change. When we talk about if a function (or a series or an infinite sum) approaches a certain value and gets almost to it, but never quite reaches it, we talk about a converging function.

When a function diverges, it either blows off to infinity or negative infinity. The two graphs in the picture show both - A converging function and a diverging one:

(A third kind of function would be alternating ones. Those oscillate between values but don't stay there.)

So what does that mean for the definition of the Mandelbrot set? It means that the value for $z_{n+1}$ does not blow up to infinity or negative infinity.

Complex numbers

All numbers (0, 1, -13, Pi, e, you name it) can be arranged in a number line:

Any number is somewhere on this line. The number line is one-dimensional. Complex numbers introduce a second dimension. This new dimension is called the "imaginary part" of the complex number, whereas the usual number line is called the "real part" of this number. A complex number thus looks like this:

a+bi

$a$ is the real part, $bi$ the imaginary part with the imaginary unit $i$ . Examples for complex numbers would be $12+6i$ or $-3-87i$ . The number line thus evolves into a number plane and would look like this (with the example of $2+1i$ ):

Complex numbers come with a set of special calculation rules. We need to know how addition and multiplication work. Before we dive a little too deep into the why, we just look up the rules and roll with them:

Multiplication: (a+bi)*(c+di)=(ac-bd)+(ad+bc)i \newline Addition: (a+bi)+(c+di)=(a+c)+(b+d)i

Another side note: All numbers are by default complex numbers. If they're right on the number line, they're represented with an imaginary part of 0. For example $5$ is actually $5+0i$

So complex numbers can be displayed on an X/Y plane. For each number $X + Yi$ we can say if it belongs to the Mandelbrot set or not.

The signature pattern emerges when we give those points on the complex number plane that belong to the Mandelbrot set a different color.

With this knowledge we can get going!

Let's implement this

We start with a representation of complex numbers.

class Complex {
  constructor(real, imaginary) {
    this.real = real
    this.imaginary = imaginary
  }

  plus(other) {
    return new Complex(
      this.real + other.real,
      this.imaginary + other.imaginary
    )
  }

  times(other) {
    return new Complex(
      (this.real * other.real - this.imaginary * other.imaginary),
      (this.real * other.imaginary + other.real * this.imaginary)
    )
  }
}

The rules for multiplication and addition are now already in there. These complex number objects can now be used like this:

const x = new Complex(1, 2) // (1 + 2i) 
const y = new Complex(3, -3) // (3 - 3i)

console.log(x.plus(y), x.times(y))

Awesome. Now let's implement the function that checks if a given complex number converges with the given iteration:

/**
 * Calculates n+1
 */
const iterate = (n, c) => n.times(n).plus(c)

/**
 * Checks if a complex number `c` diverges according to the Mandelbrot definition.
 */
const doesDiverge = (c, maxIter) => {
  let n = new Complex(0, 0)
  for (let i = 0; i < maxIter; i++) {
    n = iterate(n, c)
  }

  // If the iteration diverges, these values will be `NaN` quite fast. Around 50 iterations is usually needed.
  return isNaN(n.real) || isNaN(n.imaginary)
}

We can now ask this function to tell us if a complex number $c$ is within the Mandelbrot set:

!doesDiverge(new Complex(1, 1), 100) // false
!doesDiverge(new Complex(0, 0), 100) // true

Building the visualization

So far so good, we're almost there. Now we can visualize the Mandelbrot set. We'll add a click zoom option as well. For this, we'll use a canvas and some more elements:

<!-- Used to control the zoom level etc. -->
<div class="controls">
  <div>
    Zoom size:
    <input type="range" min="2" max="50" value="10" id="zoomsize">
  </div>

  <input type="button" id="reset" value="Reset">
</div>

<!-- A little box that shows what part of the Mandelbrot set will be shown on click -->
<div class="selector"></div>

<!-- The canvas we'll render the Mandelbrot set on -->
<canvas class="canvas" />

And style these a little bit:

html, body {
  margin: 0;
  padding: 0;
  height: 100%;
}
.controls {
  position: fixed;
  background-color: #f0f0f0;
  z-index: 1000;
}
.selector {
  border: 2px solid #000;
  opacity: .2;
  position: fixed;
  z-index: 999;
  transform: translate(-50%, -50%);
  pointer-events: none;
}
.canvas {
  width: 100%;
  height: 100vh;
}

So far so good. Let's head to the JS part. Since it's relatively independent, we'll start with the selector box:

// Size of the zoom compared to current screen size
// i.e. 1/10th of the screen's width and height.
let zoomsize = 10

/**
 * Makes the selector follow the mouse
 */
document.addEventListener('mousemove', event => {
  const selector = document.querySelector('.selector')
  selector.style.top = `${event.clientY}px`
  selector.style.left = `${event.clientX}px`
  selector.style.width = `${window.innerWidth / zoomsize}px`
  selector.style.height = `${window.innerHeight / zoomsize}px`
})

/**
 * Zoom size adjustment.
 */
document.querySelector('#zoomsize').addEventListener(
  'change', 
  event => {
    zoomsize = parseInt(event.target.value)
  }
)

Now the user has a clear indication which part of the Mandelbrot set they're going to see when they click.

The plan is now as follows: We define which part of the complex plane is visible (coordinates) and map this to actual pixels. For this we need an initial state and a reset button:

// X coordinate
const realInitial = {
  from: -2,
  to: 2,
}

// Y coordinate, keep the aspect ratio
const imagInitial = {
  from: realInitial.from / window.innerWidth * window.innerHeight,
  to: realInitial.to / window.innerWidth * window.innerHeight,
}

// Ranging from negative to positive - which part of the plane is visible right now?
let real = realInitial
let imag = imagInitial

document.querySelector('#reset').addEventListener('click', () => {
  real = realInitial
  imag = imagInitial

  // TODO: Trigger redraw.
})

Nice. Now we create a function that actually renders the Mandelbrot set pixel by pixel. I won't got into detail about the coordinate system juggling, but the main idea is to determine how much a number on X and Y coordinate changes by each pixel. For example: When there's a 50 by 100 pixel grid that represents a 5 by 10 number grid, each pixel is $0.1$ .

/**
 * Draws the Mandelbrot set.
 */
const drawMandelbrotSet = (realFrom, realTo, imagFrom, imagTo) => {
  const canvas = document.querySelector('canvas')
  const ctx = canvas.getContext('2d')

  const winWidth = window.innerWidth
  const winHeight = window.innerHeight

  // Reset the canvas
  canvas.width = winWidth
  canvas.height = winHeight
  ctx.clearRect(0, 0, winWidth, winHeight)

  // Determine how big a change in number a single pixel is
  const stepSizeReal = (realTo - realFrom) / winWidth
  const stepSizeImaginary = (imagTo - imagFrom) / winHeight

  // Loop through every pixel of the complex plane that is currently visible
  for (let x = realFrom; x <= realTo; x += stepSizeReal) {
    for (let y = imagFrom; y <= imagTo; y += stepSizeImaginary) {
      // Determine if this coordinate is part of the Mandelbrot set.
      const c = new Complex(x, y)
      const isInMandelbrotSet = !doesDiverge(c, 50)

      const r = isInMandelbrotSet ? 67 : 104
      const g = isInMandelbrotSet ? 65 : 211
      const b = isInMandelbrotSet ? 144 : 145

      // Cast the coordinates on the complex plane back to actual pixel coordinates
      const screenX = (x - realFrom) / (realTo - realFrom) * winWidth
      const screenY = (y - imagFrom) / (imagTo - imagFrom) * winHeight

      // Draw a single pixel
      ctx.fillStyle = `rgb(${r}, ${g}, ${b})`
      ctx.fillRect(screenX, screenY, 1, 1)
    }
  }
}

Now this should already render the Mandelbrot set as we know it:

drawMandelbrotSet(real.from, real.to, imag.from, imag.to)

Last but not least, a click on the canvas should now set the real and imag according to the selected section:

/**
 * Perform a zoom
 */
document.querySelector('canvas').addEventListener('click', event => {
  const winWidth = window.innerWidth
  const winHeight = window.innerHeight

  const selectedWidth = winWidth / zoomsize
  const selectedHeight = winHeight / zoomsize

  const startX =  (event.clientX - (selectedWidth / 2)) / winWidth
  const endX = (event.clientX + (selectedWidth / 2)) / winWidth
  const startY = (event.clientY - (selectedHeight / 2)) / winHeight
  const endY = (event.clientY + (selectedHeight / 2)) / winHeight

  real = {
    from: ((real.to - real.from) * startX) + real.from,
    to: ((real.to - real.from) * endX) + real.from,
  }

  imag = {
    from: ((imag.to - imag.from) * startY) + imag.from,
    to: ((imag.to - imag.from) * endY) + imag.from,
  }

  drawMandelbrotSet(real.from, real.to, imag.from, imag.to)
})