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

Ok I will propose one algorithm, it won't be brilliant, but it will work.

First, we will need a point in triangle test. I propose to use the "Barycentric Technique" as explained in this excellent post:

http://www.blackpawn.com/texts/pointinpoly/default.html

Now to the algorithm:

i) let (x1,y1) (x2,y2) (x3,y3) be the triangle vertices

ii) let ymin = floor(min(y1,y2,y3)) ymax = ceiling(max(y1,y2,y3)) xmin = floor(min(x1,x2,x3)) ymax = ceiling(max(x1,x2,3))

iii) iterating from xmin to xmax and ymin to ymax you can enumerate all the integer points in the rectangular region that contains the triangle

iv) using the point in triangle test you can test for each point in the enumeration to see if it's on the triangle.

It's simple, I think it can be programmed in less than half hour.

Answer 2

My knee-jerk reaction would be to brute-force it:

• Find the maximum and minimum extent of the triangle in the x and y directions.
• Loop over all combinations of integer points within those extents.
• For each set of points, use one of the standard tests (Same side or Barycentric techniques, for example) to see if the point lies within the triangle. Since this sort of computation is a component of algorithms for detecting intersections between rays/line segments and triangles, you can also check this link for more info.

Answer 3

I only have half an answer for a non-brute-force method. If the vertices were integer, you could reduce it to figuring out how to find how many integer points the edges intersect. With that number and the area of the triangle (Heron's formula), you can use Pick's theorem to find the number of interior integer points.

Edit: for the other half, finding the integer points that intersect the edge, I suspect that it's the greatest common denominator between the x and y difference between the points minus one, or if the distance minus one if one of the x or y differences is zero.

Answer 4

Quick n'dirty pseudocode:

-- Declare triangle
p1 2DPoint = (x1, y1);
p2 2DPoint = (x2, y2);
p3 2DPoint = (x3, y3);
triangle [2DPoint] := [p1, p2, p3];

-- Bounding box
xmin float = min(triangle[][0]);
xmax float = max(triangle[][0]);
ymin float = min(triangle[][1]);
ymax float = max(triangle[][1]);

result [[float]];

-- Points in bounding box might be inside the triangle
for x in xmin .. xmax {
  for y in ymin .. ymax {
    if a line starting in (x, y) and going in any direction crosses one, and only one, of the lines between the points in the triangle, or hits exactly one of the corners of the triangle {
      result[result.count] = (x, y);
    }
  }
}

Answer 5

Hi

I have this idea -

Let A(x1, y1), B(x2, y2) and C(x3, y3) be the vertices of the triangle. Let 'count' be the number of integer points forming the triangle.

If we need the points on the triangle edges then using Euclidean Distance formula http://en.wikipedia.org/wiki/Euclidean_distance, the length of all three sides can be ascertained. The sum of length of all three sides - 3, would give that count.

To find the number of points inside the triangle we need to use a triangle fill algorithm and instead of doing the actual rendering i.e. executing drawpixel(x,y), just go through the loops and keep updating the count as we loop though. A triangle fill algorithm from

Fundamentals of Computer Graphics by Peter Shirley,Michael Ashikhmin

should help. Its referred here http://www.gidforums.com/t-20838.html

cheers

Answer 6

I'd go like this :

Take the uppermost point of the triangle (the one with the highest Y coordinate). There are two "slopes" starting at that point. It's not the general solution, but for easy visualisation, think of one of both "going to the left" (decreasing x coordinates) and the other one "going to the right".

From those two slopes and any given Y coordinate less than the highest point, you should be able to compute the number of integer points that appear within the bounds set by the slopes. Iterating over decreasing Y coordinates, add all those number of points together.

Stop when your decreasing Y coordinates reach the second-highest point of the triangle.

You have now counted all points "above the second-highest point", and you are now left with the problem of "counting all the points within some (much smaller !!!) triangle, of which you know that its upper side parallels the X-axis.

Repeat the same procedure, but now with taking the "leftmost point" instead of the "uppermost", and with proceedding "by increasing x", instead of by "decreasing y".

After that, you are left with the problem of counting all the integer points within a, once again much smaller, triangle, of which you know that its upper side parallels the X-axis, and its left side parallels the Y-axis.

Keep repeating (recurring), until you count no points in the triangle you're left with.

(Have I now made your homework for you ?)

Answer 7

(wierd) pseudo-code for a bit-better-than-brute-force (it should have O(n))
i hope you understand what i mean

n=0
p1,p2,p3 = order points by xcoordinate(p1,p2,p3)
for int i between p1.x and p2.x do
  a = (intersection point of the line p1-p2 and the line with x==i).y 
  b = (intersection point of the line p1-p3 and the line with x==i).y
  n += number of integers between floats (a, b)
end
for i between p2.x+1 and p3.x do
  a = (intersection point of the line p2-p3 and the line with x==i).y 
  b = (intersection point of the line p1-p3 and the line with x==i).y
  n += number of integers between floats (a, b)
end

this algorithm is rather easy to extend for vertices of type float (only needs some round at the "for i.." part, with a special case for p2.x being integer (there, rounded down=rounded up))
and there are some opportunities for optimization in a real implementation

Answer 8

Here's another method, not necessarily the best, but sure to impress any interviewer.

First, call the point with the lowest X co-ord 'L', the point with the highest X co-ord 'R', and the remaining point 'M' (Left, Right, and Middle).

Then, set up two instances of Bresenham's line algorithm. Parameterize one instance to draw from L to R, and the second to draw from L to M. Run the algorithms simultaneously for X = X[L] to X[M]. But instead of drawing any lines or turning on any pixels, count the pixels between the lines.

After stepping from X[L] to X[M], change the parameters of the second Bresenham to draw from M to R, then continue to run the algorithms simultaneously for X = X[M] to X[R].

This is very similar to the solution proposed by Erwin Smout 7 hours ago, but using Bresenham instead of a line-slope formula.

I think that in order to count the columns of pixels, you will need to determine whether M lies above or below the line LR, and of course special cases will arise when two points have the same X or Y co-ordinate. But by the time this comes up, your interviewer will be suitably awed and you can move on to the next question.

-Al.