Finding rectangles in a 2d block grid

Let's say I have a grid of blocks, 7x12. We use the colors '*','%','@' and an empty cell '-'.

1 2 3 4 5 6 7
- - - - - - -  1
- - - - - - -  2
% % - - - - -  3
% % - - - - *  4 
% % - - - @ %  5
@ @ @ - - @ %  6
@ @ * * * - *  7
* * * % % % %  8 
% @ @ % * * %  9
% @ % % % % %  10
* * * % % @ @  11
* * @ @ @ @ *  12

I want to find rectangles in this grid of a certain minimum size, and the biggest I can find and then smaller until no rectangles greater or equal to the minimum size can be found.

In this example, consider the minimum size 1x4, 4x1, 2x2 so a 1x3 is not valid but a 2x3 is. If we want the biggest rectangles we find the following:

Note that rectangles cannot be in each others space, they cannot overlap. For example the 2x2 rectangle at (4,10) is not mentioned because it would overlap the 5x1 rectangle at (3,10).

All are perfectly valid rectangles: they are equal or greater that the minimum size and all the blocks per rectangle are of the same color.

What I want is to do this programmatically. When you tell someone to find rectangles in a grid, he finds them immediatly, without any thinking about it. The question is, how can I write an algoritm that does the same?

I considered bruteforcing but I need the algorithm to execute as fast as possible as it will need to be executed a lot in a very small time frame on a limited (mobile) device.

I see a lot of questions on the internet about rectangles, but I'm suprised this one hasn't been asked anywhere yet. Am I thinking too difficult or has no one ever wanted to do something like this?

Call the width and height of the input array W and H respectively.

This approach is "greedy" insofar as it won't guarantee to choose the largest sequence of rectangles overall if there are multiple ways to carve a solid coloured region into maximal rectangles. (Eg it might be that there are several rectangles whose top-left corner is at (10, 10) and which have an area of 16: 16x1, 8x2, 4x4, 2x8, 1x16. In this case one choice might produce bigger rectangles "downstream" but my algorithm doesn't guarantee to make that choice.) If necessary you could find this overall optimal series of rectangles using backtracking, though I suspect this could be very slow in the worst case.

The maximum-rectangle algorithm I mention is designed for single-colour rectangles, but if you can't adapt it to your multi-colour problem you can simply run it once for each colour before starting step 2.

I had to solve a very similar problem for my first person shooter. I use that in input:
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ][ ]
[ ][X][X][X][X][X][X][X]
[ ][ ][X][X][X][X][ ][ ]
[ ][X][X][X][X][ ][ ][ ]
[ ][X][X][X][X][ ][ ][ ]
[ ][ ][X][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

I get that in output:
[ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][A][ ][ ][ ][ ]
[ ][B][G][G][G][F][E][E]
[ ][ ][G][G][G][F][ ][ ]
[ ][D][G][G][G][ ][ ][ ]
[ ][D][G][G][G][ ][ ][ ]
[ ][ ][C][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ]

This schema is better. The source code (under GNU General Public License version 2) is here, it is heavily commented. You may have to adapt it a bit to your needs like the one suggested by j_random_hacker.

Note: this operates under the assumption that you're trying to find the biggest k rectangles.

We know we must, in the worst case, look at every node in the grid at least once. This means our best-case worst-cast is O(len*wid) .

Your brute-force is going to be O(len*len*wid*wid) with the naive approach of "Checking for rectangles at a point is O(len*wid) , and you do that O(len*wid) times.

It may be that you find this to not be the case, as each time you find a rectangle, you have potential to reduce the problem space. A brute force approach of "check each rectangle" I feel is going to be the best approach. There are things you can do to speed it up, though.

Basic algorithm:

for(x = 1 .. wid) {
    for(y = 1 .. len) {
        Rectangle rect = biggestRectOriginatingAt(x,y);
        // process this rectangle for being added
    }
}

Rectangle biggestRectOriginatingAt(x,y) {
    area = areaOf(smallestEligibleRectangle); // if we want the biggest k rect's, this
                                              // returns the area of the kth biggest
                                              // known rectangle thus far

    for(i = 1 .. area) {
        tempwid = i
        templen = area / i

        tempx = x + tempwid
        tempy = y + templen

        checkForRectangle(x,y,tempx,tempy); // does x,y --> tempx,tempy form a rectangle?
    }

}

This allows you to get big performance gains towards the end of your large searches (if it's a small search, you don't gain as much but you don't care because it's a small search!)

This also doesn't work as well for more random distrobutions.

Note that neither of these approaches reduce the worst case. But, they do reduce the real-world expected running time.

上一篇: 二维矩阵中1的最大矩形

下一篇: 在2d块网格中查找矩形