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.

Hellraiser

"Maximum efficiency is not needed, speed is more important." - Huh? I assume that you mean "I don't want the absolute minimum number of rectangles, just something that does a good approximation, quickly"...? – Come

Oh, and have you proved that cycling through each square is your performance bottleneck? – Come

Regarding approximation, yes, that. I'm basically looking for the most balanced solution as far as effectiveness vs. speed goes. Also, yes, i am 100% sure that the cycling is the bottleneck due to Perl being a lot slower than OpenGL itself. – Hellraiser

Is your data static? I.e. is it worth caching? – Analects

Depending on the use it changes roughly between every 3-30 minutes. In fact, this algorithm would be applied during the creation of another cache. The ultimate goal is to get a bounding box to be used in occlusion checks during 3d rendering. – Hellraiser

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

Infallible

Yup, that's what i'll be doing unless someone else comes up with a better solution. :) – Hellraiser

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.

Spurious

That site seems to be having problems staying up, so here's an internet archive mirror: web.archive.org/web/20220717151228/https://www.ddj.com/database/… – Duce

Answer 3

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.

Analects

Yes, this is pretty much what i am looking for. I already thought about doing it 1-dimensionally, but was hoping someone else had already spent time on thinking about how to do it in 2 dimensions. – Hellraiser

Answer 4

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?

Lettered

Added explanation as addendum 3. Thanks for helping me clarify it. :) – Hellraiser

Answer 5

I had to solve a similar problem, my algorithm supports jagged arrays, I have heavily tested and commented it but it's slower than joel-in-gö's suggestion : https://stackoverflow.com/a/13802336

Molloy