Convert 3D array to 2D array

Question

I have a rank 3 int array array[9][3][3] and I want to convert it into a rank 2 array arrayConvt[9][9] by removing the major axis (rather than the middle axis). To make a 9x9 array rather than 3x27, imagine array broken up into 3 equal parts, each laid out into arrayConvt before the next. Note that the middle arrays (array[i]) do not remain contiguous in arrayConvt, but the innermost arrays (array[i][j]) do.

One way to visualize it is to look at array as an array of 9 blocks. I want to recombine the blocks left-to-right, top-to-bottom:

How can I reshape array according to this mapping?

The code sample below provides data to work with and the desired result:

public static void main(String[] args) {
    int[][][] array = {
        {
            {0, 1, 2},
            {10, 11, 12},
            {20, 21, 22}
        },
        {
            {100, 101, 102},
            {110, 111, 112},
            {120, 121, 122}
        },
        {
            {200, 201, 202},
            {210, 211, 212},
            {220, 221, 222}
        },
        {
            {300, 301, 302},
            {310, 311, 312},
            {320, 321, 322}
        },
        {
            {400, 401, 402},
            {410, 411, 412},
            {420, 421, 422}
        },
        {
            {500, 501, 502},
            {510, 511, 512},
            {520, 521, 522}
        },
        {
            {600, 601, 602},
            {610, 611, 612},
            {620, 621, 622}
        },
        {
            {700, 701, 702},
            {710, 711, 712},
            {720, 721, 722}
        },
        {
            {800, 801, 802},
            {810, 811, 812},
            {820, 821, 822}
        }
    };
    
    int[][] arrayConvt;
    
    /*****
     * What should go here to fill out `arrayConvt` using entries from `array` so it's equivalent to `array2d` below?
     */
    
    int[][] array2d = {
        {  0,   1 ,  2,   100, 101, 102,   200, 201, 202},
        { 10,  11,  12,   110, 111, 112,   210, 211, 212},
        { 20,  21,  22,   120, 121, 122,   220, 221, 222},
        
        {300, 301, 302,   400, 401, 402,   500, 501, 502},
        {310, 311, 312,   410, 411, 412,   510, 511, 512},
        {320, 321, 322,   420, 421, 422,   520, 521, 522},
        
        {600, 601, 602,   700, 701, 702,   800, 801, 802},
        {610, 611, 612,   710, 711, 712,   810, 811, 812},
        {620, 621, 622,   720, 721, 722,   820, 821, 822}
    };
    
}

Answer 1

Try this.

public static void main(String[] args) {
    int[][][] array = {
        {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}},
        {{10, 11, 12}, {13, 14, 15}, {16, 17, 18}},
        {{20, 21, 22}, {23, 24, 25}, {26, 27, 28}},
        {{30, 31, 32}, {33, 34, 35}, {36, 37, 38}},
        {{40, 41, 42}, {43, 44, 45}, {46, 47, 48}},
        {{50, 51, 52}, {53, 54, 55}, {56, 57, 58}},
        {{60, 61, 62}, {63, 64, 65}, {66, 67, 68}},
        {{70, 71, 72}, {73, 74, 75}, {76, 77, 78}},
        {{80, 81, 82}, {83, 84, 85}, {86, 87, 88}},
    };
    int[][] arrayConv = new int[9][9];

    int[][] s = {
        {0, 0}, {0, 3}, {0, 6},
        {3, 0}, {3, 3}, {3, 6},
        {6, 0}, {6, 3}, {6, 6},
    };

    for (int i = 0, p = 0; i < 9; ++i, ++p)
        for (int j = 0, r = s[p][0]; j < 3; ++j, ++r)
            for (int k = 0, c = s[p][1]; k < 3; ++k, ++c)
                arrayConv[r][c] = array[i][j][k];

    for (int[] r : arrayConv)
        System.out.println(Arrays.toString(r));
}

output:

[0, 1, 2, 10, 11, 12, 20, 21, 22]
[3, 4, 5, 13, 14, 15, 23, 24, 25]
[6, 7, 8, 16, 17, 18, 26, 27, 28]
[30, 31, 32, 40, 41, 42, 50, 51, 52]
[33, 34, 35, 43, 44, 45, 53, 54, 55]
[36, 37, 38, 46, 47, 48, 56, 57, 58]
[60, 61, 62, 70, 71, 72, 80, 81, 82]
[63, 64, 65, 73, 74, 75, 83, 84, 85]
[66, 67, 68, 76, 77, 78, 86, 87, 88]

Answer 2

First, construct some source data

int src[][][] = new int[9][3][3];
for (int r = 0; r < 9; r++) {
    for (int rr = 0; rr < 3; rr++) {
        for (int cc = 0; cc < 3; cc++) {
            src[r][rr][cc] = r * 9 + rr * 3 + cc + 1;
        }
    }
}
for (int[][] d : src) {
    System.out.println(Arrays.deepToString(d));
}

prints

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[10, 11, 12], [13, 14, 15], [16, 17, 18]]
[[19, 20, 21], [22, 23, 24], [25, 26, 27]]
[[28, 29, 30], [31, 32, 33], [34, 35, 36]]
[[37, 38, 39], [40, 41, 42], [43, 44, 45]]
[[46, 47, 48], [49, 50, 51], [52, 53, 54]]
[[55, 56, 57], [58, 59, 60], [61, 62, 63]]
[[64, 65, 66], [67, 68, 69], [70, 71, 72]]
[[73, 74, 75], [76, 77, 78], [79, 80, 81]]
    

Now transform the matrix

int[][] dst = transform(src);

for (int[] row : dst) {
    System.out.println(Arrays.toString(row));
}

prints

[1, 2, 3, 10, 11, 12, 19, 20, 21]
[4, 5, 6, 13, 14, 15, 22, 23, 24]
[7, 8, 9, 16, 17, 18, 25, 26, 27]
[28, 29, 30, 37, 38, 39, 46, 47, 48]
[31, 32, 33, 40, 41, 42, 49, 50, 51]
[34, 35, 36, 43, 44, 45, 52, 53, 54]
[55, 56, 57, 64, 65, 66, 73, 74, 75]
[58, 59, 60, 67, 68, 69, 76, 77, 78]
[61, 62, 63, 70, 71, 72, 79, 80, 81]

• sr,sc - the source row and column of the inner 3x3 matrix to copy
• r - the destination row to contain the above
• the outer loop is used to create the destination row as well as allow
  intermediate increments of key variables
• and the JavaDoc explains System.arraycopy

public static int[][] transform(int[][][] src) {
  int sr = 0;
  int[][] dst = new int[9][9];
  for (int x = 0; x < 3; x++) {
     for (int sc = 0; sc < 3; sc++) {
        int r = x * 3 + sc;
        System.arraycopy(src[sr][sc], 0, dst[r], 0, 3);
        System.arraycopy(src[sr + 1][sc], 0, dst[r], 3, 3);
        System.arraycopy(src[sr + 2][sc], 0, dst[r], 6, 3);
     }
     sr = sr + 3;
  }
  return dst;
}

Answer 3

The best way of figuring out how to do this sort of thing is to play around with indices & reshaping, examining the resultant arrays. Once you do this, you notice a few things that can help you come up with more formal approaches.

One is to examine the mapping in terms of array index expressions. Since you want to map array[i][j][k] to arrayConvt[u][v], you need a way of expressing u and v in terms of i, j and k (or vice versa).

Calculate Destination Indices

Let's start with u. Note each array[i][j] remains contiguous in the result. Note also that array[i][j] is followed by array[i+1][j] (rather than array[i][j+1]) until you reach the end of arrayConvt. Thus, array[i..i+2][j] (where i is a multiple of 3), if flattened, becomes arrayConvt[j+x]. The x is present because the range of j doesn't quite match between array and arrayConvt, and so an adjustment is needed. Once the first 3 arrays in arrayConvt are filled, j goes back to 0, but j+x can go on to the next element of arrayConvt. As for where to get x, k is similarly limited in range, but i hasn't run through its range. Since j runs 0..2, it only needs to be combined with a multiple of 3, which we can get with (i / 3) * 3. This gives j + (i / 3)*3, which a quick mental check will show that it runs 0..8. Thus, u = j + (i / 3) * 3.

On to v. First note:

1. the minor index (k) in array[i][j][k] changes just as rapidly for arrayConvt and
2. the minor index for arrayConvt is independent of j

Thus v = k + f(i) (where f must be determined). Looking at how each arrayConvt[u] is layed out in terms of k and the 1D arrays from array[i][j] (<1D> #n in the diagram), we see something similar to how u related to i.

  v  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
  k  | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
     |  <1D> #0  |  <1D> #1  |  <1D> #2  |
  i  |  3a + 0   |  3a + 1   |  3a + 2   |
f(i) |     0     |     3     |     6     |

We can see that for any row of arrayConvt, i % 3 will range over 0..2. (i % 3) * 3 gives us f(i). Thus v = k + (i % 3) * 3

This gives you a loop over the source array indices, which are mapped to the destination array indices.

int[][] arrayConvt = array[array.length][array[0].length * array[0][0].length];
for (int i = 0; i < array.length; ++i) {
    for (int j = 0; j < array[i].length; ++j) {
        for (int k = 0; k < array[i][j].length; ++j) {
            arrayConvt[j + (i/3)*3][k + (i%3)*3] = array[i][j][k];
        }
    }
}

Calculate Source Indices

You can take the above expressions for u and v and rewrite them so i, j and k are in terms of u and v. You could also try starting from u and v and examine how i, j and k might come from them. Let's do this, but by a different route: examine the entries in the sample array2d, since i, j and k can be read directly from it (not an accident; by encoding coordinates into the original array and figuring out where each element should get mapped to, the overall mapping is, in effect, created. You could even use this as the basis for the mapping function: loop over the elements of the coordinate array, and use the values & indices to copy from the source to the destination).

k we see increasing left-to-right only (along v), though it wraps around. This is simply v % 3. j increases top-to-bottom (along u) and also wraps around. Thus j = u % 3.

i varies with both u and v. It also occurs in groups of 3 along both axes before changing, so we're looking for something involving u / 3 and v / 3. Lastly, it varies faster along v and jumps by 3 along u, so i = (u / 3) * 3 + (v / 3).

You can loop over the destination array indices, and map the source array indices.

int[][] arrayConvt = array[array.length][array[0].length * array[0][0].length];
for (int u = 0; i < arrayConvt.length; ++i) {
    for (int v = 0; j < arrayConvt[i].length; ++j) {
        arrayConvt[u][v] = array[ (u / 3) * 3 + (v / 3) ][u % 3][v % 3];
    }
}

Beyond the Problem

There's another approach that, once spotted, is even easier to work with. Hidden in the 3D array is a hypercube: array can be viewed as a projection of a 4D array into 3 dimensions. You can realize this in various (equivalent) ways:

• envisioning array as 9x3x3, broken into three cubes, you get one fairly common visualization of a projected discrete hypercube (the same as a 3x3x3 discrete cube projected into 2D is 3 3x3 squares).
• An MxN array can be represented as an array of 1 lower rank of size M*N by mapping [i][j] to i*N+j (this is how multidimensional arrays are implemented in languages that use contiguous memory for such arrays). Under this mapping, a T[M][N] is equivalent to T[M*N]. Looking at the indices, note that i can be refactored as i = i_0 * 3 + i_1, where i_0 and i_1 range from 0 through 2. Thus, array[9][3][3] is equivalent to a multidimensional array array4d[3][3][3][3].

From this vantage, the problem is a simple reshaping from a rank 4 cube to a rank 2 cube; the main work is:

1. figuring out the index order from the source
2. identifying which indices of the destination to map to

With indices h, i, j and k, we have the index expression array[h*3+i][j][k] (note: i is the 3rd dimension, or depth, and h is the 4th, or duration). When mapping, the last index of array remains the last of arrayConvt (the 1st dimension). After completing a loop over k, we advance along the outermost array; in particular, the 3rd dimension, i (the 4th is also along the outermost array but jumps from cube to cube). After copying a square (with dimensions width x depth), we continue with a cube, travelling along its height, or j axis. Lastly, we check that the travel direction corresponds to the remaining axis: after finishing a cube, we go to the next cube, which is indeed along h. This gives a an index order (minor to major) of k, i, j, h.

The formulae for u and v come straight from the T[M][N] to T[M*N] conversion. Each index of arrayConvt uses two indices from the hypercube, in the previously determined index order: that's h and j for u, and i and k for v. Thus, u = h * 3 + j and v = i * 3 + k.

int M = 3,
    N = 3,
    P = 3,
    Q = 3;
for (int h = 0; h < M; ++h) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < P; ++j) {
            for (int k = 0; k < Q; ++j) {
                arrayConvt[h * 3 + j][i * 3 + k] = array[h * 3 + i][j][k];
            }
        }
    }
}

Note the index expressions here can be converted to the ones used earlier. You could use this to write a non-nested loop over 0..80 that reshapes array, but it wouldn't be as readable. You can also use this approach to reshape the hypercube to any compatible shape you want.