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
P
1-P
2
to P
6-P
1
(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")
