How can I reduce a grid of equal sized squares to a minimum set of rectangles?

If I have an arbitrary sized grid of equal sized squares (with no spacing between them), I need to know an efficient way to reduce these into a minimum number of rectangles, for example if each asterisk represents a square, then this could be reduced to one big rectangle:

*****
*****
*****

While this could be reduced to two rectangles:

  ***             ***
*****   =>  **(1) ***(2)
*****       **    ***
  ***             ***

An obvious solution is t开发者_运维百科o collect adjacent squares in each row, then collect adjacent rows which are identical. For my second example this would find three rectangles, which is not optimal.

  *** (1)

***** (2)
*****

  *** (3)

I am wondering if there's a more successful and efficient algorithm to do this.

I've a gut feeling that this problem can be complex... for example consider

   *
   ***
****
   ***
   *

The optimal solution is 4

   B
   BCC
AAAB
   BDD
   B

but i don't find an easy way to foresee by local reasoning that A should stop before last square. In the optimal solution A, C, and D are non-maximal rectangles and only B is maximal. Things can get even more complex for example with:

   *
   ***
****
   ***
   *
 *****
  * *
  * *

where the optimal solution is

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

where only E is maximal. Also looks it's actually easy to build arbitrarily large problems where in the optimal solution all but one rectangles are non-maximal. Of course this doesn't mean IMO that no easy solution exists... like I said it's a gut feeling, but IMO any solver that reasons with maximal rectangles is going to have problems if the absolute minimum is needed.

For a somewhat similar but also different problem (I was searching a minimal covering with non-necessarily-disjoint discs) I used a slow greedy approach always adding to the solution the disc that was contained and covering most not-yet-covered squares. For your problem I'd probably see how it works adding the largest contained rectangle every time... that as the examples above show however this is not going to be in general an optimal solution.

I don't know off the top of my head if there is already an algorithm for this, so I made one up:

Find (xmin,ymin) (xmax,ymax) i.e. the minimum and maximum of the x and y coordinates of the existing squares. This defines a single bounding rectangle enclosing all of your squares.

Find and connect with straight lines concave corners within the bounding rectangle.

Answer to comments: ok, so if we connect all the concave perimeter corners along the grid lines, gradually removing (labeling) the peripheral rectangles, we get the following on the above difficult example:

   A
   XBB
CCCX
   XDD
   X
 EFFFG
  I J
  I J

which, as has rightly been pointed out, is sub-optimal. There are some decisions to be made in which order to pairwise connect the concavities when more than one way is possible. Choose the one resulting in the least number of new rectangles. (See F under the lowest X).

When the splits are finished, we now add another stage of extending (merging) the existing rectangles. Crucially only such merging is to be allowed that does not reduce any of the existing rectangles. Changing the uppermost X to a B would be such a disallowed change because the Xs rectangle has been reduced. This condition guarantees that changes are only in the direction towards the minimum number of rectangles. Continuing with this procedure on the above example, we get:

   X
   XBB
CCCX
   XDD
   X
 FFFFF
  I J
  I J

Which happens to be optimal on this example but in general you may have to do a state-space search using these operations in order to find the global minimum.