How many integer points within the three points forming a triangle?

Question

Actually this is a classic problem as SO user Victor put it (in another SO question regarding which tasks to ask during an interview).

I couldn't do it in an hour (sigh) so what is the algorithm that calculates the number of integer points within a triangle?

EDIT: Assume that the vertices are at integer coordinates. (otherwise it becomes a problem of finding all points within the triangle and then subtracting all the floating points to be left with only the integer points; a less elegant problem).

Answer 1

Assuming the vertices are at integer coordinates, you can get the answer by constructing a rectangle around the triangle as explained in Kyle Schultz's An Investigation of Pick's Theorem.

For a j x k rectangle, the number of interior points is

I = (j – 1)(k – 1). 

For the 5 x 3 rectangle below, there are 8 interior points.

_{(source: uga.edu)}

For triangles with a vertical leg (j) and a horizontal leg (k) the number of interior points is given by

I = ((j – 1)(k – 1) - h) / 2 

where h is the number of points interior to the rectangle that are coincident to the hypotenuse of the triangles (not the length).

_{(source: uga.edu)}

For triangles with a vertical side or a horizontal side, the number of interior points (I) is given by

_{(source: uga.edu)}

where j, k, h1, h2, and b are marked in the following diagram

_{(source: uga.edu)}

Finally, the case of triangles with no vertical or horizontal sides can be split into two sub-cases, one where the area surrounding the triangle forms three triangles, and one where the surrounding area forms three triangles and a rectangle (see the diagrams below).

The number of interior points (I) in the first sub-case is given by

_{(source: uga.edu)}

where all the variables are marked in the following diagram

_{(source: uga.edu)}

The number of interior points (I) in the second sub-case is given by

_{(source: uga.edu)}

where all the variables are marked in the following diagram

_{(source: uga.edu)}

Answer 2

Pick's theorem (http://en.wikipedia.org/wiki/Pick%27s_theorem) states that the surface of a simple polygon placed on integer points is given by:

A = i + b/2 - 1 

Here A is the surface of the triangle, i is the number of interior points and b is the number of boundary points. The number of boundary points b can be calculated easily by summing the greatest common divisor of the slopes of each line:

b =   gcd(abs(p0x - p1x), abs(p0y - p1y))      + gcd(abs(p1x - p2x), abs(p1y - p2y))      + gcd(abs(p2x - p0x), abs(p2y - p0y)) 

The surface can also be calculated. For a formula which calculates the surface see https://stackoverflow.com/a/14382692/2491535 . Combining these known values i can be calculated by:

i = A + 1 - b/2