Detect free space in two dimension array

Question

I need this for angular gridster when I add new item so I know the dimension of the new element I'm adding (when there is no space for current element), but to simplify lets assume that I have 2 dimension array with value true or false and I want to search the first free space in array to find position x,y and width,height of free space. So far I have this:

var array = [
  [false, false, false, false, false, false],
  [false, false, false, false, false, false],
  [false, false, false, false, false, false],
  [false, false, false, true, true, true],
  [false, false, false, true, true, true]
];
var place = {};
loop:
for (var i=0; i<array.length; i++) {
  for (var j=0; j<array[i].length; j++) {
    if (array[i][j] && !place.x && !place.y) {
      place.x = j;
      place.y = i;
      place.width = 0;
      place.height = 0;
      for (var y=i; y<array.length; y++) {
        for (var x=j; x<array[y].length; x++) {
          if (array[y][x]) {
            place.width =  x - j + 1;
            place.height = y - i + 1;
          }
        }
      }
      break loop;
    }
  }
}
console.log(place);

but this will fail for array like this:

var array = [
  [false, false, false, false, false],
  [false, false, false, false, false],
  [false, false, false, false, false],
  [true, true, false, true, true],
  [true, true, false, true, true]
];

How can I fix my code to make it work for array like this? The result should be:

{x:0, y:3, width: 2, height: 2}

How are those numbers interpreted? Is it, basically `array[x][y]` where the free space (`true`) starts and then `width` and `height` are the end points, i.e., `array[x+width][y+height]` and everything in that range is considered free? — VLAZ, Sep 27 '16 at 14:55
@charlietfl because there are 2 free "slots" in height and 2 in width. — jcubic, Sep 27 '16 at 14:57
@kevinternet I'v already posted the result for the second array, it should be `{x:0, y:3, width: 2, height: 2}` — jcubic, Sep 27 '16 at 14:58
also you've swapped x and y. do `array[y][x]`, and note that j corresponds to y, not x. — danyamachine, Sep 27 '16 at 15:00
i highly recommend breaking your code out into semantic functions that each have a specific job. that way, you can test whether each independent part of your code works separately. for instance, write one function for find the first `true`, and a separate function for finding the block size of a `true` block that starts at `x,y` — danyamachine, Sep 27 '16 at 15:03
one problem is conditional `!place.x && !place.y` ...`x` can be zero but when it should be zero will get overwritten — charlietfl, Sep 27 '16 at 15:18
related: http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-n%C3%97n-binary-matrix — georg, Sep 27 '16 at 16:09

Redu · Answer 1 · 2016-09-27T15:38:30.523

I guess you might do as follows; It will return you the x and y coordinates of the upper left corner along with the width and height of the free opening. If there is no opening (all false) you will be returned a false.

var array = [
  [false, false, false, false, false],
  [false, false, false, false, false],
  [false, false, true, true, true],
  [false, false, true, true, true],
  [false, false, true, true, true]
],
 emptyXY = (a) => { var x,
                        y = a.findIndex(row => (x = row.findIndex(col => col), x !== -1));
                        w = 0,
                        h = 0;
                    while (a[y] && a[y][x+w]) w++;
                    while (a[y+h] && a[y+h][x]) h++;
                    return !!~y && {x:x,y:y,width:w,height:h};
                  };
console.log(emptyXY(array));

score 1 · Accepted Answer · answered Sep 27 '16 at 16:38

Here's another option. I tried to divide the problem in smaller ones:

Find the first true element in the matrix
From there, find the number of true elements adjacent to 1

Here's the fiddle and here's the code. Hope it helps.

function findCoords(matrix) {
  for (var row = 0; row < matrix.length; row++) {
    for (var col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col]) {
        return createCoordsObj(row, col, matrix);
      }
    }
  }
  return null;
}

function createCoordsObj(row, col, matrix) {
  return {
    x: col,
    y: row,
    width: find('width', row, col, matrix),
    height: find('height', row, col, matrix)
  };
}

function find(type, row, col, matrix) {
  var res = 0;
  while (matrix[row] && matrix[row][col]) { // will finish when element in matrix is false || undefined
    res += 1;
    col += type === 'width' ? 1 : 0;
    row += type === 'width' ? 0 : 1;
  }
  return res;
}

console.log(findCoords([
  [false, false, false, false, false],
  [false, false, false, false, false],
  [false, false, false, false, false],
  [true, true, false, true, true],
  [true, true, false, true, true]
]));

Your code fail on this: `console.log(findCoords([ [false, false, false, false, true, true], [false, false, false, false, true, false], [false, false, false, false, false, false], [true, true, true, false, true, true], [true, true, true, false, true, true] ]));` but I think that this case may never happen in my code. — jcubic, Sep 28 '16 at 08:11

Detect free space in two dimension array

2 Answers2