Counting triangles

I'm going to discuss the analysis of the problem Counting triangles here.

Problem description is very short:

Consider a 2D integer grid with lower left corner at (0, 0) and upper right corner at (X, Y). We are interested in isosceles right triangles which all the 3 corners at the grid node (integer coordinates). Your task is to count the number of those triangles.

There was another problem with the same name: Counting Triangles, in which you have to count all the triangles within a grid having all the three corners in integer coordinate inside the grid. But in this problem you need not to count all of those triangles. You only need to count those triangles which are Isosceles triangle and Right triangle. Now, a triangle can have different shapes and same shaped triangle can have different rotations in the grid. We have to count them all carefully.

For simplicity, lets consider our triangle is OAB, where angle O is right angle, side OA and side OB are equal, so it fulfills both of the conditions above. lets consider the triangle such that, if we rotate OA clockwise in respect of O by 90 degrees then A will be reach to the exactly on the point B. lets consider the coordinate of A, B and O is (x1, y1), (x2, y2) and (x3, y3) respectfully, and also consider O is in the origin, i.e. (0, 0).

Now coordinate of A is (x1, y1) if we rotate it in respect of origin, by rotation matrix of 90 degrees we will get that x2 = y1 and y2 = -x1.

Here is the equation to calculate the coordinate of B form O and A.






You can find the rotation matrix for 90 degrees here.

We know that O (here origin) is an integer coordinate. By the above equation we found that if A is integer coordinate, then B will also be integer coordinate.

So we will brute force for all the integer coordinate for A and calculate the coordinate of B. By all I mean [-X, X] for x coordinate and [-Y, Y] for y coordinate, for other values of x or y, it will definitely occupy a bounding box which is larger than the given 2D grid. So the complexity of this brute force solution is O(X * Y), which is not too big.

In our brute force we will find several triangles OAB, and coordinates of their corner (x3, y3), (x1, y1) and (x2, y2) respectfully. Can you calculate the height and weight of the bounding box of this triangle?

Yes, it's very easy. Height is H = max(y1, y2, y3) - min(y1, y2, y3), and width is W = max(x1, x2, x3) - min(y1, y2, y3).

Now we can place this bounding box in our grid if H ≤ Y and W ≤ X, otherwise it will not fit in our grid and in the same way, our triangle will not fit in the grid. If we can place the bounding box in the grid, we can easily put the lower left corner of the bounding box in (0, 0), so the upper right corner will be (W, H). So, here we found one place where we can place our triangle as well. Can we place the same triangle in another way by shifting our bounding box horizontally or vertically? Yes we sometimes we can. if X is less than W we can shift it horizontally and find another position to place our triangle, in the same way we can shift it vertically if Y is less than H.

In general, for a given bounding box (W, H) we can place it in (X - W + 1) * (Y - H + 1) ways. So this calculation is simply O(1). We will sum up the values for all triangles we calculated by brute-forcing on coordinate A. So our overall complexity of this algorithm is O(X * Y).

Here is my function in java to solve this problem -

long my_solution(int X, int Y){
  if (X == 0 || Y == 0){
      return 0;
  }

  int x3 = 0;
  int y3 = 0;
  long count = 0;
  for (int x1 = -X; x1  <= X; x1 ++) {
      for (int y1 = -Y; y1  <= Y; y1 ++) {
          if (x1 == 0 && y1 == 0) continue;
        
          int x2 = y1;
          int y2 = -x1;
        
          int maxX = Math.max(x1, Math.max(x2, x3));
          int minX = Math.min(x1, Math.min(x2, x3));
          int maxY = Math.max(y1, Math.max(y2, y3));
          int minY = Math.min(y1, Math.min(y2, y3));
        
          int WIDTH = maxX - minX;
          int HEIGHT = maxY - minY;
        
          if (WIDTH > X || HEIGHT > Y) {
              continue;
          }
        
          count += (X - WIDTH + 1) * (Y - HEIGHT + 1);
      }
  }
  return count;
}

Warning:
The result can be big, don't rely on 32 bit integers.