How to divide an area composed of small squares into bigger rectangles?

Question

Where would i go to look for algorithms that take a 2d grid of values that are either 0 or 1 as input and then identifies all possible non-overlapping rectangles in it?

In a more practical explanation: I am drawing a grid that is represented by a number of squares, and i wish to find a way to combine as many adjacent squares into rectangles as possible, in order to cut down on the time spent on cycling through each square and drawing it.

Maximum efficiency is not needed, speed is more important.

Addendum: Apparently what i am looking for seems to be a technique called Tesselation. Now i only need to find a good description for this specific case.

Addendum 2: The boundary of the "1" squares will be irregular and in some cases not even connected, as the distribution of "1" squares will be completely random. I need these irregular shapes to be identified and split up into regular rectangles.

Correct answer: To get the best balance between speed and efficiency it is optimal to use the grid data to fill a quad-tree with each node having a status value of either empty/partly filled/filled.

Answer 1

So you are looking for the rectangular boundary of the 'ON' squares?
Do you want the inner or outer bound?
ie. Must the boundary only have 'ON' squares or do you want the rectangle to contain all the 'ON' squares in a group?

Answer 2

As you are not looking for the minimum number of squares I would suggest using a compromise that still keeps your algorithm simple.

What the best solution is depends on your data, but one simple alternative is to just collect boxes along one row. I.e:

0 0 1 1 1 0 0 0 1 1 1 1 0

Will result in:

skip 2
draw 3
skip 3
draw 4
skip 1

This will reduce the number of calls to draw box without any need of caching (i.e you can build your boxes on the fly).

If you want to create bigger boxes I would suggest a backtracking algorithm there you find the first 1 and try to expand the box in all directions. Build a list of boxes and clear the 1:s as you have used them.

Answer 3

I've done something similar for a quick-and-dirty voxel visualization of 3d boxes with OpenGL.

I started from the top left box and stored the empty/filled flag. Then I tried to expand the rectangle to the right until I hit a box with a different flag. I did the same in the down direction.

Draw the rectangle, if it is filled.

If there are boxes remaing, recursivly repeat the procedure for all three remaing rectangles induced by the last rectangle, which are right, bottom and bottom right:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 4

Also, http://mathworld.wolfram.com has myriad algorithms for all sorts of cool things. Check 'em out :)

Answer 5

Have a look at this article from Dr Dobb's Portal on finding a maximal rectangle in your situation. It is a very detailed discussion of an extremely efficient algorithm, and I think that repeating it iteratively would possibly solve your problem.