Thursday November 22, 2007

You see on the left three simple polygons (a polygon is simple if its boundary does not cross itself.) How would you determine the areas of these shapes? The rectangle is easy. The blue polygon is a little more tedious since you need to count the number of interior grid squares. But how would you find the area of the red polygon?

As it turns out, you can easily compute the area of any simple polygon whose vertices are aligned on a regular, square grid using Pick's Theorem, which says the area of such a polygon can be found as I + B/2 - 1 where I is the number of grid points on the interior of the polygon and B is the number of grid points lying along the boundary of the polygon. I find it amazing that this works for any simple polygon.

We can see by inspection that the green rectangle has area 42 (6x7.) Let's apply Pick's Theorem. There are 30 grid points in the interior and 26 grid points on the boundary. 30 + 26/2 - 1 = 42. Magic. :-)

Now let's try the blue polygon. I = 25, B = 52, so Pick's Theorem says the area is 25 + 52/2 - 1 = 50, which is correct by inspection. By my count, the red polygon's area is 70 + 24/2 - 1 = 81. My lines are a little fat so I made some (consistent) judgement calls about "in" or "on"--your count may be slightly different than mine.

Visit this page to explore Pick's Theorem with an interactive Java applet. See this page for one proof of the theorem.