extract 2D array from another 2D array represented as a 1D array

user_1414721 0
Viewed 41

So if I have a 2D array such as

const array = [
            [1, 2, 3, 4, 5],
            [9, 8, 7, 6, 5],
            [1, 8, 3, 6, 5],
            [9, 8, 7, 6, 5],
            [1, 8, 3, 6, 5],
            [1, 2, 3, 4, 5]
          ];

which could for the point of the question be any size, square or not square.

and I want to extract 3x3 arrays out of it, for instance at 1,1 that would be const sub = [[8, 7, 6], [8, 3, 6], [8, 7, 6]]. So far so good - I can do this. However I am flattening the 2D array so that its represented as a 1D array (long story as to why), i.e

const array = [1, 2, 3, 4, 5, 9, 8, 7, 6, 5, 1, 8, 3, 6, 5, 9, 8, 7, 6, 5, 1, 8, 3, 6, 5, 1, 2, 3, 4, 5];

What I'm trying to do is extract the same (or any) 3x3 array out of this but while its represented as a 1D array, so I would then get back [8, 7, 6, 8, 3, 6, 8, 7, 6].

I almost got there, however I made an error of only working with arrays that were 9x9 and always extracting 3x3 subsets which mean that my solution only works for that specific case, and the more I stare at my solution, the more I cannot work out what the generic solution would look like.

My solution:

const extractSubsetFrom1D = (array, subHeight, subWidth, startRow, startCol) => {
    const kWH = subWidth * subHeight
    const subset = array.slice(((((kWH - 2) * startRow) + startCol) * kWH), ((((kWH - 2) * startRow) + startCol) * kWH) + kWH)
    return subset
}

In my case subHeight and subWidth were always equalling 3 respectively, and as the array itself was always 9x9 I believe I accidentally stumbled on a solution for that specific case as they divide nicely into each other.

To be clear my solution will fail for the startRow = 1 startCol = 0 for the provided array (it works for the startRow = 0 scenario

multidimensional-array arrays javascript
1 Answers

It's not entirely clear to me how you came to your current implementation, but I can at least tell:

  • āœ… You correctly determined the size of the sub grid array to return (kWH)
  • āŒ You incorrectly assume you can slice out a sub grid as one continuous part of the original 1d array
  • The calculation of the first element seems kind-of-right but is actually wrong (probably because of the previous mistake)

From (y,x) to i

Let's start from scratch and work our way up to a nice one liner.

In a 2d-array, you can get a cell's value by doing:

cellValue = grid2d[y][x]

Once you flatten it, you'll need to do:

cellValue = grid1d[y * GRID_WIDTH + x]

y * GRID_WIDTH takes you to the start of the right row, and + x gets you to the right column.

As you can see, you need to know the original grid's size before you can even query a specific cell. That means your extract function would need an argument to pass the original width (or, if the grids are guaranteed to be square, you can do Math.sqrt(array.length).

A slice per row

Let's use this math to find the indices of a 2x2 sub grid at (1,1) extracted from a 3x3 source grid:

0  1  2
3 [4][5]
6 [7][8]

As you can see, the resulting indices are [4,5,7,8]. There is no way to slice these indices out of the source array directly because we don't want to include the 6.

Instead, we can use a nested loop to skip the gaps between our rows:

const to1d = (x, y, w) => y * w + x;

const extractSubGrid1D = (grid, gridWidth, x, y, w, h) => {
  const yTop = y;
  const yBottom = y + h
  const xLeft = x;
  const xRight = x + w;
  
  const subgrid = [];
  
  for (let y = yTop; y < yBottom; y += 1) {
    for (let x = xLeft; x < xRight; x += 1) {
      const index = to1d(x, y, gridWidth);
      subgrid.push(grid[index]);
    }
  }

  return subgrid;
}

const originalGrid = [
  0, 1, 2,
  3, 4, 5,
  6, 7, 8
];

console.log(
  extractSubGrid1D(originalGrid, 3, 1, 1, 2, 2)
)

Once you get a feel for the logic, feel free to refactor.

The other way around

To go from a 1d-index to a 2d coordinate, you can do:

x = i % w
y = Math.floor(i / w)

Applying this logic, you can also fill your sub grid like so:

  • Create a new array of the right size
  • For each of its indices, determine the original grid's (x, y) coordinate
  • Transform that coordinate back to an index to query the original grid with

const to1d = (x, y, w) => y * w + x;

const extractSubGrid1D = (grid, gridWidth, x, y, w, h) => Array.from(
  { length: w * h },
  (_, i) => grid[to1d(x + i % w, y + Math.floor(i / w), gridWidth)]
)

const originalGrid = [
  0, 1, 2,
  3, 4, 5,
  6, 7, 8
];

console.log(
  extractSubGrid1D(originalGrid, 3, 1, 1, 2, 2)
)

user_32972910
Related