Pick's theorem and youthful loves

I am a faithful husband.
But there are some old loves that every now and then come back to stimulate and fill my mind, making me live again those emotions that i felt when i used to date them. And so, here i am to savour, once again with renewed strength, those pleasures i was granted of, almost like in the candour of a teen-age flirt.
One of those loves is Mathematics. ;-)

It's thanks to Giovanna and her blog Matematicamedie that i found something of this matter still unknown to me. Infact, i have never heard before about Pick's theorem.
As the teacher Giovanna well explains om her very interesting post, that tells about a wonderful work her class made, Pick's theorem computes in an easy and concise way the area of a polygon built under some particular rules.

To clarify better the problem, let me try with some definitions.

Given a regular grid of points (that we can imagine as the crossings of the lines on a squared paper), a "Pick's segment" is a segment that join two points of the grid without intersecting any other on its path. If we need a segment that lays on an extra point, it is considered like the concatenation of two consecutive segments lying on the same line.
A "Pick's polygon" is a closed concatenation of Pick's segments not self-intersecting.
It's right the area of Pick's polygon that is evaluated by Pick's theorem.

Please note that the non-self-intersection condition is demanded for any area computation.

figure 1

It doesn't make much sense infact to evaluate the area of a self-intersecting polygon.
Moreover the condition for which a segment doesn't have to contain any other point of the grid more than its extrema, doesn't reduce the representation power of the definition. If a polygon has a side cut by a point of the grid, well, in that point one can also consider an additional vertex that generate a straight angle. For example figure 1 shows a Pick's polygon with four vertex and four sides, in different colors, even if it is perfectly superimposable on a triangle.
As Giovanna reveals, Pick's theorem asserts that area A of a Pick's polygon is given by the formula

A = PI + PC/2 -1

dove PI is the number of the "internal" points (or the points of the regular grid that fall in teh internal part of the polygon) and PC is the number of the "contour" points: the ones that fall on the vertices of the Pick's segments - sides of the polygon, or, in other words, the points that lay on the edge.
Clearly this formula is valid if the obtained value is then multiplied by the area of the square that defines the regular grid. To make it more simple, on this post, i consider a grid in which the area of the square is one.
With reference to figure 1, for example, PI is the number of the points painted in blue (7), PC the ones in yellow (4), so the area of the polygon is
A = 7 + 4/2 - 1 = 8
It works. Try and see!

In a comment of the discussion that follows the quoted blog, Giovanna suggests me a couple of links to web pages where there is also the "official" demostration of Pick's theorem. Nevertheless i didn't follow those links, nor i have any intention to do it before submitting this post, because what enchants me of mathematics is not so much the result itself, even when in cases like this the formula has a really charming elegance. And not even i need a concrete proof to believe in the truth of the formula: i trust in Giovanna!
No, what i find irresistible is to use mathematics in order to find a demonstration my own.
Naturally this task is simplified by the fact that i already know which is the result i have to reach and i am already convinced that that result is true. So, i have only to find a right path to reach the goal (without a GPS navigator system ;-)).

Trying to wear the pants of an eventual reader that doesn't know Pick's theorem, i warn now that the rest of this post shows my own demonstration and so, if one is interested to find another one, this is a good point to stop reading.

So...

First of all i find the way to count the internal points in the polygon, the geometrical informations on the vertices given.
I start defining a Cartesian axis system centered in any point of the grid lower and more on the left of the whole polygon (i believe that these last conditions are irrelevant, but, since i can choose, i simplify my own life!).

figure 2

I concentrate now to find an easy way to express the number of the points that are "under" a Pick's segment. With the word "under" i mean that their ordinates are greater or equal to zero and lower than the intersection point between the vertical line and the segment, and, moreover, their abscissa falls between or equal to the abscissae of the segment extrema. In the example shown in figure 2 that is the number of the points painted in yellow.

figure 3

In order to do so, i consider the figure obtained by all the points that are "under" the segment plus all the ones that i obtain rotating the figure of a 180deg angle around the center of the segment. These points are disposed as a rectangle that i name R (an example is given in figure 3).
The number of points belonging to this rectangle si clearly given by the number of points at the base multipled by the number of point in the height.
Naming P1 and P2 the extrema of the segment, and (x1, y1) and (x2, y2) their coordinates, respectively, the computation of the number of points in the rectangle is given by this following formula:
R = (x2 - x1 +1) * (y2 + y1 + 1)

The comuted value R is an even number.

figure 4

Infact, as it is shown in figure 4, R can be divided in three rectangles, marked by colors red, green and blue. Clearly the red and blue rectangles are equal, and so they contain the same number of points. The sum of all those points, so, is even. To show that R is even, then, it is enough to show that the nubmer of points in the green rectangle is also even.
Numbers dx = x2 - x1 and dy = y2 - y1 are prime between each other. Infact if it was not like that, segment between tra P1 and P2 would meet other points of the grid. So, the segment wouldn't match the definition which a point of the grid cannot belong to a Pick's segment, unless one of its extrema. Since dx and dy are prime each other, atleast one of them is an odd number (if both were even, they would have 2 as a common divisor). So, atleast one value between dx+1 and dy+1 is even. It follows that their product is necessarily even, and incidentally that product is right the number of points of the green rectangle. So, R &is even.
Number R can be divided by 2, and the result of that division is given by the number of point "under" the segment plus one. Infact for construction the number of points belonging to R that are "upon" the segment is the same as the number of the ones that are "under", and equal to the half of R subtracted by the ones that are right "on" the segment (the 2 extrema).

figure 5

I am interested now to find the number of points that are under the segment except the last column (as shown, in figure 5, by the points marked in green). This number, that i name Q, is clearly given by
Q = (R-2)/2 - y2
since y2 is the number of points of the last column, and so
Q = (x2 - x1 +1) * (y2 + y1 + 1) / 2 - 1 - y2

figure 6

It easy to verify that this formula is valid also if point P1 lies in a position higher than point P2 or if they are at the same height (that is y1 = y2).
In case P1 lies at the right of P2 (that is x1 > x2), the formula is still valid, except for the result that changed its sign and that also the involved extrema is counted. This result is shown in figure 6.
In this case, infact, the base of the rectangle R is the projection of the segment excluding the extrema, sign-inverted. The formula to count the points
R = (x2 - x1 +1) * (y2 + y1 + 1)
represents so the inverse of the number of points in that rectangle. Note that the area is 0 if x1 = x2 + 1. The first part of the formula Q, (x2 - x1 +1) * (y2 + y1 + 1) / 2, denotes the number of points that are under the segment, excluding the first and the last column, as shown by the points marked in green in figure 6.

figure 7

The second part of the formula Q, -1 -y2, instead, clearly denotes the left column of the points under the segment sign-inverted, counting, this time, also point P2 itself, as shown by the blue points in figure 6. The algebric sum of the two parts, given by gormula Q
Q = (x2 - x1 +1) * (y2 + y1 + 1) / 2 - 1 - y2
then denotes the number of points that are "under" the segment, excluding the rightmost column and counting also the left extrema, the all inverted of sign.

Formula Q is useful to compute, in a concatenation of segments, the number of points that are "under" for the ones that go from left to right, but in the same time "upon" the ones that run right to left. Figure 7 shows the concatenation of two segments left to right: the number of points under the red segment are summed to the number of points under the blue one.

figure 8-1 figure 8-2 figure 8-3

In figures 8-1, 8-2, 8-3 is shown the procedure to algebrically sum the points of two consecutive segments, one left-to-right and the other right-to-left. In 8-1 are shown in red the points for the red segment, positive, in 8-2 in blue the ones for the blue segment, in 8-3 their algebric sum.

figure 9-1 figure 9-2 figure 9-3 figure 9-4 figure 9-5 figure 9-6

In figure 9-1 to 9-6 sequence it is shown the iteration for segments from P1-P2 to P6-P1 (closing the path).
Figures 9-1 and 9-2 show how to sum the contributions of two segments left-to-right, figure 9-3 shows the subtraction of points from the amount obtained in the previous step. In blue it's shown the "negative" points, that is the ones that are subtracted in excess. Those points undo some of the positive ones at point 9-4. In 9-5 and 9-6 are then subtracted the points of the last two, both right-to-left, segments.
The value obtained by the iteration is the number of the polygon's internal points, except two points that are subtracted in excess (extrema P1 and P4), and one that is summed in excess (P3). Considering the reasons for this happening, the conclusion is that the exceeding summed points are the vertices that form "left concavities" (the ones that form a concavity between a right-to-left segment and the next left-to-right one) and, vice-versa, the exceeded subtracted points are the vertices that form "left convexities" (the ones that form a convexity from the previous right-to-left segment and the next left-to-right one).
It's easy to show that, going along the polygon clockwise, the total number of left-concavity vertices is equal to the number of left-convexity vertices minus one, infact, for each "change of direction", sooner or later there must be another change of direction in the opposite way. So, to compute the exact number of points internal to the polygon, if N is the number of left-convexities, we must sum N and subtract N-1, or, in other words, subtract 1.

Considering again the formula for Q, and generalizing on the indices of the points:
Qi = (xi+1 - xi +1) * (yi+1 + yi + 1) / 2 - 1 - yi+1
This is valid for all the n segments of the polygon, varying i on values 1, 2, ..., n. Index n+1 identifies point P1, so that the last segment is the one that join Pn to P1.
Modifying a little this formula, multiplying and collecting:
Qi = (xi+1 - xi) * (yi+1 + yi) / 2 + (xi+1 - xi + yi+1 + yi + 1)/2 - 1 - yi+1
obtaining, then
Qi = (xi+1 - xi) * (yi+1 + yi) / 2 + (xi+1 - xi -yi+1 + yi - 1)/2
I can cut this formula, naming
Ai = (xi+1 - xi) * (yi+1 + yi) / 2
Bi = (xi+1 - xi -yi+1 + yi - 1)/2
and so
Qi = Ai + Bi

The number of polygon's internal points is than given by
PI = (Σi = 1..nQi) +1 = [Σi = 1..n(Ai + Bi)] +1
or:
PI = (Σi = 1..nAi) + (Σi = 1..nBi) +1

Said
A = Σi = 1..nAi
B = Σi = 1..nBi
the conclusion is that
PI = A + B + 1

The portion B can be simplified. Infact
B = Σi = 1..nBi = Σi = 1..n[(xi+1 - xi -yi+1 + yi - 1)/2]
or, in other words
B = [(x2-x1-y2+y1-1) + (x3-x2-y3+y2-1) + ... + (xn-xn-1-yn+yn-1-1) + (x1-xn-y1+yn-1)]/2
Observing the formula written in this way, we note that all the terms xi and yi are canceled each other, and what remains is -1 summed n times, where n is the number of the Pick's polygon sides, which is clearly equal to the number of the points that lie on the edge of the polygon. So
B = -PC/2
and so
PI = A - PC/2 + 1

Now i try to compute the area of the Pick's polygon.

figure 10

In a similar way as above, i consider the Pick's polygon segment by segment. Every segment, if covered left-to right, gives a positive contribution given by the area of the trapezoid formed by the segment itself and its projection on the x-axis, as shown in figure 10. The are of the trapezoid is givne by the sum of the bases (y1 + y2) multiplied by the height (x2 - x1) divided by 2.
Generalizing, then
Ai = (xi+1 - xi) * (yi+1 + yi) / 2

This formula is valid also for the segment that are covered right-to-left, except for the fact that the obtained area is negative, since the height (xi+1 - xi) is negative. The algebric sum of the contribution of all the segment, any verse covered, generates the area of the polygon, as shown in the sequence of figures 11-1 to 11-6.

figure 11-1 figure 11-2 figure 11-3 figure 11-4 figure 11-5 figure 11-6

At any step of the sequence the portion Ai relative to the considered segment, is algebrically summed. In figure 11-3 it is marked in blue the portion that is subtracted in excess, and that is then recovered by the positive area summed at step 11-4.
Summation
Σi=1..n Ai
That computes the area of the polygon, is exactly the portion A of the formula obtained above
PI = A - PC/2 + 1

From this previos we obtain then

A = PI + PC/2 - 1

which is the thesis of Pick's theorem itself.
When i was a student, at this point, one concludes the exercise, enjoying the moment of suffered glory, with the achronym

CVD
("come volevasi dimostrare" = "as one wanted to demonstrate")