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 +-------------+ +---- -------+ |#############| |### ######| |#############| |### ######| | +--+ | |###+ +######| |###| |######| |###| |######| |###+ +------| | +--+ |### |######| |### |######| +---- +------+
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:
Divide the space into rectangles based on the corners identified by the occupied spaces.
Form the "basic rectangles" by extending line segments from those corners to the edges of the entire space.
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:
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;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With