6

Screenshot of what I have (on the left) and what I'm trying to accomplish (on the right)

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!

  • I had a somewhat similar problem a while back:https://stackoverflow.com/questions/11002205/find-all-rectangular-areas-with-certain-properties-in-a-matrix However in my case the resulting rectangles could overlap. Perhaps you could adapt that, find all overlapping rectangles of maximum size, then for each region that is covered by multiple rectangles, add it to exactly one of those rectangles. – HugoRune Sep 04 '17 at 19:33
  • just so I fully understand, are the rectangles created from drawing vertical/horizontal lines across a large rectangle and then picking some random created rectangles as 'red' rectangles? – Theo Walton Sep 04 '17 at 23:35
  • No, I start with a sheet with only the red rectangles and then I slice the entire sheet around them. –  Sep 05 '17 at 07:01

1 Answers1

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.

algrid
  • 5,600
  • 3
  • 34
  • 37
  • The problem with blindly merging 2 rectangles is that this meme can arise: http://i.imgur.com/4O1H1a6.png If I happen to by chance merge the blue ones then that prevents the huge white cluster from being formed, which would clearly result in less rectangles in the final list which is a huge priority –  Sep 04 '17 at 21:26
  • @Otopkin In my algorithm on each step you have to merge the pair of rectangles that makes the **largest area**. With that you can also find an example where it's not optimal. I'm just hoping that for your real life application it will be good enough. – algrid Sep 04 '17 at 21:34
  • I'll probably do something along these lines, should give a good enough baseline that I can later fine tune by hand. I looked into a few polygon reduction algorithms, the kind they use for 3d models and such, worst case scenario I can just convert this to a mesh, open it in Blender and use theirs rofl. –  Sep 04 '17 at 22:03