How to fill a 2D array diagonally based on coordinates

Question

I'm building a heatmap-like rectangular array interface and I want the 'hot' location to be at the top left of the array, and the 'cold' location to be at the bottom right. Therefore, I need an array to be filled diagonally like this:

    0    1    2    3
  |----|----|----|----|
0 | 0  | 2  | 5  | 8  |
  |----|----|----|----|
1 | 1  | 4  | 7  | 10 |
  |----|----|----|----|
2 | 3  | 6  | 9  | 11 |
  |----|----|----|----|

So actually, I need a function f(x,y) such that

f(0,0) = 0
f(2,1) = 7
f(1,2) = 6
f(3,2) = 11

(or, of course, a similar function f(n) where f(7) = 10, f(9) = 6, etc.).

Finally, yes, I know this question is similar to the ones asked here, here and here, but the solutions described there only traverse and don't fill a matrix.

Answer 1

Interesting problem if you are limited to go through the array row by row. I divided the rectangle in three regions. The top left triangle, the bottom right triangle and the rhomboid in the middle.

For the top left triangle the values in the first column (x=0) can be calculated using the common arithmetic series 1 + 2 + 3 + .. + n = n*(n+1)/2. Fields in the that triangle with the same x+y value are in the same diagonal and there value is that sum from the first colum + x.

The same approach works for the bottom right triangle. But instead of x and y, w-x and h-y is used, where w is the width and h the height of rectangle. That value have to be subtracted from the highest value w*h-1 in the array.

There are two cases for the rhomboid in the middle. If the width of rectangle is greater than (or equal to) the height, then the bottom left field of the rectangle is the field with the lowest value in the rhomboid and can be calculated that sum from before for h-1. From there on you can imagine that the rhomboid is a rectangle with a x-value of x+y and a y-value of y from the original rectangle. So calculations of the remaining values in that new rectangle are easy.
In the other case when the height is greater than the width, then the field at x=w-1 and y=0 can be calculated using that arithmetic sum and the rhomboid can be imagined as a rectangle with x-value x and y-value y-(w-x-1).

The code can be optimised by precalculating values for example. I think there also is one formula for all that cases. Maybe i think about it later.

inline static int diagonalvalue(int x, int y, int w, int h) {
    if (h > x+y+1 && w > x+y+1) {
        // top/left triangle
        return ((x+y)*(x+y+1)/2) + x;
    } else if (y+x >= h && y+x >= w) {
        // bottom/right triangle
        return w*h - (((w-x-1)+(h-y-1))*((w-x-1)+(h-y-1)+1)/2) - (w-x-1) - 1;
    }

    // rhomboid in the middle
    if (w >= h) {
        return (h*(h+1)/2) + ((x+y+1)-h)*h - y - 1;
    }
    return (w*(w+1)/2) + ((x+y)-w)*w + x;
}

---

for (y=0; y<h; y++) {
    for (x=0; x<w; x++) {
        array[x][y] = diagonalvalue(x,y,w,h);
    }
}

Of course if there is not such a limitation, something like that should be way faster:

n = w*h;
x = 0;
y = 0;
for (i=0; i<n; i++) {
    array[x][y] = i;
    if (y <= 0 || x+1 >= w)  {
        y = x+y+1;
        if (y >= h) {
            x = (y-h)+1;
            y -= x;
        } else {
            x = 0;
        }
    } else {
        x++;
        y--;
    }
}

Answer 2

What about this (having an NxN matrix):

count = 1;
for( int k = 0; k < 2*N-1; ++k ) {
  int max_i = std::min(k,N-1);
  int min_i = std::max(0,k-N+1);
  for( int i = max_i, j = min_i; i >= min_i; --i, ++j ) {
    M.at(i).at(j) = count++;
  }
}