4 ms·

I see what it’s doing recursively (splitting into quadrants and moving clockwise) . But I’m a bit startled as to why it rotates, but I’m thinking when it gets

• arketyp 5y ago
  This lateral shift on a 2x2 grid is equal to rotation. In each iteration tiles are shifted/rotated but its content is not. So the content is split into smaller tiles which are rotated but the content is not, so it is split and so on until you reach pixel level.
• Someone 5y ago
  If you have AB CD with A, B, C, D square blocks of 2^n×2^n pixels, it correctly moves the pixels in A to where those in B are, those in B to where those in D are, etc. It doesn’t rotate A, B, C, and D, though. So, we have to rotate the four smaller blocks A, B, C, D. Let’s assume the algorithm works. Then, we can recurse into each of the smaller blocks. Eventually, you hit the case where A, B, C, and D are 1×1 pixels (and the image 2×2 pixels). Here, you cannot recurse anymore, but luckily, you notice that you can’t see the difference between a single pixel and that pixel rotated by 90 degrees. So, for sunblocks that small, you don’t have to rotate the pixels. Because of that, the 2×2 case works. Because of that, the 4×4 case works, etc. You could also say it doesn’t work. If, say, your pixels had a wood grain running horizontally, that grain would still run horizontally after this set of shifts.
  • acomjean 5y ago
    Thanks. Helpful and clear. single pixels don't have orientation, I overlooked that.