How to convert canvas imageData to nested quadrants

Question

Example:

Lets say i have a canvas of 512x512 resolution . I am trying to get it's coordinates as follows :

First step : Divide each canvas into Cartesian coordinate quadrants

 _____ _____
|     |     |
|  2  |  1  |
|_____|_____|
|     |     |
|  3  |  4  |
|_____|_____|

Second step : Divide each quadrant to another four quadrants and add new quadrant id after the old one , like this :

 _____ _____ _____ _____
|     |     |     |     |
|  22 |  21 |  12 |  11 |
|_____|_____|_____|_____|
|     |     |     |     |
|  23 |  24 |  13 |  14 |
|_____|_____|_____|_____|
|     |     |     |     |
|  32 |  31 |  42 |  41 |
|_____|_____|_____|_____|
|     |     |     |     |
|  33 |  34 |  43 |  44 |
|_____|_____|_____|_____|

And so on...

 _____ _____ _____ _____ _____ _____ _____ _____
|     |     |     |     |     |     |     |     |
| 222 | 221 | 212 | 211 | 122 | 121 | 112 | 111 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 223 | 224 | 213 | 214 | 123 | 124 | 113 | 114 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 232 | 231 | 242 | 241 | 132 | 131 | 142 | 141 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 233 | 234 | 243 | 244 | 133 | 134 | 143 | 144 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 322 | 321 | 312 | 311 | 422 | 421 | 412 | 411 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 323 | 324 | 313 | 314 | 423 | 424 | 413 | 414 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 332 | 331 | 342 | 341 | 432 | 431 | 442 | 441 |
|_____|_____|_____|_____|_____|_____|_____|_____|
|     |     |     |     |     |     |     |     |
| 333 | 334 | 343 | 344 | 433 | 434 | 443 | 444 |
|_____|_____|_____|_____|_____|_____|_____|_____|

Until number of quadrants is equal to the number of pixels

I am trying to wrap my head here, about how to implement this functionality. First i thought of doing a function which will get an imageData index and return it's quadrant id . But this way i'll have to do some heavy(?) computation each time the function is called .
Or To generate a new array from imageData and access its elements by index when i need them .

I'm sure there are a couple of ways one could tackle this problem . A recursive approach is interesting , is it possible on a bigger canvas ?

Friend of mine pointed me to the following piece of code that does something very similar , but i am struggling to follow whats going on here :

for (var y = 0; y < 512; y++)
    for (var x = 0; x < 512; x++){
            var s = "";
        for (var b = 1; b <= 256; b *= 2){
                var yb = y & b;
                var xb = x & b;
                s = String.fromCharCode(49 + (xb != yb) + yb / b * 2) + s;
        }
    }

I don't get the binary math , or the magic 49 number ? which is a string of "1" . is it a good idea to use it as starting point ?

Answer 1

Say that that your image has a 2^p width == height.
Every (x,y) coordinates of a pixel will have a x and y that codes on p bits.
Now what's fine is that the quadrant coordinates are just an interleave of x and y coordinates :

We can write x, bit by bit, as :

x = x(p-1) x(p-2)  ... x2 x1 x0

and y as :

x = y(p-1) y(p-2)  ... y2 y1 y0

then q is the interleave of x and y :

q = x(p-1)y(p-1) x(p-2)y(p-2)  ... x2y2 x1y1 x0y0 

q is the quadrant coordinates you're searching for, except it's built like :

 _____ _____
|     |     |
|  0  |  2  |
|_____|_____|
|     |     |
|  1  |  3  |
|_____|_____|

Maybe the scheme is more clear like this :

 x = 0   x = 1
 _____________
|      |      |
|  00  |  10  |  y = 0
|______|______|
|      |      |
|  01  |  11  |  y = 1    (figures inside are in binary form)
|______|______|

In fact on the scheme above, x is coded by the first bit, and y is coded by second bit.

More generally, in which topmost quadrant a point is depend only the upper bit in x and the upper bit in y.
You can imagine quickly, if x > 255 we are on the right otherwise we are on the left. same goes for y : if y <=255 we are on top, and if y>255 we are not. Testing if x>255 is the same as testing x & 256 => testing wether most important bit is set or not.
And in fact if you think carefully, the exact same scheme will occur at all resolutions : say we are on quadrant 00. Now to see if we are in left or right part of this quadrant, we will compare x to 127. Same for y. So in fact we are testing the second bit of x and y.

So you can see that, taken two by two, the interleaved bits of the (x,y) points describes the points quadrants [xp-1yp-1], [xp-2yp-2], ..., [x2y2], [x1y1], [x0y0]

Now the code, that you can find live here : http://jsbin.com/cavifito/1/edit?js,console

the x,y -> quadrant coordinates function is pretty straightforward bit mashing:

var widthLog=10;  // 2^10 = 1024 X 1024 picture

function getQuadrant(x,y) {
    var q=0;
    var mask = 1 << (widthLog-1) ; 
    for (var i=0; i<widthLog; i++) {
        q<<=1;
        q |= ((x & mask ) == mask);
        q<<=1;
        q |= ((y & mask) == mask);
         x<<=1; y<<=1;      
    }
    return q;
}

On the other hand, quadrant coordinates -> (x,y) function is :

function getCoords(q, pt) {
  var x=0, y=0;
    var mask = 1 << (2*(widthLog)-1) ; 
    for (var i=0; i<widthLog; i++) { 
      x<<=1;
      x |= ((q & mask)==mask);
      q<<=1;
      y<<=1;
      y |= ((q & mask)==mask);
      q<<=1;    
    }  
  pt.x = x;
  pt.y = y;
}

Here's a handy function that changes the quadrant into a human readable number (each digit stands for a quadrant).

function quadrantToNum ( q ) {
     var res = 0;
     var bitIndex = 2*widthLog ;
     var mask = 3 << (bitIndex);
     while ( mask ) {
       var qi = (q & mask) >> bitIndex ;
       bitIndex -=2 ;
       mask >>= 2;
       res = 10*res + qi ;
     }
  return res;
}

Results for widthLog = 2 / width = 4 :

00  02  20  22 
01  03  21  23 
10  12  30  32 
11  13  31  33 

Result for widthLog = 3 / width = 8 :

000  002  020  022  200  202  220  222  
001  003  021  023  201  203  221  223  
010  012  030  032  210  212  230  232  
011  013  031  033  211  213  231  233 
100  102  120  122  300  302  320  322  
101  103  121  123  301  303  321  323  
110  112  130  132  310  312  330  332  
111  113  131  133  311  313  331  333  

Answer 2

If the x-coordinate is abcdefghi in (big-endian) binary and the y-coordinate is jklmnopqr in binary, then the quadrant number represented in base-4 is (up to a consistent renumbering of quadrants) the interleaving ajbkcldmenfogphqir. Here's some bit-twiddling C code to do this for 32-bit coordinates (written for another purpose).

uint64_t expand(int32_t x) {
  uint64_t n = (uint32_t)((int64_t)x - INT32_MIN);
  n = (n | (n << 16)) & UINT64_C(0x0000ffff0000ffff);
  n = (n | (n << 8)) & UINT64_C(0x00ff00ff00ff00ff);
  n = (n | (n << 4)) & UINT64_C(0x0f0f0f0f0f0f0f0f);
  n = (n | (n << 2)) & UINT64_C(0x3333333333333333);
  return (n | (n << 1)) & UINT64_C(0x5555555555555555);
}

int32_t unexpand(uint64_t n) {
  n &= UINT64_C(0x5555555555555555);
  n = (n | (n >> 1)) & UINT64_C(0x3333333333333333);
  n = (n | (n >> 2)) & UINT64_C(0x0f0f0f0f0f0f0f0f);
  n = (n | (n >> 4)) & UINT64_C(0x00ff00ff00ff00ff);
  n = (n | (n >> 8)) & UINT64_C(0x0000ffff0000ffff);
  return (int32_t)((int64_t)(uint32_t)(n | (n >> 16)) + INT32_MIN);
}

uint64_t z_rank(struct Point p) {
  return expand(p.x) | (expand(p.y) << 1);
}

struct Point z_unrank(uint64_t n) {
  return (struct Point){unexpand(n), unexpand(n >> 1)};
}

If you need the string for some reason, then peel off the low-order bits two at a time, something like this.

var s = "";
while (n > 0) {
    s = (n & 3) + s;
    n >>= 2;
}