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.

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.

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.

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;
    }
}

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)

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

I think that consider just conrers will not get the best math.

For example, in the image below, the "r" rect is the best match, but does not start in any corner.

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

Here is the algorithm I used for exactly the same case:

This will return a list of Empty Space Rectangles.

1. Order known-obstacles in a list from top-left to bottom-right
2. Create a first Empty Space Rectangle that takes the whole area that you want to check
3. For each obstacle (O) in order :
   1. For each Empty space that overlaps O
      1. Delete Empty Space Rectangle (ESR)
      2. If ESR.left < O.left, Create New Empty Space Rectangle (NESR) with NESR.right = O.left and add it to the list of ESR the other obstacles must check for overlaps.
      3. If ESR.right > O.right, Create New ESR, NESR.left = O.right
      4. If ESR.bottom < O.bottom, Create New ESR, NESR.top = O.bottom
      5. If ESR.top > O.top, Create New ESR, NESR.bottom = O.top

N.B: this is a sequence of If, not else if. Meaning that you create up to 4 new ESR for each overlap.

Explanation:

• We create a single huge "Empty Space Rectangle", then we check for each known obstacle to know if it overlaps with it (it obviously does, as this rectangle covers everything).
• The first obstacle will split the first Empty space rectangle into up to 4 smaller rectangles. Clamped to not overlap it.
• The 2nd obstacle will then check if it overlaps any of the newly created Empty space rectangles. Each rectangle it overlaps is split further down, into up to 4 new rectangles. None of those will overlap either obstacle 1 or obstacle 2.
• We keep going like that until every obstacle has been checked.
• We end up with a list of Empty spaces that do not overlap any obstacles. We will definitely have overlaps though.

I think that you can implement a Montecarlo Approach.

Regards.