需要帮助合并一些矩形

Question

嗨,我左边有乱七八糟的混乱,它几乎是一些带有一些孔的矩形阵列(标记为红色).我正在寻找一种方法来组合它们,我将尽可能少的矩形结束,并且最好使它们中的大多数尽可能接近正方形.看看右边的图像,这就是我想要完成的事情,只是有点漂亮,最好是更自动一点.

我需要这个用于游戏而且它不会在运行时完成所以速度并不是真正的关注点(除非它非常慢,因为我必须在相当大的区域上进行)但我从来没有做过什么喜欢这样,我真的不知道从哪里开始.

我已经尝试通过数组进行强制执行,从左上角的方块开始并且有点合并,直到没有任何东西可以合并,但它实际上效率不高,因为它不能考虑合并矩形3x2,4x3等.

如果您能指出任何可以处理此类事情的算法,或者想知道如何实现这一点,那将非常感激.谢谢!

Answer 1

你可以尝试一下贪心算法。当然它不会是最优的（好吧，你没有严格定义最优标准）。但也许它的性能足以满足您的需求。

所以你可以尝试：

• 找到一对可以合并且总面积最大的矩形
• 将它们替换为新的 - 合并操作的结果
• 重复直到找不到合适的一对

如果您还关心生成的矩形接近正方形，您可以尝试最大化一些值，例如a * totalArea + (1 - a) * (min_resulting_side/max_resulting_side)使用 0 < a < 1 的合适值。