3

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

4
  • 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.
    – Dave Chen
    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.
    – Dave Chen
    Mar 26, 2015 at 23:27

2 Answers 2

1

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.