A fun little demo to distract me from the upcoming exams.
Play around with the settings to see how it affects the background!
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
commonly seen in geographical maps. The marching squares algorithm gives us an easy way to do that, and
here's how:
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.
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.
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.
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:
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.