I have an 2D boolean array that looks like this:
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][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][1][1][1][0][0][0][0]
[0][0][0][1][1][1][0][0][0][0]
[0][0][0][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][0][0][0][0][0][0][0]
(0 = false, 1 = true)
I've found a way to combine neighbouring zeros on the horizontal plane like like:
[----------------------------]
[----------------------------]
[----------------------------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[-------][1][1][1][----------]
[----------------------------]
[----------------------------]
The code for achieving this is as such:
for y = 0 to ySize
for x = 0 to xSize
if array[y][x] = 0
set width = 1
for x2 = x + 1 to xSize
if array[y][x2] = 0
width++
else
break
add object at x, y and set width to width
set x = x + width - 1
So it loops the 2D array looking for zeros, and if it finds one, it loops until the end of the row to find where it is no longer a zero.
It then creates an object at the position where it first found a zero, and stretches it to fill the part until it is not a zero.
I want to adapt this code in order to make rectangles instead of long planks, like:
____________________________
| |
| | <------ rect at 0, 0 with size (10, 3)
|____________________________|
| |[1][1][1]| |
| |[1][1][1]| |
| |[1][1][1]| | <------ rect at 6, 3 with size (4, 5)
| |[1][1][1]| |
| |[1][1][1]|__________|
| | |
|_______|____________________| <------ rect at 3, 8 with size (7, 2)
^
|
|
rect at 0, 3 with size (3, 7)
So instead of making 15 horizontal planks, it makes 4 rectangles that surround the ones.
In short, I want to create an algorithm that will, when given an 2D array of ones and zeros, create rectangles around the ones.
For a smaller example:
{
[0][0][0] { 0, 0, 0 },
[0][1][0] { 0, 1, 0 },
[0][0][0] { 0, 0, 0 }
}
Will return the position and dimension of rectangles such as:
[-------]
[-][1][-]
[-------]
{
{0, 0, 3, 1}, //rect at (0, 0) with width 3, height 1
{0, 1, 1, 1}, //rect at (0, 1) with width 1, height 1
{2, 1, 1, 1}, //rect at (2, 1) with width 1, height 1
{0, 2, 3, 1} //rect at (0, 2) with width 3, height 1
}
What should this algorithm look like?
Edit: There should be some effort to minimize number of rectangles used (otherwise, it could just leave it as is).
Also, it doesn't matter if it prefers horizontal or vertical rectangles. Example:
[-------]
[-][1][-]
[-------]
is the same as
_ _
| |[ ]| |
| |[1]| |
|_|[ ]|_|
In the end, both have 4 rectangles surrounding the [1].
Best Answer
I think this is a not so easy problem, when handling more complex arrays, such as :
The real complexity lies in the attempt to use the least possible rectangles. One approach would be to calculate the column of the first '1' appearing in each row. Then, the minimum column is used to create a subarray. For instance :
Then continue iterating from the 1st row. However, I am not sure if this solution finds the smallest number of rectangles.
Another approach would be to start from the point that is the nearest to the center of the 2D array and execute a BFS algorithm, until you find a '1'. Then, this BFS will have created a rectangle and then the next iteration will be executed for the new point that is the nearest to the center. This approach is for sure sub-optimal, since a lot of small rectangles will be created in corners.