Imagine a 2-dimensional right triangle drawn on graph paper (a lattice), with the right corner originating at (0,0). Each unit on graph paper has a width of 1 unit. The lengths of the base and height for this triangle can be any real number. Is there a formula for determining the number of lattice points contained in the triangle? By lattice point, I mean where the lines cross on the graph paper, which is where coordinates are integer values. The image (#1) below shows a triangle with area of 2 square units, containing 6 lattice points.
And another similar image (#2), this time with triangle area being 7 square units, and containing 13 lattice points:
QUESTION: Is there a formula to calculate the number of lattice for arbitrary values of base and height?
As a background, I am doing this as a hobby as I try to figure out a computer programming challenge. I have studied up through calculus-1 and calculus-2 in college, but that was many years ago. If more details are desired, let me know.
I realize that this could be solved algorithmically with loops in a computer program. But the real challenge involves the volume of an N-dimensional hyperpyramid, with very large dimensional values, and a requirement to be calculated in < 1 second. So I am hoping for an actual formula.
EDIT: (changed "vertex points" to "lattice points" above, after encountering better terminology).
UPDATE: Studying link from Somos led me to Pick's theorem (https://en.wikipedia.org/wiki/Pick%27s_theorem):
A = i + b/2 - 1 or Area = Number_of_internal_lattice_points + Number_of_boundry_lattice_points/2 - 1
I can calculate total area "A" from the formula for a triangle, using a Floor() function for the dimensions to align with lattice points, required for Pick's theorem. I am looking for (i+b), so I need to next determine b. That would be:
Floor(base_length)+1 + Floor(height_length)+1 + number_of_lattice_points_on_hypotenuse_not_including_end_points
So how to calculate the number of integer lattice points would fall on the hypotenuse?
The image (#3) below has a slope (m) = rise / run = -1/4.
But image #2, from above, has a slope of -2/7 and NO lattice points on the hypotenuse.
But if we were to scale this triangle by factor of 2, we would have a slope of -4/14 and 1 lattice point on the hypotenuse.
So I think the general steps will be:
- Find slope (m) by Floor(height) / Floor(base)
- Find largest integer number N that can reduce slope while still keeping numerator and denominator integers.
- This number N is the number of divided segments of the hypotenuse. The number of lattice points is N-1