Need help merging some rectangles

Question

Hi, I have this mess mess on the left, it's pretty much an array of rectangles with some holes (marked in red). I'm looking for a way to combine them in a way that I'll end up with as few rectangles as possible and preferably have most of them will be as close to squares as possible. Look at the image on the right, that's the kind of thing I'm trying to accomplish, just a bit prettier and preferably a bit more automatic.

I need this for a game and it won't be done at runtime so speed isn't really a concern (unless it's extremely slow, because I have to do it on a fairly large area) but I've never had to do something like this before and I honestly have no idea where to even start.

I already tried bruteforcing my way through the array, starting from the top-left square and kind of merging until there's nothing left to merge but it really isn't that efficient since it can't consider merging rectangles 3x2, 4x3, etc..

If you can point me to any algorithms that can handle this sort of thing or have an idea of how this could be accomplished it would be much appreciated. Thanks!

Answer 1

You can try a greedy algorithm. Of course it won't be optimal (well, you didn't define the optimality criterion strictly). But maybe it will perform good enough for your needs.

So you can try:

• Find a pair of rectangles that can be merged with maximum total area
• Replace them with the new one - the result of merge operation
• Repeat until you cannot find a suitable pair

If you also care for resulting rectangles being close to square you can try to maximize something like a * totalArea + (1 - a) * (min_resulting_side/max_resulting_side) with a suitable value for 0 < a < 1.