Найдите координаты всех прямоугольников смежных единиц в двумерном массиве в Javascript

Я нашел множество вопросов о том, как найти самый большой смежный прямоугольник в 2D-массиве, и некоторые, которые спрашивают о количестве прямоугольников, но только один, который касается нахождения координат, ширины и высоты всех прямоугольников, необходимых для покрыть площадь 1s в 2D 1s и 0s.

Вопрос (Поиск прямоугольников в сетке 2d-блоков) имеет решение но его трудно понять, поскольку он ссылается на внешний блок кода.

Я имею дело с 2D-массивами, которые составляют пиксели букв:

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0

Желаемый результат здесь будет примерно таким:

[[4,0,6,17],[7,0,16,2],[7,7,15,9],[7,15,15,17]]

Где каждый массив содержит верхнюю левую координату и нижнюю правую координату (любой метод, который получает верхнюю левую и ширину и высоту, также работает).

Может ли кто-нибудь предоставить псевдокод (или Javascript) либо для ранее заданного вопроса, либо для другого работающего алгоритма, или предоставить более подробное объяснение необходимых шагов?


javascript arrays multidimensional-array
person Freddie R    schedule 19.02.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вот способ сделать это с помощью простого алгоритма.

  1. Вычислить общую площадь, покрытую прямоугольниками -> A
  2. While the area of the rectangles found so far is smaller than A
    1. Find a new rectangle
      1. Find the upper left corner, scan the matrix and stop at the first 1 found
      2. Найдите правый нижний угол, начиная с левого верхнего угла, просканируйте матрицу и остановитесь на первом найденном 0
    2. Отметьте найденный прямоугольник, установив для каждой ячейки значение, отличное от 1.
    3. Добавить его площадь к накопленной площади
    4. Подтолкнуть прямоугольник к списку

const mat = [
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//0
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//1
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//2
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//3
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//4
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//5
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//6
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0],//7
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0],//8
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0],//9
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//10
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//11
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//12
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//13
  [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],//14
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//15
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0],//16
  [0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0] //17
];

const W = mat[0].length;
const H = mat.length;

// get the area covered by rectangles
let totalRectArea = 0;
for (let i = 0; i < W; ++i) {
  for (let j = 0; j < H; ++j) {
    totalRectArea += mat[j][i] > 0 ? 1 : 0;
  }
}

const rects = [];
let rectArea = 0;

// find all rectangle until their area matches the total
while (rectArea < totalRectArea) {
  const rect = findNextRect();
  rects.push(rect);
  markRect(rect);
  rectArea += (rect.x2 - rect.x1 + 1) * (rect.y2 - rect.y1 + 1);
}

console.log(rects);

function findNextRect() {
  // find top left corner
  let foundCorner = false;
  const rect = { x1: 0, x2: W-1, y1: 0, y2: H-1 };
  for (let i = 0; i < W; ++i) {
    for (let j = 0; j < H; ++j) {
      if (mat[j][i] === 1) {
        rect.x1 = i;
        rect.y1 = j;
        foundCorner = true;
        break;
      }
    }
    if (foundCorner) break;
  }
  // find bottom right corner
  for (let i = rect.x1; i <= rect.x2; ++i) {
    if (mat[rect.y1][i] !== 1) {
      rect.x2 = i-1;
      return rect;
    }
    for (let j = rect.y1; j <= rect.y2; ++j) {
      if (mat[j][i] !== 1) {
        rect.y2 = j-1;
        break;
      }
    }
  }
  return rect;
}

// mark rectangle so won't be counted again
function markRect({ x1, y1, x2, y2 }) {
  for (let i = x1; i <= x2; ++i) {
    for (let j = y1; j <= y2; ++j) {
      mat[j][i] = 2;
    }
  }
}

person jo_va    schedule 19.02.2019
comment
Это очень полезно. Это работает (увеличивая скорость примерно в 10 раз), и его гораздо легче понять, чем что-либо еще, с чем я сталкивался, спасибо. - person Freddie R; 19.02.2019
comment
Я использую этот код в библиотеке javascript с открытым исходным кодом, как бы вы хотели, чтобы вас признали? - person Freddie R; 24.02.2019