Pick’s Theorem

In JavaScript!

I recently learned about Pick’s Theorem. It’s a simple way to calculate the area of simple polygons, in a grid of equidistant points. If you’ve not heard of it, check out the video!

I was curious about how I could make an interactive version of the algorithm. I imagined some kind of grid, on which I could click to build a polygon. And then it would work out which points were inside and which were on the boundaries, and finally calculate the area inside.

It turned out to be fun!

Drawing the grid

It would help if you were familiar with the Canvas element, and some of the basics of drawing on a canvas element...

I started off with a basic HTML page:

This creates a canvas over the whole page, so we have the whole surface to draw on. Next, we need to add some code to draw a grid. We’ll use functions as a kind of class structure:

Here we create a Theorem function, and store the canvas element and block size (interval) as properties. Every time we say var instance = new Theorem(element, number), instance will have its own canvas and instance properties. They’ll be a reference to what we provided in the make-shift constructor.

We create an “instance” method by adding functions to the Theorem prototype, so that inside them this is bound to a specific object.

this can be confusing at first. Read a bit more about it...

It would be handy if the grid could re-draw itself when the window size changes. So let’s do that:

These methods give us a way to add and remove event listeners on the elements of our HTML page. Right now we’ve only got one, but we’ll have a few more before we’re done…

Clicks and lines

The aim of this is to allow interaction, so we want to show where people have clicked and draw lines between these points. We also want a way to reset these clicks and lines so we can start over if we make a mistake or want to try different shapes!

Our reset function sets a few object properties back to a “clean” state. We’re going to track four different sets of points (on our grid). We want to remember where users have clicked, so those go in “click”. Later we’ll calculate where shape lines meet grid points, so we’ll put those in “boundary”. We’ll calculate all grid points inside the shape and put those in “interior”.

Every time we need to calculate those last two, we need to scan all the likely points of the grid where there could be lines or clicks. This can get expensive unless we try to refine the search area. Every time we click, we can narrow our search area to number of grid points shapes could be in, and exclude the rest. The refined list of search points is what we’ll store in “check”.

Let’s start tracking grid clicks…

Each time we click, we add an object (with x and y values) to the array of click points. We’re only interested in points on the grid, so we round to the nearest grid point and take those x and y values. Then we need to draw lines between these points:

Now, when you click on the grid, you should see lines drawn from click to click! Remember how I said we need to try and limit the number of grid points we constantly check? Let’s do that now:

When you click, you’ll see faint red dots on all the grid points that we’ll check. Take another look at the `click` method. We’re only adding click points if they are unique. So how can we close a shape? Let’s add another method for that!

You’ll want to add that same if (this.closed) check to the click method, so it stops drawing lines when the shape is closed.

In addition to this, we should also fill the shape in, so it’s easier to see!

Now you should be able to create new shapes. Just a few left-clicks, and a right-click to close them. Remember you can use space to start over.

Boundary and interior points

Now we’re getting to the fun bits. Pick’s Theorem is really about the grid points on the boundary and inside a shape. It would be easy to draw the places we’ve clicked, but what about the grid points we haven’t clicked If polygon lines cross over those points, we still need to add them to the calculation.

There’s some interesting stuff going on here. We step through each of the grid points in our “check” array. Then we fetch a 3x3 pixels around it. If we see colours there that match the polygon shape colour, we assume they are grid points on the boundary.

If they’re not on a boundary, we check if they have colours that match the faint red dot of a check point. If they are dark enough to be under the fill of the shape, we assume they are grid points inside the shape.

We redraw boundary points in blue and interior points in green. Now that we know how many there are, we can do the calculation:

That’s it! You can see a demo of this code on GitHub, and the full source code is there too.