3

The following code snippet, with width=2,height=2

int maxI = width + height;
for (int i = 1; i <= maxI; i++) {
    int startJ = Math.Max(0, i - width);
    int maxJ = Math.Min(i, height);
    for (int j = startJ; j <= maxJ; j++) {
        int x = i - j;
        int y = j;
        DoSomething(x,y);}}

Will call DoSomething with the following x,y pairs:

1: X=1,Y=0
2: X=0,Y=1          (Diagram: 0,0 
3: X=2,Y=0          at bottom left)
4: X=1,Y=1           5 7 8
5: X=0,Y=2           2 4 6
6: X=2,Y=1           @ 1 3
7: X=1,Y=2
8: X=2,Y=2

This is the desired result; to iterate a rectangle starting from 0,0 but expanding diagonally rather than (the much more popular) [y*width+x]. However, I'm baffled by the maxI=width+height and x=i-j calculations. How does this conversion work?

2
  • What exactly is it that baffles you? Your snippet shows only ints, so there's no conversion at all involved. Jan 13, 2014 at 17:31
  • 2
    i iterates through the diagonals (excluding the upper left corner). So maxI is the number of diagonals. j iterates though the elements on the current diagonal. So maxJ takes the current i and computes the number of elements in that diagonal.
    – mbeckish
    Jan 13, 2014 at 17:35

2 Answers 2

3

The thing to realize here is that x + y is a constant for each cell in a particular diagonal. For example, cells 3, 4, and 5 have coordinates {2, 0}; {1, 1}; {0, 2}. Notice that each of those add up to 2.

So maxI is really the maximum value of one of these sums. Since {width, height} is the top right, the sum for that diagonal is width + height. So that's where that comes from.

The i - j part comes about because it's basically solving the above equation. Each value of i is the sum of the coordinates. j is chosen to be the y-coordinate of a cell within that diagonal. Since we know x + y = i and that y = j, we get that x + j = i or x = i - j.

1

This can be also explained by geometric transformations:

1) Translation, so the rectangle's center is in origin:

x' = x - width/2
    bounds: [-width/2,width/2)

y' = y - height/2
    bounds: [-height/2,height/2)

2) Rotation by 45 degrees:

x'' = x'cos(45) - y'sin(45) = (sqrt(2)/2)x' - (sqrt(2)/2)y'
y'' = x'sin(45) + y'cos(45) = (sqrt(2)/2)x' + (sqrt(2)/2)y'

3) Scaling by sqrt(2)/2:

x''' = x' - y' = x - width/2 - y + height/2   
    bounds: [-width/2-height/2,width/2+height/2)

y''' = x' + y' = x - width/2 + y - height/2   
    bounds: [-width/2-height/2,width/2+height/2)

4) Translating back only on x axis:

x'''' = x''' + width/2 = x - y + height/2     
    bounds: [-height/2,width/2+height/2)

y'''' = y'''                                  
    bounds: [-width/2-height/2,width/2+height/2)

5) Introducing parametric variables:

i = y'''' + width/2 + height/2                
    bounds: [0,width+height)

j = x'''' + y'''' - width/2 - height/2        
    bounds: [-width-3*height/2,width/2+height/2)

For this transformation you get that:

x = i - j
y = j

And it will iterate point by point through diagonals going from bottom-right to top-left corner of the screen. Max and Min in the code you presented bound the result to a subset of these diagonals, representing a rectangle.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.