4 ms·
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
by 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 agoThanks. Helpful and clear. single pixels don't have orientation, I overlooked that.