Title: Verify Pick's Theorem in Python

[Pick's Theorem calculates the area of a polygon easily]

In the late 1800s, the Austrian Jewish mathematician Georg Alexander Pick had a problem. He wanted to calculate the areas of complicated polygons but his iPad was broken so he needed a relatively easy way to calculate polygon areas manually. Okay, he obviously didn't have an iPad and, for all I know, he didn't need to find the areas of many polygons. Nevertheless he came up with the following amazing result for polygons on a lattice.

Area = i + b / 2 - 1

Where:

i is the number of lattice points that are inside the polygon
b is the number of lattice points that are on the polygon's boundary

To calculate the area of a polygon in the "normal" way, you would break it into triangles, trapezoids, or some other simple shape and combine their areas. TO use Pick's Theorem, you just count the lattice points inside and on the polygon and use the formula.

For example, the polygon in the picture at the top of this post has 122 internal points and 11 boundary points so its area is 122 + 11 / 2 - 1 = 126.5. If you look closely at the picture, you'll see that the area calculated with Pick's Theorem agrees with the area calculated in the "normal" way using trapezoids.

This post brings together techniques explained in the following posts:

To use the program, left-click to define the polygon's vertices and then right-click to close the polygon. While you're doing that, the program uses the techniques in example 3 to snap the polygon's vertices to the lattice.

When you close the polygon, the program uses example 2 to see which lattice points are inside or outside of the polygon. It uses example 1 to see which lattice points lie on the polygon's edges.

The program then calculates and displays the area according to Pick's Theorem. It also uses example 4 to calculate the area using trapezoids and posts that.

Processing Polygons

You can download the example and look at the examples listed above to figure out most of this. I just want to go over a couple of the more interesting pieces.

First, the program calls the following process_polygon method when you finish drawing a polygon.

def process_polygon(self): '''Process the new points to make a polygon and verify the theorem.''' # Delete everything. self.canvas.delete(tk.ALL) # Draw the grid. num_interior_points, num_boundary_points = self.draw_grid_points() set_entry(self.interior_entry, num_interior_points) set_entry(self.boundary_entry, num_boundary_points) picks_area = num_interior_points + num_boundary_points / 2 - 1 set_entry(self.pick_entry, picks_area) # Draw the polygon. self.canvas.create_polygon(self.new_points, outline='blue', fill='') # Convert the points into lattice points. points = [( round(point[0] / self.col_wid), round(point[1] / self.row_hgt)) for point in self.new_points] # Calculate the polygon's area. area = polygon_area(points) # Display the results. set_entry(self.calculated_entry, area)

This method clears the drawing canvas and then calls self.draw_grid_points (described shortly) to draw the lattice. In addition to drawing the lattice, that method also counts the points that lie inside the polygon and on its borders.

The code then displays those values, calculates the area according to Pick's Theorem, and displays that value, too.

Next, the code draws the polygon. It then converts the polygon points that you clicked into lattice points. The polygon's vertices are where you clicked, recorded in pixels. The code divides the X and Y coordinates by the size of the lattice points. As it is written the example spaces the lattice points 20 pixels apart so, for example, the canvas point (100, 60) corresponds to lattice point (5, 3).

Technically the pixels also form a lattice, just with their points very close together. You could apply Pick's Theorem to the pixels, but that's a lot less intuitive. It would also be hard to count the pixels inside the polygon and on its edges manually so that wouldn't have helped Pick much.

Having converted the polygon points to lattice points, the code calculates the polygon's area in lattice space and displays the result.

Drawing the Grid

The following code shows the draw_grid_points method, which draws the lattice.

def draw_grid_points(self): '''Draw the grid points.''' # Count the nuber of interior points. num_interior_points = 0 num_boundary_points = 0 self.canvas.update() wid = self.canvas.winfo_width() hgt = self.canvas.winfo_height() for y in range(0, hgt, self.row_hgt): for x in range(0, wid, self.col_wid): pt = (x, y) # See if the point is inside or on the polygon. if self.new_points is None: point_location = 'E' else: point_location = test_point(self.new_points, pt) # Draw the point accordingly. if point_location == 'E': color = 'black' r = 0.5 elif point_location == 'B': color = 'green' r = 3 num_boundary_points += 1 elif point_location == 'I': color = 'pink' r = 3 num_interior_points += 1 self.canvas.create_oval(x-r, y-r, x+r, y+r, fill=color, outline=color) return num_interior_points, num_boundary_points

This method gets the canvas's width and height and then loops over its surface, incrementing the X and Y coordinate by the lattice's column width and row height at each step.

For each point, the code first checks whether we have a polygon. If self.new_points is None, there is no polygon yet so the code sets point_location to E to indicate that the point is external to the none-existent polygon. If we do have a polygon, the code calls test_point (described later) to see if the point is inside, outside, or on the border of the polygon.

Having classified the point, the method draws it accordingly. It draws exterior points as small black dots, boundary points as large green dots, and interior points as large pink dots.

Classifying Points

The following code shows the test_point function.

def test_point(points, pt): '''See if pt is inside the polygon or on the polygon's boundary.''' # Return B (boundary), I (interior), or E (exterior). # See if it's on the boundary. num_points = len(points) for i in range(num_points): j = (i + 1) % num_points closest, distance = find_distance_to_segment(pt, points[i], points[j]) if math.isclose(distance, 0, abs_tol=0.001): return 'B' # See if it is inside the polygon. if point_in_polygon(points, pt): return 'I' return 'E'

This code first loops through the polygon's edges and calls find_distance_to_segment to see how far the lattice point is from that segment. If the distance is smaller than 0.001 pixels, the function assumes the point is on the edge and hence on the polygon's boundary so it returns B.

If the point is not on any of the polygon's edges, the function calls point_in_polygon to see if the point lies inside the polygon, in which case the function returns I.

If the point is not on the polygon's boundary and isn't inside the polygon, the function returns E to indicate it is external to the polygon.

Conclusion

Most of this example's harder calculations are described in the examples mentioned earlier, this example just puts them together so it can apply Pick's Theorem.

I think the theorem is pretty amazing. It lets you find the areas of some pretty complicated polygons relatively easily. For example, it would take some careful work to use the theorem to find the areas of the polygons shown below, but it would be a lot easier than dividing those polygons into triangles or trapezoids.

[Pick's Theorem can calculate the area of complex polygons]

[For self-intersecting shapes, Pick's Theorem is right but the verification method is wrong]

There is one caveat about drawing polygons: don't draw self-intersecting shapes. If you do, Pick's Theorem calculates the area correctly but the other code that uses the earlier example's techniques to verify the area does not. That technique counts some of the areas inside the polygon multiple times so its result is wrong. If you look closely at the picture on the right, you'll see that Pick's Theorem says the polygon's area is 141 square units but the verification method says it's 177 square units.

Download the example to experiment with it and to see additional details.