How many integer points within the three points fo

问题:

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).

回答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.

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image008.jpg

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).

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image012.jpg

For triangles with a vertical side or a horizontal side, the number of interior points (I) is given by

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula5.jpg

where j, k, h1, h2, and b are marked in the following diagram

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Triangle3.jpg

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

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula7.jpg

where all the variables are marked in the following diagram

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/triangle5.jpg

The number of interior points (I) in the second sub-case is given by

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image042.png

where all the variables are marked in the following diagram

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image038.png

回答2:

Pick's theorem (http://en.wikipedia.org/wiki/Pick%27s_theorem) states that the surface of a simple polygon placed on integer points is given by:

A = i + b/2 - 1

Here A is the surface of the triangle, i is the number of interior points and b is the number of boundary points. The number of boundary points b can be calculated easily by summing the greatest common divisor of the slopes of each line:

b =   gcd(abs(p0x - p1x), abs(p0y - p1y)) 
    + gcd(abs(p1x - p2x), abs(p1y - p2y)) 
    + gcd(abs(p2x - p0x), abs(p2y - p0y))

The surface can also be calculated. For a formula which calculates the surface see https://stackoverflow.com/a/14382692/2491535 . Combining these known values i can be calculated by:

i = A + 1 - b/2

回答3:

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.

回答4:

This is called the "Point in the Triangle" test.

Here is an article with several solutions to this problem: Point in the Triangle Test.

A common way to check if a point is in a triangle is to find the vectors connecting the point to each of the triangle's three vertices and sum the angles between those vectors. If the sum of the angles is 2*pi (360-degrees) then the point is inside the triangle, otherwise it is not.

回答5:

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:

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

2. 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))

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

4. 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.

回答6:

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.

回答7:

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.

回答8:

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

回答9:

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

回答10:

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 ?)

回答11:

(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

回答12:

I found a quite useful link which clearly explains the solution to this problem. I am weak in coordinate geometry so I used this solution and coded it in Java which works (at least for the test cases I tried..)

http://mathforum.org/library/drmath/view/55169.html

public int points(int[][] vertices){
      int interiorPoints = 0;
      double triangleArea = 0;
      int x1 = vertices[0][0], x2 = vertices[1][0], x3 = vertices[2][0];
      int y1 = vertices[0][1], y2 = vertices[1][1], y3 = vertices[2][1];

      triangleArea = Math.abs(((x1-x2)*(y1+y2))                             
                + ((x2-x3)*(y2+y3))
                + ((x3-x1)*(y3+y1)));

      triangleArea /=2;
      triangleArea++;

      interiorPoints = Math.abs(gcd(x1-x2,y1-y2))
                + Math.abs(gcd(x2-x3, y2-y3))
                + Math.abs(gcd(x3-x1, y3-y1));

      interiorPoints /=2;

      return  (int)(triangleArea - interiorPoints);
 }

回答13:

Here is a Python implementation of @Prabhala's solution:

from collections import namedtuple
from fractions import gcd


def get_points(vertices):
    Point = namedtuple('Point', 'x,y')
    vertices = [Point(x, y) for x, y in vertices]

    a, b, c = vertices

    triangle_area = abs((a.x - b.x) * (a.y + b.y) + (b.x - c.x) * (b.y + c.y) + (c.x - a.x) * (c.y + a.y))
    triangle_area /= 2
    triangle_area += 1

    interior = abs(gcd(a.x - b.x, a.y - b.y)) + abs(gcd(b.x - c.x, b.y - c.y)) + abs(gcd(c.x - a.x, c.y - a.y))
    interior /= 2

    return triangle_area - interior

Usage:

print(get_points([(-1, -1), (1, 0), (0, 1)]))  # 1
print(get_points([[2, 3], [6, 9], [10, 160]]))  # 289