javascript - 如何将 Canvas 图像数据转换为嵌套象限

Question

示例:

假设我有一个分辨率为 512x512 的 Canvas 。我正在尝试按如下方式获取它的坐标:

第一步:将每个 Canvas 划分为笛卡尔坐标象限

 _____ _____|     |     ||  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;
        }
    }

我不懂二进制数学，或者神奇的 49 数字？这是 "1" 的字符串。将其用作起点是个好主意吗？

Answer 1

假设您的图像有 2^p 宽度 == 高度。
像素的每个 (x,y) 坐标都将有一个 x 和 y，编码为 p 位。
现在很好的是象限坐标只是 x 和 y 坐标的交错:

我们可以将 x 一点一点地写成:

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

和 y 作为:

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

那么 q 是 x 和 y 的交错:

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

q 是您要搜索的象限坐标，但它的构建方式如下:

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

也许这样的方案更清晰:

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

其实在上面的方案中，x是用第一个bit编码的，y是用第二个bit编码的。

更一般地，一个点在哪个象限中仅取决于 x 中的高位和 y 中的高位。
你可以很快想象，如果 x > 255 我们在右边，否则我们在左边。 y 也是如此:如果 y <=255 我们在顶部，如果 y>255 我们不是。测试 if x>255 与测试 x & 256 相同 => 测试是否设置了最重要的位。
事实上，如果你仔细想想，在所有分辨率下都会出现完全相同的方案:假设我们在 00 象限。现在看看我们是在这个象限的左边还是右边，我们将比较 x 和 127。y 也一样.所以实际上我们正在测试 x 和 y 的第二位。

所以你可以看到，(x,y) 点的交错位描述了点象限 [xp-1yp-1], [xp-2yp-2], ..., [ x2y2], [x1y1], [x0y0]

现在可以在这里找到代码:http://jsbin.com/cavifito/1/edit?js,console

x,y -> 象限坐标函数非常简单:

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;
}

另一方面，象限坐标 -> (x,y) 函数是:

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;
}

这里有一个方便的函数，可以将象限更改为人类可读的数字(每个数字代表一个象限)。

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;
}

widthLog = 2/width = 4 的结果:

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

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