geometry - Algorithm for "healing" multiple rectangles into a smaller number of rectangles?

Say I have a grid of rectangles of different shapes and colors and I want to reduce (reasonably close to optimal is fine, optimal is not necessary) the number of rectangles to represent the same layout of colors.

The image above is a very simplified case and the whitespace between the rectangles is for visualization only -- they would actually be tightly packed.

What is an approach or algorithm name (happy to google) that can help me do this?

Answer

First, we can convert your source rectangles to cells in your underlying grid, to make the input more uniform. (Effectively rasterizing the problem)

This will let us find optimizations that might not be obvious when working directly with the source rectangles - particularly when it involves splitting multiple source rectangles to recombine them differently.

Next we can find connected regions of the same colour, using depth-first-search or flood filling algorithms. We can consider each connected region (a polyomino) in isolation - nothing that we do to a different region needs to influence this one.

Effectively we want to find a way to dissect this polyomino into rectangles (unfortunately most of the literature I can find is about the opposite problem: dissecting rectangles into polyominoes! This makes it tricky to search for leads...)

One straightforward method is to combine horizontal runs of adjacent squares into long skinny rectangles. Then we can compare against the row above and combine if our run starts & ends match up - either as we finish each run/row, or as we consider each cell to add to the current run.

I don't know yet how close this method gets to optimal. It seems it can run into a bit of trouble when a row it hasn't considered yet suggests a different split than the rows it's seen so far:

Detecting when a run/rectangle is exactly covered by runs above & below, then splitting it and merging them will solve this particular case, but I haven't explored how general the problem is.

I've also looked at methods where we walk the perimeter of the polyomino, and cut across anytime we encounter a concave corner, but this approach looks more error-prone to me. Getting optimal results seems to require prioritizing cuts that join two concave corners, and shapes containing hollows need special handling, so the row scan method seems to have the simplicity advantage.

One more method I'm looking at is to take the first run found in the top row & extend it down as far as you can. Then take the first run in the top row of what's left... This gets tripped-up on inverted T shapes though, so it's not optimal either.

I feel like there's probably a way to use dynamic programming to find the optimal split, but I haven't found it yet.