<p>The marching squares is a well know algorithm in computer science. I'll show you how to recreate this demo in Javascript,
but first mess around with demo, and see if you can figure out how it is done!</p>

<div id="container"></div>
<span id="slider"></span>
<h2>What is Marching Squares</h2>
<p>Alright, so unless you an ultra-nerd like me you've probably never heard of the algorithm before. So let me explain the problem we
are trying to solve. Let's start with a real world example that you are probably familiar with. If you wanted to tell a
computer to draw a line on a map that separated all areas above 100 feet from all areas below 100 feet, how would you do it?</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/Topographic_map_example.png" class="img-bordered" style="max-height: 450px">
    <br>
    <small><i><a href="https://commons.wikimedia.org/wiki/File:Topographic_map_example.png">United States Geological Survey (Public Domain)</a></i></small>
</div>
<p>We can see how useful it is to draw distinctions between groups in data, but trying to come up with a efficient way to
solve this is not a trivial problem. Let's simplify this a little more.
Say we have a grid of values we want to separate into 2 groups, and to make it simple we
will be using be using 0's and 1's. If we draw these points as squares it would look something like this.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/no-lines-example.png" class="img-bordered" style="max-height: 300px">
</div>
<p>Just looking at that image I bet you immediately separate the image into 2 groups, foreground and background. Pretty amazing how our brain does that,
but unfortunately computers aren't as straightforward.<br>
What we want the computer to do the same thing by drawing a line separating the 2 groups. No gaps allowed, and it needs to be done fast enough to
see live, like the animation above. This is the goal of the Marching Squares algorithm. If you looked at each group of 4 points,
and drew a line according to the this guide, you would come out with a perfect separation between the 2 groups.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/marching-squares-example.png" class="img-bordered" style="max-height: 450px">
    <br>
    <small><i><a href="https://en.wikipedia.org/wiki/Marching_squares#/media/File:Marching-squares-isoline.png">Credit: Mikhailfranco</a></i></small>
</div>
<h2>Prerequisites</h2>
<p>This animation was written using <a href="https://p5js.org/">p5.js</a>. I would recommend looking at getting started <a href="https://p5js.org/get-started/">guide</a>
if you want to start making animations that you can share on the web! So to get started using this in a project you can simply add this tag to your html.</p>
<pre><code class="language-html">&#x3C;script src="https://cdn.jsdelivr.net/npm/p5@1.1.9/lib/p5.js">&#x3C;/script>
</code></pre>
<p>I will also be using this <a href="https://github.com/josephg/noisejs">Perlin noise</a> code to generate our data. Just download it
and link it locally in your HTML.</p>
<h2>Set-up</h2>
<p>First, we need to set some environment variables.</p>
<pre><code class="language-javascript">var scalar_array
var SPACE_BETWEEN = 10
var CANVAS_HEIGHT = 500
var CANVAS_WIDTH = 500

generate_noise.seed(Math.random())
function getNoise(x, y) {
    let d = new Date()
    return generate_noise.perlin3(x / 12, y / 12, d.getTime() / 3000)+1
}
</code></pre>
<p>We will store our gid of data in <code>scalar_array</code>, and <code>SPACE_BETWEEN</code> will be used to change the resolution of the points
on the screen. If you have troubles with performance you can try increasing <code>Space_between</code>,  make sure it can divide
into the resolution of the canvas we set later on.<br>
<code>generate_noise</code> is a function of the Perlin noise code that I referenced earlier. To use this you need to give it a seed,
<code>Math.random()</code> will do just fine. Next we need to pass in x, y, and z coordinates to get a value between -1 to 1.
We will pass in x and y to the function <code>getNoise(x,y)</code> and the current time will be our z coordinate.
Just use <code>generate_noise.perlin3(x, y, z)</code> from above, and we add 1 to the value so we only get postive values between 0 and 2.</p>
<h2>Creating the Canvas</h2>
<p>If you have never used p5.js before there are 2 major functions you will need to know about <code>Setup()</code> and <code>Draw()</code>.
<br>
<code>Setup()</code> is called once at the beginning for p5.js. This is where we create the canvas, and set some settings for our animation.</p>
<pre><code class="language-javascript">function setup() {
    canvas = createCanvas(CANVAS_WIDTH, CANVAS_HEIGHT)
    canvas.parent('container')
    frameRate(30)
    loop()
}
</code></pre>
<p><code>createCanvas(x, y)</code> will create a canvas of the specified size. <code>canvas.parent('#id')</code> sets the canvas tag to be a child
of an HTML tag with that ID. Put this HTML tag in you page and the <code>canvas</code> will appear there. <em><strong>NOTE!</strong></em> Make sure to
link your script below the container tag, otherwise you will get some errors.</p>
<pre><code class="language-html">&#x3C;div id="container">&#x3C;/div>
</code></pre>
<p><code>frameRate(FPS)</code> tells p5.js how many frames a second we want to render, you can also lower this number if you are getting
poor performance. And we won't draw more than one frame unless we specify <code>loop()</code> as well.</p>
<h2>Draw!</h2>
<p>Alright now for the fun stuff! The <code>draw()</code> function is repeatedly called, so we can put our main logic and call to draw
things in the canvas here.</p>
<pre><code class="language-javascript">function draw() {
    clear()
    background(0)
}
</code></pre>
<p>Ok, now we run our code all we get is a blank canvas. Let's change that!</p>
<h2>Get to the Point</h2>
<p>Let's start getting some points on the screen. First, lets add one more line of code to the beginning of <code>setup()</code></p>
<pre><code class="language-javascript">scalar_array = Array(CANVAS_WIDTH / SPACE_BETWEEN + 1).fill(0).map(() =>
               Array(CANVAS_HEIGHT / SPACE_BETWEEN + 1).fill(0))
</code></pre>
<p>This creates a 2d array for <code>scalar_array</code> based off our environment variables we made earlier. New we can iterate
over each entry in the array to generate a point on the screen.<br>
Now add this next piece of code to the end of <code>draw()</code></p>
<pre><code class="language-javascript">let square_size = Math.floor(SPACE_BETWEEN / 3)

// Main Loop
for(let x = 0; x &#x3C; scalar_array.length; x++){
    for(let y = 0; y &#x3C; scalar_array[x].length; y++){
        // Create a point object for entry in the array
        // TODO: This could be done a lot more efficiently
        scalar_array[x][y] = {
            data: Math.floor(getNoise(x,y)),
            xpos: x * SPACE_BETWEEN,
            ypos: y * SPACE_BETWEEN,
            x: x,
            y: y,
        }

        // If point is active draw a square
        fill(0, 255, 0)
        if(scalar_array[x][y].data !== 0){
            square(scalar_array[x][y].xpos - square_size / 2, scalar_array[x][y].ypos - square_size / 2, square_size)
        }

        // WE WILL BE ADDING MORE CODE HERE LATER
    }
}
</code></pre>
<p><em>When I mention adding more code to the main loop later, put it where that comment is.</em>
<br>
Ok this a bit of to get though, but bear with me. <code>square_size</code> is pretty self-explanatory. The Main Loop
integrates though each entry in the <code>scalar_array</code>. Then we assign each position an object. The most important thing
to notice here is the <code>.data</code> info. Here we are getting our random value and rounding it down to 0 or 1. <em>Technically</em>
we could get 2 as well, but it won't cause any problems so we will ignore that.<br>
The next important part is where we actually draw the squares. <a href="https://p5js.org/reference/#/p5/fill"><code>fill(r,g,b)</code></a> sets the
color we want to use to <em>fill</em> our squares. The <a href="https://p5js.org/reference/#/p5/square"><code>square(x, y, SIZE)</code></a> lets a
draw a square on the canvas. It draws the the top left corner at the x and y coordinate we pass to the function, so we
will move that by half of the size of the square to center it.<br>
You're code should draw a canvas similar to the photo from before.</p>
<h2>Drawing a Line in the... Square?</h2>
<p>Now for the hard part. We need to come up with an algorithm to draw the lines for each square. We are going to define a
square as a point and it's neighbors up 1 position, left 1 position, and both.</p>
<p>Since any point at the very top or very left of the canvas won't have any of those neighbors lets add this statement
to our main loop before we start adding code to it.</p>
<pre><code class="language-javascript">if(x > 0 &#x26;&#x26; y > 0){
    // More here later
}
</code></pre>
<p>We could write a case for every combination of points in a square, and for each case draw a different line.
However, I'm lazy so I tried to do the same thing in as little lines of code as possible. Let's see how this goes.<br>
Now that we are only checking the correct position we can now collect all the points of the square into one array.
After we do that, we can filter that array down to just the points are active so we can know how many there are.<br>
Put this inside the if statement block.</p>
<pre><code class="language-javascript">let current_square = [scalar_array[x - 1][y - 1], scalar_array[x][y - 1], scalar_array[x][y], scalar_array[x - 1][y]]
let active_corners = current_square.filter(point => point.data >= 1)
</code></pre>
<h3>One Point Active</h3>
<p>Let's break this problem down step by step. We will start with squares that only have one active point.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/single-point-squares.png" class="img-bordered">
</div>
<p>If you look at the image you might notice a pattern. A line is just a connection of 2 vectors on the canvas. If you look
at the diagram you will notice whenever one of the top two corners are active, one of the vectors is in the top middle
of the square. The opposite is true. The same pattern arises when you look at the left vs. the right. Since there is a
pattern with a little bit of Math we handle this with a few lines of code. Add this function to the bottom of your
Javascript code.</p>
<pre><code class="language-javascript">function onePointActive(point, x, y){
    noFill()
    stroke(color(0,255,0))
    let xval = point.x - x
    let yval = point.y - y
    let line_vector = {
        x1: x*SPACE_BETWEEN - SPACE_BETWEEN / 2,
        y1: (y + yval) * SPACE_BETWEEN,
        x2: (x + xval) * SPACE_BETWEEN,
        y2: y*SPACE_BETWEEN - SPACE_BETWEEN / 2,
    }
    line(line_vector.x1, line_vector.y1, line_vector.x2, line_vector.y2)
}
</code></pre>
<p><a href="https://p5js.org/reference/#/p5/noFill"><code>noFill()</code></a>, <a href="https://p5js.org/reference/#/p5/stroke"><code>stroke()</code></a>, and <a href="https://p5js.org/reference/#/p5/color"><code>color()</code></a>
are all most p5.js functions, if you need to read more on them I've provided links.<br>
First, we need to know what corner is active for the current square. This is the purpose of <code>xval</code> and <code>yval</code>.
<code>xval</code> will be 0 if the corner in on the bottom of the square, or -1 if it is on the top. <code>yval</code> is similar in where it
will be 0 if the active corner is on the right or -1 if it is on the left.
<br>
We then use these values to make 2 vectors. <code>x1</code> and <code>y1</code> make up the vector on the top or bottom the square. <code>x2</code> and <code>y2</code>
make up the left or right vector. Now we plug that into the <a href="https://p5js.org/reference/#/p5/line"><code>line()</code></a> function
and we are good to go!
<br>
Now we need to pass a point to this function each time we only have one active point. Add this to our if block from earlier.</p>
<pre><code class="language-javascript">if(active_corners.length === 1){
    onePointActive(active_corners[0], x, y)
}
</code></pre>
<p>You should see an output similar to this now.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/one-line-example.png" class="img-bordered" style="max-height: 350px">
</div>
<h3>Two Points Active</h3>
<p>So new lets figure out what to do if we have 2 points active on out square. We will go ahead put this right after the last
if statement we made.</p>
<pre><code class="language-javascript">else if(active_corners.length === 2){
    twoPointsActive(active_corners, x, y)
}
</code></pre>
<p>Let's take a peek at the our guide again.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/two-point-squares.png" class="img-bordered">
</div>
<p>This one look even easier. If both points are on the left or right, we draw a vertical line.
If both points are both are on the top or bottom, we draw a horizontal line.<br>
Go ahead and slap this function below the <code>onePointActive</code> function.</p>
<pre><code class="language-javascript">function twoPointsActive(active_corners, x, y){
    noFill()
    stroke(color(0, 255, 0))
    // If points are complements treat them both as solo points
    if (active_corners[0].x === active_corners[1].x){
        xval = x * SPACE_BETWEEN - SPACE_BETWEEN / 2
        line(xval, y * SPACE_BETWEEN, xval, (y - 1) * SPACE_BETWEEN)
    }
    else if (active_corners[0].y === active_corners[1].y){
        yval = y * SPACE_BETWEEN - SPACE_BETWEEN / 2
        line(x * SPACE_BETWEEN, yval, (x - 1) * SPACE_BETWEEN, yval)
    }
}
</code></pre>
<p>This one isn't too complicated compared to the last one. We are checking the corners if we should draw a vertical
or horizontal line. Then we draw the line.</p>
<p>Now we should be getting something like this.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/two-points-p1-example.png" class="img-bordered" style="max-height: 350px">
</div>
<h3>Two Points Active the Sequel</h3>
<p>Ok, so that actually wasn't all the combinations for points. If you noticed what I was skipping over, nice work! Here have a cookie. 🍪</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/missing-two-point-squares.png" class="img-bordered">
</div>
<p>There's actually a couple of ways we could handle opposite active corners. To make things simple lets pretend they
each a single active point. It's a pretty uncommon occurrence anyways. Plus we get to reuse our code from earlier! Add
this to the end of <code>twoPointsActive</code> function from earlier.</p>
<pre><code class="language-javascript">else {
    onePointActive(active_corners[0], x, y)
    onePointActive(active_corners[1], x, y)
}
</code></pre>
<h3>Three Points Active</h3>
<p>Almost there! Now that you know I'm a cheat, you might be able to tell what I'm going to do next.</p>
<div style="text-align: center;">
    <img src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/three-point-squares.png" class="img-bordered">
</div>
<p>Since three points being active is the same line drawn as the opposite one points being active, we can just pass the one
point that isn't active to our <code>onePointActive</code> and get the desired result. Add this final chunk of code to our if block
at the end of if statment in <code>draw()</code> and we will be good to go.</p>
<pre><code class="language-javascript">else if(active_corners.length === 3){
    let inactive_corners = current_square.filter(point => point.data &#x3C; 1)
    onePointActive(inactive_corners[0], x, y)
}
</code></pre>
<p>Here we filter out the active corners instead and pass the one inactive corner to our function.</p>
<h2>End</h2>
<p>And that's it! You should have the complete animation up and running now. If you want to see a couple of extras like resizing the
canvas or pausing the animation when it is scrolled out of view checkout the full source code on github below!</p>
<h2>Links</h2>
<p>You can find the source code for this project on my <a href="https://github.com/Logan-Ruf/Marching-Squares">Github</a>.<br>
If you enjoyed this post leave it a star!<br>
<br>
The algorithm used to generate the random data in the animation was written by <a href="https://github.com/josephg/noisejs">Joseph Gentle</a></p>
<script src="https://cdn.jsdelivr.net/npm/p5@1.1.9/lib/p5.js"></script>
<script src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/perlin.js"></script>
<script src="/assets/blog/2020-11-04-Marching_Squares-Algorithm/marching_squares.js"></script>

Marching Squares Algorithm - Tutorial