Suppose you have a grid of size R * C of boolean values. What is the most efficient technique for dividing the grid into the smallest number of rectangles that include only false values? Obviously, there can be multiple solutions that solve the problem producing the same minimum number of rectangles. Pseudocode would be helpful. I'm thinking that the solution may be related to dynamic programming, but unfortunately, DP wasn't my strong suit in college, and my knowledge of it is a bit rusty at this point anyway.
Thanks, Mallory <pre> Example: 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 One solution would be: rect(0,0,1,4) rect(1,0,1,2) rect(2,0,1,1) rect(2,2,1,2) rect(4,1,3,3) rect(5,0,2,1) </pre> Background on my specific problem: In case you were wondering, I need an efficient algorithm to make the fewest number of calls to draw subrectangles of the screen where motion isn't ocurring. If I draw each cell, I end up with 3600 draw calls per frame for a 60 * 60 grid. With my optimizations so far, which don't use DP, I've gotten the number of draw calls per frame down to an average of 65, but I think further optimization can improve this. FWIW, my current technique is to examine each column, if all values are 0, then draw the whole column in one call. if not, examine each cell in the column, finding contiguous blocks of zeros in the column, and drawing each contiguous block of zeros with one call. Obviously a DP solution would yield much better results. Any ideas?
