1

I have found numerous questions asking about how to find the largest contiguous rectangle in a 2D array, and some that ask for the number of rectangles, but only one that deals with finding the coordinates, width, and height of all of the rectangles required to cover an area of 1s in a 2D of 1s and 0s.

The question (Finding rectangles in a 2d block grid) has a solution but is difficult to follow since it references an external code block.

I am dealing with 2D arrays that make up the pixels of letters:

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

The desired output here would be something like:

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

Where each array contains the upper left hand coordinate and lower right hand coordinate (any method that gets upper left and width and height also works).

Could someone provide the psudocode (or Javascript) for either the question previously asked or another algorithm that works, or provide a more in-depth explanation of the steps required?

Freddie R
  • 377
  • 5
  • 15

2 Answers2

3

Here is a way to do it with using a simple algorithm.

  1. Calculate the total area covered by rectangles -> 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. Find the bottom right corner, starting at the upper left corner, scan the matrix and stop at the first 0 found
    2. Mark the rectangle found by setting each cell to something else than 1
    3. Add its area to the accumulated area
    4. Push the rectangle to a list

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;
    }
  }
}
jo_va
  • 13,504
  • 3
  • 23
  • 47
  • 1
    This is extremely helpful. It works (giving a ~10x speed increase), and is far easier to understand than anything else I've come across, thank you. – Freddie R Feb 19 '19 at 10:39
  • I am using this code in an open source javascript library, how would you like to be acknowledged? – Freddie R Feb 23 '19 at 23:47
  • I found a *lot* of algorithms addressing a similar problem. This was the only one that worked for my use case, and the only one that (in my opinion) was understandable without a math degree. Many thanks @jo_va, I wish I could give you more rep. – Anders Aug 18 '22 at 22:10
0

here is my python code,do optimization add beginx

def find(mat):
    W = len(mat[0])
    H = len(mat)

    #get the area covered by rectangles
    totalRectArea = 0
    for i in range(W):
      for j in range(H):
          if mat[j][i] > 0:
              totalRectArea += 1

    rects = []
    rectArea = 0

    #find all rectangle until their area matches the total
    beginx=0
    beginy=0
    while (rectArea < totalRectArea):
      rect = findNextRect(beginx,beginy,W,H,mat)
      if(rect['x1']>1):
          beginx=rect['x1']-1
      if(rect['y1'] > 1):
          beginy=rect['y1']-1

      rects.append(rect)
      markRect(rect,mat)
      rectArea += (rect['x2'] - rect['x1'] + 1) * (rect['y2'] - rect['y1'] + 1);

    print(rects)
    return rects

#mark rectangle so won't be counted again
def markRect(rect,mat) :
    for i in range(rect['x1'], rect['x2']+1):
        for j in range(rect['y1'], rect['y2']+1):
          mat[j][i] = 2

def findNextRect(beginx,beginy,W,H,mat):
    #find top left corner
    foundCorner = False
    rect = {'x1': 0, 'x2': W-1, 'y1': 0, 'y2': H-1 }
    for i in range(beginx,W):
        for j in range(H):
          
          if (mat[j][i] == 1):
            rect['x1'] = i
            rect['y1'] = j
            foundCorner = True
            break
        if (foundCorner):
            break

    #find bottom right corner
    for i in range(rect['x1'], rect['x2']+1):
        
        if (mat[rect['y1']][i] != 1):
            rect['x2'] = i-1
            return rect
        for j in range(rect['y1'], rect['y2']+1):
          
          if (mat[j][i] != 1) :
            rect['y2'] = j-1;
            
            break

    return rect
Xj Zhao
  • 1
  • 1
    As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Mar 18 '23 at 12:01