# How to draw rectangles for 2D arrays

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

• Interesting question. Do you have any criteria around the rectangles you are looking to build? In other words, should they maximize area? Should the algorithm minimize the number of rectangles generated? Mar 24, 2015 at 23:46
• @RandallCook It should try to use as few rectangles as possible. I've edited my question to better show this. Mar 24, 2015 at 23:53
• This is not homework? Mar 26, 2015 at 23:27
• Nah, but I wonder how this could be a computer science hw. Mar 26, 2015 at 23:27

I think this is a not so easy problem, when handling more complex arrays, such as :

``````[0][0][0][0][0][0][1][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][1][0][0]
[0][0][0][0][0][1][0][0][1][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][1][0][0][0]
[0][0][0][0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0]
[0][0][0][1][0][0][0][0][0][0]
``````

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 :

``````[0][0][0][0][0][0][1][0][0][0] (6)              |--------|0][0][0][1][0][0][0]
[0][0][0][0][0][0][0][0][0][0] (-1)             |        |0][0][0][0][0][0][0]
[0][0][0][0][1][0][0][0][0][0] (4)              |        |0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][1][0][0] (7)              |        |0][0][0][0][1][0][0]
[0][0][0][0][0][1][0][0][1][0] (5) -> min=3 ->  |        |0][0][1][0][0][1][0] --> ...
[0][0][0][0][0][0][0][0][0][0] (-1)             |        |0][0][0][0][0][0][0]
[0][0][0][0][0][0][1][0][0][0] (6)              |        |0][0][0][1][0][0][0]
[0][0][0][0][1][0][0][0][0][0] (4)              |        |0][1][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0][0] (-1)             |        |0][0][0][0][0][0][0]
[0][0][0][1][0][0][0][0][0][0] (3)              ---------|1][0][0][0][0][0][0]
``````

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.

I could see this being a recursive function in which you seek the top-left corner of the next possible rectangle. Scan right and down, keeping track of the new rectangle width and height to determine the length to check in your next scan row/column. When you've hit on both left edge and bottom edges, add result to result list, mark those "cells" as used, and reiterate. When you find no empty cells, you're done.