How to calculate the integer number of vertices in a 2 dimensional triangle?

Question

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

Answer 1

I think I have found the solution to this. I will present it as a short c program. It makes use of a call to gcd (greatest common denominator), which I got from here: https://en.wikipedia.org/wiki/Binary_GCD_algorithm

long latticePointsInTriangle(double base, double height) {
  long intBase = floor(base);
  long intHeight = floor(height);
  long gcdValue = gcd(intHeight, intBase);
  long numBoundryLatticePoints = intBase+1 + intHeight + (gcdValue - 1);
  double area = double(intBase) * double(intHeight) / 2;
  long numInternalLatticePoints = floor(area - numBoundryLatticePoints/2 + 1);
  return numBoundryLatticePoints + numInternalLatticePoints;
}

I appreciate the help from Somas and poetasis!

EDIT: Let me qualify this solution. The first thing the algorithm does is reduce the base and height to integers and this effectively shrinks the triangle. For some inputs, this gives a correct answer. But I found an example (base = 140/19, height = 140/7) where this causes lost solutions, and a count that is too small. According to this post: Counting integral lattice points in a triangle that may not have integer coordinates? it looks like there is not a simple formula to calculate non-integer inputs other then cyclic addition.

UPDATE:
I have been thinking about how to compensate for lost vertices when shrinking from a triangle with real (non-integer) lengths down to integer lengths as per my posted solution above. Consider the following image. It has to be large to show the subtle details:

The red line is the hypotenuse of the originating triangle with non-integer dimensions. The blue line is the new hypotenuse after collapsing it to integer dimensions, so that Pick's Theorem can be used. The black circles are highlighting all vertices that are lost when counting JUST with Pick Theorem. The correct count would need to be expanded by this amount.

So how to efficiently code for these? The next image shows the next step towards a generalization

So finally, I have the following image:

Here is appears that the number of "lost" lattice points can themselves be calculated with a triangle area formula.

Things I am not sure of:

• How does the floor() function impact the hypotenuse of this triangle? Is it a straight line? The points in this graph were calculated. I will later try a bigger data set and calculate a delta value between each and see if there is variance.
• It would be nice if I could prove if this approach will work for all inputs.
• I need to put this into a final algorithm to update my one posted above.

UPDATE

• I have done more calculation and experimentation with larger data sets. I will say that the graphing of the lost lattice points does NOT reliably form a straight hypotenuse.

Answer 2

Given $(a,b)$ as lengths of two sides of triangle, we can calculate number of lattice points in it ($n$) as follows:

1. Calculate slope: $m=\frac b a$
2. Calculate number of points of one of the two sides by adding $1$ to the length:
   $$c=b+1$$
3. Use the following formula:
   $$n=\sum^{a}_{k=0} \lfloor c-|km| \rfloor$$

Note that: we used the absolute value for $km$ because slope can be a negative number, and the floor function to get rid of decimal part.

We can summarize these steps in the following formula using $(a,b)$ only:

$$n=\sum^{a}_{k=0} \lfloor b+1-|k \left( \frac b a \right)| \rfloor$$