algorithm - Finding rectangles in a 2d block grid

Question

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:

• 4x1 at (4,8)
• 5x1 at (3,10)
• 2x3 at (1,3)
• 2x2 at (6,1)
• 2x2 at (1,11)
• 4x1 at (3,12)

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?

Answer 1

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

1. Run this clever O(WH) algorithm for determining the largest rectangle, but instead of tracking just the single largest rectangle, for each (x, y) location record in a W*H matrix the width and height of (one or all of) the largest rectangles whose top-left corner is (x, y), updating these values as you go.
2. Loop through this matrix, adding each sufficiently-large rectangle in it to a max-heap ordered by area (width * height).
3. Read entries out of this heap; they will be produced in decreasing area order. With every entry read whose top-left corner is (x, y) and which has width w and height h, mark each of the wh locations included in the rectangle as "used" in a WH bit array. When reading rectangles from the heap, we must discard any rectangles that contain "used" squares to avoid producing overlapping rectangles. It's sufficient to check just the four edges of each candidate rectangle against the "used" array, since the only other way that the candidate rectangle could overlap another rectangle would be if the latter rectangle was completely contained by it, which is impossible due to the fact that we are reading rectangles in decreasing area order.

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. (E.g. 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.