CODEWITHSUNDEEP
c#
Mr. Smith
Mr. Smith

Reputation: 4516

How does this coordinate conversion achieve the desired result?

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?

Upvotes: 3

Views: 89

Answers (2)

BartoszKP
BartoszKP

Reputation: 35921

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.

Upvotes: 1

Kyle
Kyle

Reputation: 6694

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.

Upvotes: 3

Related Questions