6
$\begingroup$

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.

enter image description here

And another similar image (#2), this time with triangle area being 7 square units, and containing 13 lattice points:

enter image description here

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.

enter image description here

But image #2, from above, has a slope of -2/7 and NO lattice points on the hypotenuse.

enter image description here

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
$\endgroup$
  • 2
    $\begingroup$ You should read Wikipedia Ehrhart polynomial. $\endgroup$ – Somos Apr 21 at 17:17
  • $\begingroup$ This looks like what I was looking for. Had not learned of these before... Studying now. $\endgroup$ – kdtop Apr 21 at 17:28
  • $\begingroup$ What could you do with Pythagorean triples like $27,36,45$ which is a $9 times$ multiple of $3,4,5$? $\endgroup$ – poetasis Apr 21 at 18:42
  • $\begingroup$ @poetasis I'm sure I'm dense, and I know you are trying to help me think of something, but I can't figure out what it is. I'll keep thinking about it. $\endgroup$ – kdtop Apr 21 at 19:00
  • 1
    $\begingroup$ @kdtop It's just a thought about using multiples of Pythagorean triples. I don't know how to calculate vertices but $these$ would seemingly have a predictable larger number of additional vertices because all the dimensions are divisible by integers. $\endgroup$ – poetasis Apr 21 at 19:07
2
$\begingroup$

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:

enter image description here

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

enter image description here

So finally, I have the following image:

enter image description here

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.
$\endgroup$
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ @anas_pcpro Thank you for taking the time to put together this reply. However, I am not going to mark this as an accepted answer because it uses cyclic addition, which is programatically slow, and I put in the original question that I already knew how to do that. I think the fastest way is going to be to use Pick's Theorem to find the area of a smaller triangle, shrunk to integer lattice points, and then use a cyclic process (which should be overall shorter) to pick up the points that fall outside the smaller bound. I do appreciate your post! $\endgroup$ – kdtop Jun 3 at 16:39
  • $\begingroup$ @kdtop, Thank you so much for your reply, I know what you are talking about and wanted to introduce other ways for solving not to get my answer accepted, for me it doesn't matter at all ! $\endgroup$ – anas pcpro Jun 3 at 18:30
  • $\begingroup$ @anas_pcpro Thanks! $\endgroup$ – kdtop Jun 3 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.