What is an algorithm to return free space in blocks of largest possible rectangles?

Question

Algorithm

Consider this layout:

+-------------+
|             |
|             |
|   +--+      |
|   |##|      |
|   |##|      |
|   +--+------+
|      |######|
|      |######|
+------+------+

The black part is the occupied space. Now I need an algorithm that returns the largest remaining rectangular spaces. (Ordered from top to bottom, left to right.)

Like this:

1                 2          3            4
+-------------+   +----      -------+
|#############|   |###        ######|
|#############|   |###        ######|
|   +--+      |   |###+      +######|
                  |###|      |######|
                  |###|      |######|
                  |###+      +------|     |   +--+
                  |###                    |######|
                  |###                    |######|
                  +----                   +------+

Input

The width and height of the enclosing container. (A page in my code.)

A list of already occupied rectangles. They can be in any form that you like. E.g. (x,y,width,height) or (x1,y1,x2,y2)

I'm dealing with floats, therefore a mathematical solution would be preferred.

Answer 1

Pardon me for writing in codes:

for(int y = 0; y < rows; y++){

  for(int x = 0; x < columns; x++){
     // (x, y) would be the current space

     if(checkEmptySpace(x,y)){
       // empty space found

     }

  }

}

That's the easiest and straight way to do this. but the bad point is that it has to loop through all the space which may cause inefficiency.

Improvised:

1. (STEP1) loop through all the rows while rows are empty
2. (STEP1) stop when an occupied space is found in the row
   1. (STEP1) store the value of the current row to TOP_EMPTY only when first time
3. (STEP2) if number remaining rows is > number of columns go to step 8
4. (STEP2) loop through remaining rows
5. (STEP2) calculate space in front of occupied space
6. (STEP2) calculate space behind occupied space
7. (STEP2) loop end
8. (STEP2) go to 13
9. (STEP2) loop through columns
10. (STEP2) skip TOP_EMPTY rows
11. (STEP2) calculate space before occupied space in column
12. (STEP2) calculate space after occupied space in column
13. (STEP2) loop end
14. (STEP3) calculate the space at the top with TOP_EMPTY * no. of columns
15. DONE.

Answer 2

1. Start
2. set row=0, column=0
3. if is free space:
   1. get largest free rectangle, starting horizontally
4. if not, and at the last column, and not at end, row + 1, column = 0 and goto 3
5. else if not at last column, column + 1 and goto 3
6. else end

(note that 3.1 is the same algorithm, only with free/blocked inverted, and with different coordinates)

Answer 3

From your example it appears that you aren't asking to exclude overlap (e.g. 1 and 2 have the top-left segment in common), so perhaps this will suit your needs:

1. Divide the space into rectangles based on the corners identified by the occupied spaces.

2. Form the "basic rectangles" by extending line segments from those corners to the edges of the entire space.

3. Using any systematic order (e.g. top-to-bottom, left-to-right):

   3.1. Select a basic rectangle and extend it as far as possible with other basic rectangles that have a side in common.

   3.2. Form the set of all (unique) such extended rectangles.

Note that this searches/builds based on the "basic rectangles" from step 2, and not point-by-point throughout the entire space, so the performance should be much better.

Answer 4

You're looking for something similar to Code Golf: Running Water

Answer 5

char mark = 'A';
for(i from 0 to rows)
    colstart = 0;
    while(colstart = next empty col in ith row)
        width = 0;
        for(j from colstart to columns)
        {
            if(empty)
                width++;
            else 
                break;
        }
        if(width == 0)
            continue
        for(n from colstart to colstart + width)
            for(m from i to rows)
                if(!empty)
                    break;
            if(m != i)
                set the rectangle from i, colstart to m - 1, colstart + width 
                with mark char and increment mark;

update: java code.

public class Program
{
    public static char occuppied;
    public static char vacant;
    public static char mark;
    public static void main(String[] args)
    {
     int rows = 7;
     int cols = 11;
     mark = 'A';
     occuppied = '#';
     vacant = '-';
     char[][] matrix = new char[rows][cols];
     setRect(matrix, vacant, 0, 0, rows, cols);
     setRect(matrix, occuppied, 3, 3, 2, 2);
     setRect(matrix, occuppied, 5, 5, 2, 6);

     print(matrix);
     for(int i = 0; i < rows; i++)
     {
      int colstart = 0;
      while((colstart = nextEmptyCol(matrix[i], colstart)) != -1)
      {
       int width = 0;
       for(int j = colstart; j < cols; j++)
       {
        if(matrix[i][j] == vacant)
         width++;
        else
         break;
       }
       if(width == 0)
        continue;
       int height = 1;
       outer:
       for(; height + i < rows; height++)
        for(int n = 0; n < width; n++)
        {
         if(matrix[i + height][colstart + n] == occuppied)
          break outer;
        }
       System.out.println("width = " + width + ", height = " + height);
       setRect(matrix, mark, i, colstart, height, width);
       print(matrix);
       mark++;
      }
     }
    }
    public static void setRect(char[][] matrix, char c, int startrow, int startcol, int numrows, int numcols)
    {
     for(int i = 0; i < numrows; i++)
      for(int j = 0; j < numcols; j++)
       matrix[startrow + i][startcol + j] = c;
    }
    public static void print(char[][] matrix)
    {
     int rows = matrix.length;
     int cols = matrix[0].length;
     for(int i = 0; i < rows; i++)
     {
      for(int j = 0; j < cols; j++)
       System.out.print(matrix[i][j] + " ");
      System.out.println();
     }
     for(int i = 0; i < cols; i++)
      System.out.print("==");
     System.out.println();
    }
    public static int nextEmptyCol(char[] row, int start)
    {
     for(int i = start; i < row.length; i++)
      if(row[i] == vacant)
       return i;
     return -1;
    }
}

Answer 6

Hi,

I think that you can implement a Montecarlo Approach.

Regards.