How to use the selection theorem for any given triangle

Question

So, I want to calculate the number of points in any given triangle. I know that I need to use Pick Theor, but my code ends up with a rather ridiculously long if-else if volume to check for every case. I used this as a guide. How many integer points are the three points that make up the triangle? but then end up with this (the vertices are an array of 3 arrays. Each array is the (x, y) coordinates of the triangle's vertex):

int maxX = Math.max(Math.max(vertices[0][0], vertices[1][0]), vertices[2][0]), minX = Math.min(Math.min(vertices[0][0], vertices[1][0]), vertices[2][0]), maxY = Math.max(Math.max(vertices[0][1], vertices[1][1]), vertices[2][1]), minY = Math.min(Math.min(vertices[0][1], vertices[1][1]), vertices[2][1]); int height = Math.abs(maxY - minY), width = Math.abs(maxX - minX); double area = Math.abs(((vertices[0][0] * (vertices[1][1] - vertices[2][1] )) + (vertices[1][0] * (vertices[2][1] - vertices[0][1])) + vertices[2][0] * (vertices[0][1] - vertices[1][1])) / 2); if ((vertices[0][0] == vertices[1][0]) && (vertices[0][1] == vertices[2][1])) { area = ((Math.abs(vertices[0][1] - vertices[1][1]) - 1) * (Math.abs(vertices[0][0] - vertices[2][0]) - 1)) / 2; } else if ((vertices[0][0] == vertices[2][0]) && (vertices[0][1] == vertices[1][1])) { area = ((Math.abs(vertices[0][1] - vertices[2][1]) - 1) * (Math.abs(vertices[0][0] - vertices[1][0]) - 1)) / 2; } else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1])) { area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) * (Math.abs(vertices[1][0] - vertices[0][0]) - 1)) / 2; } else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1])) { area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) * (Math.abs(vertices[1][0] - vertices[0][0]) - 1)) / 2; } else if(vertices[0][0] == vertices[1][0]) { int b = Math.abs(vertices[0][1] - vertices[1][1]); /*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2)), dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2));*/ if (vertices[0][1] > vertices[1][1]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1) /*- dist2*/) / 2); } else if (vertices[0][1] < vertices[1][1]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist1*/) / 2); } } else if(vertices[0][0] == vertices[2][0]) { int b = Math.abs(vertices[0][1] - vertices[2][1]); /*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + Math.pow(vertices[0][1] - vertices[1][1], 2)), dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) + Math.pow(vertices[2][1] - vertices[1][1], 2));*/ if (vertices[0][1] > vertices[2][1]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1) /*- dist2*/) / 2); } else if (vertices[0][1] < vertices[2][1]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist1*/) / 2); } } else if(vertices[1][0] == vertices[2][0]) { int b = Math.abs(vertices[1][1] - vertices[2][1]); /*double dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) + Math.pow(vertices[1][1] - vertices[0][1], 2)), dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) + Math.pow(vertices[2][1] - vertices[0][1], 2));*/ if (vertices[1][1] > vertices[2][1]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1) /*- dist2*/) / 2); } else if (vertices[1][1] < vertices[2][1]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist1*/) / 2); } } else if(vertices[0][1] == vertices[1][1]) { int b = Math.abs(vertices[0][0] - vertices[1][0]); /*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2)), dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2));*/ if (vertices[0][0] > vertices[1][0]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1) /*- dist2*/) / 2); } else if (vertices[0][0] < vertices[1][0]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist1*/) / 2); } } else if(vertices[0][1] == vertices[2][1]) { int b = Math.abs(vertices[0][0] - vertices[2][0]); /*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[1][0], 2) + Math.pow(vertices[0][1] - vertices[1][1], 2)), dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) + Math.pow(vertices[2][1] - vertices[1][1], 2));*/ if (vertices[0][0] > vertices[2][0]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1) /*- dist2*/) / 2); } else if (vertices[0][0] < vertices[2][0]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist1*/) / 2); } } else if(vertices[1][1] == vertices[2][1]) { int b = Math.abs(vertices[1][0] - vertices[2][0]); /*double dist1 = Math.sqrt(Math.pow(vertices[1][1] - vertices[0][0], 2) + Math.pow(vertices[1][1] - vertices[0][1], 2)), dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) + Math.pow(vertices[2][1] - vertices[0][1], 2));*/ if (vertices[1][0] > vertices[2][0]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1) /*- dist2*/) / 2); } else if (vertices[1][0] < vertices[2][0]) { area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist1*/) / 2); } } else if (minX == vertices[0][0]) { int a = 0, b = 0; /*double dist1 = 0, dist2 = 0, dist3 = 0;*/ if(Math.min(vertices[1][0], vertices[2][0]) == vertices[1][0]) { a = width - (vertices[1][0] - vertices[0][0]); b = height - (vertices [1][1] - vertices[0][1]); /*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + Math.pow(vertices[0][1] - vertices[1][1], 2)); dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2)); dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2));*/ } else if(Math.min(vertices[1][0], vertices[2][0]) == vertices[2][0]) { a = width - (vertices[2][0] - vertices[0][0]); b = height - (vertices [2][1] - vertices[0][1]); /*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2)); dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2)); dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + Math.pow(vertices[0][1] - vertices[1][1], 2));*/ } area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1) * (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2); } else if (minX == vertices[1][0]) { int a = 0, b = 0; /*double dist1 = 0, dist2 = 0, dist3 = 0;*/ if(Math.min(vertices[0][0], vertices[2][0]) == vertices[0][0]) { a = width - (vertices[0][0] - vertices[1][0]); b = height - (vertices [0][1] - vertices[1][1]); /*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) + Math.pow(vertices[1][1] - vertices[0][1], 2)); dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2)); dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2));*/ } else if(Math.min(vertices[0][0], vertices[2][0]) == vertices[2][0]) { a = width - (vertices[2][0] - vertices[1][0]); b = height - (vertices [2][1] - vertices[1][1]); /*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2)); dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2)); dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + Math.pow(vertices[0][1] - vertices[1][1], 2));*/ } area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1) * (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2); } else if (minX == vertices[2][0]) { int a = 0, b = 0; /*double dist1 = 0, dist2 = 0, dist3 = 0;*/ if(Math.min(vertices[0][0], vertices[1][0]) == vertices[0][0]) { a = width - (vertices[0][0] - vertices[2][0]); b = height - (vertices [0][1] - vertices[2][1]); /*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) + Math.pow(vertices[2][1] - vertices[0][1], 2)); dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) + Math.pow(vertices[0][1] - vertices[1][1], 2)); dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) + Math.pow(vertices[1][1] - vertices[2][1], 2));*/ } else if(Math.min(vertices[0][0], vertices[1][0]) == vertices[1][0]) { a = width - (vertices[1][0] - vertices[2][0]); b = height - (vertices [1][1] - vertices[2][1]); /*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) + Math.pow(vertices[2][1] - vertices[1][1], 2)); dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2)); dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) + Math.pow(vertices[0][1] - vertices[2][1], 2));*/ } area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1) * (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2); } 

Can someone help me fix the algorithm or give me an easier / better way to do this? This code almost never works.

Sorry for the long code, I didn’t know which parts I should add, so I put the whole algorithm.

Edit: So I changed the algorithm to this ( Thanks to MBo ):

 public static int answer(int[][] vertices) { int a = (Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1] - vertices[0][1]) - (vertices[2][0] - vertices[0][0]) * (vertices[1][1] - vertices[0][1]))) / 2, b = pointsOnLine(vertices[0][0], vertices[0][1], vertices[1][0], vertices[1][1]) + pointsOnLine(vertices[1][0], vertices[1][1], vertices[2][0], vertices[2][1]) + pointsOnLine(vertices[0][0], vertices[0][1], vertices[2][0], vertices[2][1]), area = (2 * a - 2 - b) / 2; // Also tried a + (b / 2) - 1; return (int)area; } public static int pointsOnLine(int x0, int y0, int x1, int y1) { BigInteger b1 = BigInteger.valueOf(Math.abs(x1 - x0)), b2 = BigInteger.valueOf(Math.abs(y1 - y0)); return b1.gcd(b2).intValue(); } 

But I do not always get the right answer. Did I do something wrong?

Answer 1

Selection Theorem :
The number of lattice points inside

i = (2*A + 2 - b)/2

where A is the area of ​​the triangle, b is the number of lattice points at the boundaries Region through the cross product :

 2*A = Abs (V[1].xV[0].x)*(V[2].yV[0].y) - (V[2].xV[0].x)*(V[1].yV[0].y)) 

NumPoints on the border between points (x0, y0) - (x1, y1), including the first point, excluding the last (GCD - Great General Divisor ):

 function PointsOnLine(x0, y0, x1, y1) = GCD(Abs(x2-x1), Abs(y2-y1)) 

for all ribs:

 b = PointsOnLine(V[0].x, V[0].y, V[1].x, V[1].y) + PointsOnLine(V[1].x, V[1].y, V[2].x, V[2].y) + PointsOnLine(V[0].x, V[0].y, V[2].x, V[2].y) 

Now you can get i

Answer 2

Based on @Mbo answer: [EDITED]

 private static long gcd(long n0, long n1) { long a = n0; long b = n1; while (a != 0) { long temp = a; a = b % a; b = temp; } return b; } public static long pointOnLine(long[][] vertices) { return gcd(Math.abs(vertices[0][0] - vertices[1][0]), Math.abs(vertices[0][1] - vertices[1][1])) + gcd(Math.abs(vertices[1][0] - vertices[2][0]), Math.abs(vertices[1][1] - vertices[2][1])) + gcd( Math.abs(vertices[2][0] - vertices[0][0]), Math.abs(vertices[2][1] - vertices[0][1])); } public static long area(long[][] vertices) { return Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1] - vertices[0][1]) - (vertices[2][0] - vertices[0][0]) * (vertices[1][1] - vertices[0][1])); } public static void main(String[] args) { long[][] vertices = {{91207, 89566}, {-88690, -83026}, {67100, 47194}}; //long[][] vertices = {{2,3}, {6,9}, {10,160}}; long i = (area(vertices) + 2 - pointOnLine(vertices)) / 2; System.out.println("points: " + i); }