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

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 2

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.