That matrix consists of consecutive integers ordered in a fractal criss-cross manner. In the following illustration modified from this article, the submatrix of each color consists of consecutive integers ordered in a criss-cross manner, and the submatrices themselves are ordered in the same criss-cross manner.
To compute the coordinate, you can compute in which submatrix the queried integer is. Then recursively compute the coordinate of the first entry of that submatrix. Then add to that coordinate depending on which index the queried integer has in that submatrix (for example, the largest value of the submatrix is located under the smallest one).
function bayerCoordinate(index, size) {
if (size === 1) {
return [0, 0];
}
const half = size / 2;
const whichSubmatrix = Math.floor(index / 4);
const indexInSubmatrix = index % 4;
const [x, y] = bayerCoordinate(whichSubmatrix, half);
switch (indexInSubmatrix) {
case 0:
return [x, y];
case 1:
return [x + half, y + half];
case 2:
return [x + half, y];
case 3:
return [x, y + half];
default:
throw new Error("Invalid value, probably not a nonnegative integer: "+index);
}
}
Complexity: Looks like n_iterations searches through the 2×2 base matrix instead of computing and searching the entire large 2^n_iterations × 2^n_iterations matrix.
