javascript - 在Javascript中查找二维数组中所有连续1的矩形的坐标

Question

我发现很多问题询问如何在二维数组中找到最大的连续矩形，有些问题询问矩形的数量，但只有一个问题涉及查找所有矩形的坐标、宽度和高度在 1 和 0 的 2D 中覆盖 1 的区域所需的矩形。

问题 ( Finding rectangles in a 2d block grid ) 有一个解决方案，但很难理解，因为它引用了外部代码块。

我正在处理构成字母像素的二维数组:

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)，或者提供所需步骤的更深入解释吗？

Answer 1

这是一种使用简单算法来完成此操作的方法。

1. 计算矩形覆盖的总面积 -> A
2. 虽然目前找到的矩形面积小于A
   1. 找到一个新的矩形
      1. 找到左上角，扫描矩阵并停在找到的第一个 1
      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;
    }
  }
}