algorithm - 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)}