Calculating the area of a zone bounded by points of known integer coordinates

Question

Firstly, please take a look at this picture:

Consider that the squares represent cartesian points and the asterisk marks the (0, 0) point.

In the picture, the given points are (in trigonometical order and marked with a '-' in the image): (0, 0); (0, 1); (0, 2); (-1, 2); (-2, 2); (-2, 1); (-3, 1); (-3, 0); (-3, -1); (-2, -1); (-2, -2); (-1, -2); (0, -2); (1, -2); (1, -1); (1, 0).

Given (just!) the points from above, how can I determine the area of the gray squares (5 in the posted picture)? ("the number of points of integer coordinates who are inside the polygon determined by the already specified points")

I want to implement something like this in C++. This is why I posted the question on StackOverflow. But once someone explains me how (geometrical approach or anything), I hope I will be able to implement it by myself.

Any help is much much appreciated! Thank you very much!

Answer 1

You can use well-known algorithm for area of polygon, defined by vertices in order.

A = Abs(1/2*Sum(X(i)*Y(i+1)-X(i+1)*Y(i)))

Then use Pick theorem to find the number of points with integer coordinates inside the contour:

i=A-b/2+1

where A is area, b is number of border points.

for this example

i=12-16/2+1=5

Answer 2

The area of the gray squares is 5 times the area of one square.

Answer 3

Try to calculate area layer by layer. First determine the bottom most layer's interval and check whether the gray area is reside in the layer. if so, then change the interval so it wont include the gray area. For example (-3,-2) (-2, -2) (-2, -3) (-1, -3) (0, -3) (0,-2) (1, -2) then the interval would be (-3, -2) U (0, 1). I hope this will help you. sorry for the bad english