Marching Squares

A fun little demo to distract me from the upcoming exams.
Play around with the settings to see how it affects the background!

10 12

What is this?

According to Wikipedia, the marching squares algorithm is a computer graphics algorithm that generates contours for a 2D scalar field. Simple enough, right? Let's break down what that means. In computer graphics, we oftentimes have a grid of values, e.g. when working with images. Maybe the image is a height map of the natural terrain around us, then it would be interesting to draw contours around areas, that are at a certain elevation, like the contour lines you see in maps. The marching squares algorithm gives us an easy way to do that, and here's how:

The Numbers

First, let's create some data to draw contours around.
To create these merging blobs, we can generate a bunch of points, that bounce around in the box and calculate the distance to each one of them. Each of our grid cells then get's assigned the inverse sum of those distances, so cells that are close to one or multiple balls have high values, while cells far away are close to zero.

Fill a single cell

Now let's get into the fancy stuff. First we have to decide on a value, that we want to draw our contours around. I chose one, so all points greater than one will be contained in the resulting blobs, and all values smaller than one will be outside.
To achieve that, we treat each grid point as one of four cell corners. For each corner we check if the value is above or below the threshold value and save that information. The resulting cell will have one of the 16 possible configurations of corners that are "inside" or "outside" the contour. Then we just do a lookup, and draw the according one of the 16 line configurations over the cell, as shown in the next image.

Rinse and repeat

Now we just repeat the process until we covered all cells and get a contour plot! It might still look a bit blocky, but we can improve that by simply increasing the resolution.

Linear interpolation

The final step is to smooth out the lines, by adjusting their position. For that, we linearly interpolate our threshold value between the two adjacent corner values. I for example am using a threshold value of 1, so if one corner point has a value of 0.5 and The adjacent corner has a value of 1.5, the line segment will be placed exactly in the middle. If the corners had the values 0.5 and 3, the line would be placed a lot closer to the left. This kind of linear interpolation is given by the following formula:
f(x, y) = (1 - x) / (y - x)
With x being the left corner value, y the right and the hardcoded threshold being 1. f(x, y) then returns a percentage describing the resulting points position.

With interpolation, the final contours look like this:

What now?

Go forth and draw contours around whatever your heart desires! Nothing can stop you, now that you have mastered the power of the squares! If you still want to learn more about this algorithm, check out Jamie Wong's blogpost that inspired me in the first place, or my code for this page on GitHub.