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].
