Pick's Theorem : The area of a Polygon

This page shows a powerful trick on how to compute the area defined by any polygon with integer vertices.
Namely, the area of such a polygon is :
(number of point inside of it) + (number of points on the frontier) / 2 - 1, this is known as Pick's Theorem.
(The proper statement of the result and a proof sketch are given below).

Theorem: (G. Pick, 1899)

Let `P` be a polygon with integer vertices in `\mathbb{Z}^2` with area `A`. Let `b` be the number of points of `\mathbb{Z}^2` lying on the frontier of the polygon and `i` the number of points lying strictly inside the polygon.
Then, `A` is given by :

`A = i + b/2 - 1.`

Proof sketch :

We consider the function from the set of polygons to `mathbb{Q}`:

`A: P \mapsto i(P) +(b(P))/2 - 1`

where, as above, `i(P)` is the number of points interior to `P` and `b(P)` the number of point on its border.
The idea is to show first that the formula is valid for rectangles, then for triangles, and finally, using the property that any 2D Polygon can be decomposed into a set of triangles, we will obtain Pick's Theorem for the general case.

We consider a `m\times n` integer rectangle `R`.
Its area is given by `mathcal{A} = mn` and `i(R) = (m-1)(n-1)`, `b(R) = 2(m+n)`, we then directly have :

`A(P) = (m-1)(n-1) + (2(m+n))/2 - 1 = mn.`

Thus the formula holds for rectangles.

Next, let us consider a triangle `T` and three corresponding right triangles `U`, `V` and `W` each having as a hypotenuse one of the sides of T. This yields one of the two following cases:


We treat explicitly the first case where the orthogonal sides of `U`, `V` and `W` for a rectangle `R`, the other one is analogous. We know that Pick's formula holds for `U`, `V`, `W` and `R`, thus the area of `T` is:

`A(T) = A(R) - A(U) - A(V) - A(W).`

We have:

`b(R) = b(U) + b(V) + b(W) - b(T)`

and

`i(R) = i(A) + i(B) + i(C) + i(T) + (b(A) + b(B) + b(C) - b(R)) - 3.`

Using these equations we show that Pick's formula holds for `T`.
Any 2D polygon can be split into triangles (see triangulability), the theorem follows.

The hidden algorithms behind this simulation

While working on this simulation, I realized that there are several problems of 2D geometry that arise when studying non-self-intersecting polygons, and that the algorithms used to solve them (polygon generation from points, point-in-polygon algorithm, Ray Tracing, ...) are quite interesting in themselves. I also thought that they deserve their own small developments (if not their own page on this website).

• How to generate a non intersecting polygon from a set of points ?

Given an arbitrary finite set of points `S = (x_i, y_i)_{1\leqi\leqn}` of `\mathbb{R}^2`, we want to build a non self-intersecting polygon `P` which has `S` as the set of its summits. The approach chosen in this simulation is to pick a special point `(x_0, y_0)` of `\mathbb{Z}^2`, which we use as a reference to convert our vertices to polar coordinates.
Here, I chose for this point the barycenter of the polygon, with the above notations for the `n` vertices of `S` :

`x_0 = \frac{1}{n}\sum_{i=1}^n x_i`,     `y_0 = \frac{1}{n}\sum_{i=1}^n y_i.`


We changed from cartesian to polar coordinates: each vertex has the form `(r_i,\phi_i)` with `i\in{1,...,n}`. Then, the points are sorted by their angle `\phi`, and if they have the same angle, we sort them by decreasing radius `r`.
We obtain a sort of 'clockwise' connection of our vertices `S`, which gives (unless it is degenerate) a non self-intersecting polygon.
Finally, we convert the coordinates back to cartesian, while preserving the order of the points, which yields a satisfying polygon, this non self-intersecting polygon is however not unique for a given `S`.


• How to know wether a point is inside, outside or on the frontier of a polygon ?

While counting the number of points inside or on the frontier of a polygon `P` is a very straightforward task for a human being, automating it to illustrate Pick's Theorem is more complex.
The idea is to scan a "window" `W` of `\mathbb{Z}^2` and check wether each point lies on the frontier or inside the polygon. For `W`, we take here the integer points standing between the minimum and maximum coordinates of `P` which yields a rectangular domain.
Then take a point `X_0 = (x_0, y_0)` outside of `W` and for each point `X = (x, y)` of `W`, count how many times the segment `[X_0,X]` intersects the frontier of the polygon. This process of selecting an outer point and tracing segments to detect relative positions of objects is the basis of ray tracing.



• An introduction to Ray Tracing

Ray tracing has become somewhat famous thanks to modern visual rendering techniques in video games, which allow for the creation of stunning images, but of course this comes at an increased cost in terms of computing power. The principle of ray tracing is not new, however, and has been used since the 16th century as a drawing technique. The first use on a computer is more recent and was first accomplished by A. Appel in 1968.



A scene generated using the POV-Ray software


The algorithm proceeds as follow :
- A virtual eye / camera draws a straight ray from its own punctual position into a chosen pixel of a grid acting as a "window" into a virtual scene.
- Once the ray passed through the chosen pixel, if it doesn't meet any object on the other side, the pixel is given the color of the scene background.
- If it meets an object (we first consider a non reflective one) the pixel is given the color of the encountered object.
If the object is reflective, the ray is reflected and continues its path until it meet the background or another object, and the algorithm continues until a given maximum number of reflections is reached.
The color given to the pixel is then a combination of the colors of the objects the ray hit along the way.



Ray casting with one object



It is easy to see that the described algorithm has a quadratic complexity with respect to the number of pixels on the width of the window (for a square grid), multiplied by the maximum number `N` of reflections of the ray, these two factors thus very quickly increase the computation time needed to render an image.

A method to improve the quality of an image without increasing the number of pixels in our ray-casting window is to use of Convolutional Neural Networks (CNN). This definitely requires less 'live calculations', but definitely more pre-computation. This technique is used for instance in video game rendering to provide good image quality without framerate drops.

If you want to get a better understanding of this algorithm and build your very own ray tracing program step by step in Python, I highly recommend this very good competitive exam subject of informatics for the Centrale Schools (in French).

See Also

The concept of integer polygons is related to a whole geometric and algebraic theory (Polytop Theory among others), which provides a whole lot of results dealing with the same kind of problems as the one presented on this page. For instance the Ehrhart theorem is a very nice generalization of Pick's theorem to higher dimension. This course by O. Debarre provides a very clear and concise introduction to Polytope theory, requiring only a very basic knowledge of linear algebra.

Sources :
Images : Morn, CC0, via Wikimedia Commons, Render glass scene; Wikimedia commons, Ray tracing
Autoencoders and ray tracing denoising
A paper on hardware considerations