需要帮助合并一些矩形

Question

你好，我在左边看到了一堆乱七八糟的东西，它几乎是一组带有一些孔的矩形（用红色标记）。我正在寻找一种方法来组合它们，这样我最终会得到尽可能少的矩形，并且最好让它们中的大部分尽可能接近正方形。看右边的图片，这就是我想要完成的事情，只是更漂亮一点，最好更自动化一点。

我的游戏需要这个，它不会在运行时完成，所以速度不是真正的问题（除非它非常慢，因为我必须在相当大的区域上做）但我已经以前从来没有做过这样的事情，老实说，我什至不知道从哪里开始。

我已经尝试过暴力破解数组，从左上角的正方形开始并进行某种合并，直到没有任何东西可以合并，但它确实没有那么有效，因为它不能考虑合并 3x2 的矩形， 4x3 等..

如果您能指出任何可以处理此类事情的算法或知道如何实现这一点，我们将不胜感激。谢谢！

Answer 1

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

所以你可以试试：

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

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