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 for which this iteration does not diverge:
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 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:
is the real part, the imaginary part with the imaginary unit . Examples for complex numbers would be or . The number line thus evolves into a number plane and would look like this (with the example of ):
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:
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 is actually
So complex numbers can be displayed on an X/Y plane. For each number 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
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
.
/**
* 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)
})
The finished result looks like this (Click "Rerun" if it looks off or is blank - happens because iframes, I guess):
Have fun exploring this infinitely complex structure!
Some screenshots
Here's a few screenshots of the visualisation:
Can you guess where the last one is located? Leave your guess in the comments!
I write tech articles in my free time. If you enjoyed reading this post, consider buying me a coffee!
Top comments (0)