18
\$\begingroup\$

enter image description here

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?

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Can you tell us a bit about where these rectangles come from? Do they tend to (roughly) align with any underlying grid, or share some common building block, or some smallest "atom" rectangle? Can they be rotated? This looks like the kind of problem that can be very thorny in the most general case, but may get a lot easier if we can exploit some constraints or commonalities in your particular scenario. \$\endgroup\$
    – DMGregory ♦
    Commented Sep 8, 2016 at 22:23
  • \$\begingroup\$ There is an underlying grid of squares (like a checkerboard) and each rectangle is sharing boundaries with those underlying squares. i.e. you can use an integer to describe top/bottom/left/right of every rectangle. Therefor they cannot be rotated in angles not divisible by 90 degrees. Also the NxM grid is fully populated with rectangles - there are no uncovered grid positions. \$\endgroup\$
    – xaxxon
    Commented Sep 8, 2016 at 22:27
  • \$\begingroup\$ I'm just trying to avoid the case that looks like the example above (from a coloration perspective), but it's made up of a ton of 1x1 rectangles and I'm processing each one of them when I can be handling the space in many fewer calls. \$\endgroup\$
    – xaxxon
    Commented Sep 8, 2016 at 22:35
  • \$\begingroup\$ I'm guessing some sort of "just start somewhere and keep trying bigger and bigger rectangles in one dimension (say vertically) until you hit a color border, then grow the other dimension (horizontally) until you hit a border. Then try horizontally first. Then maybe try only squares (growing diagonally). But not sure if simply selecting the largest of the above 3 possibilities is the right approach. \$\endgroup\$
    – xaxxon
    Commented Sep 8, 2016 at 23:08
  • \$\begingroup\$ Is it acceptable to split an existing rectangle, if it results in fewer rectangles in the end? Or should the algorithm only ever merge? Also, is total count the only criterion, or do you prefer squarer shapes over long skinny slivers / larger rectangles over smaller ones? \$\endgroup\$
    – DMGregory ♦
    Commented Sep 8, 2016 at 23:23

1 Answer 1

Reset to default
19
\$\begingroup\$

In an unrelated search, I just stumbled on this GitHub repo for optimal rectangle decomposition, using the "bipartite matching algorithm". It likely does a better job than what I've described below.

In the event that the link rots, here are the sources it cites for more information on the algorithm:

  • Jr. W. Lipski, E. Lodi, F. Luccio, C. Mugnai, L. Pagli. (1979) "On two-dimensional data organization II". Fundamenta Informaticae
  • E. Kawaguchi, T. Endo. (1980) "On a method of binary-picture representation and its application to data compression" IEEE Transactions on Pattern Analysis and Machine Intelligence
  • T. Ohtsuki. (1982) "Minimum dissection of rectilinear regions" IEEE Conference on Circuits and Systems
  • T. Suk, C. Hoschl, J. Flusser. (2012) "Rectangular Decomposition of Binary Images",Advanced Concepts for Intelligent Vision Systems. LNCS Vol. 7517

Older 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.

Example converting rectangles into grid cells and back

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.

Decomposing a polyomino into horizontal runs, then merging vertically

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:

Example of a case with a 3-rectangle solution, where the method above finds 4

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.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the awesome answer! that solution looks quick enough that I could run it a few different directions and pick which one seems best --horizontal left->right, horizontal right->left, and then vertical each way, too. \$\endgroup\$
    – xaxxon
    Commented Sep 9, 2016 at 1:40
  • 2
    \$\begingroup\$ The trouble is we can construct shapes that will mislead the algorithm from every sweep direction. Those might not be likely to show up in real use, but it still bugs me. I think there's a simple fix yet... Something like noting in each run, whether there are concave corners above it mid-run. Then if a subsequent run ends at exactly such a point, we backtrack through the runs above splitting them vertically. I haven't sorted out the full details though. \$\endgroup\$
    – DMGregory ♦
    Commented Sep 9, 2016 at 1:44
  • 1
    \$\begingroup\$ Also, I'm not sure why the flood fill step is necessary. When going from a grid positino to a long skinny rectangle, you can simply walk the full row or column of the grid (whichever way you're going) to create those 1xN rectangles. No need to ever know the polyomino, right? \$\endgroup\$
    – xaxxon
    Commented Sep 9, 2016 at 1:47
  • \$\begingroup\$ You're right, the flood fill isn't a necessary step. I included it to justify focusing on just one coloured region at a time in the subsequent steps, but you could easily apply the row scan method to multiple coloured regions interleaved. The perimeter-based method needs to work on the perimeter of one shape at a time though. \$\endgroup\$
    – DMGregory ♦
    Commented Sep 9, 2016 at 15:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .