如何排列N个矩形以覆盖最小面积。
如何排列N个矩形以覆盖最小面积。
我有N个矩形，每个矩形的尺寸都是随机的（宽度和高度都是随机的）。所有矩形都平行于X轴和Y轴。我正在寻找一种算法，帮助我将这些矩形并排排列，使得得到的包围矩形的面积最小，并且输入矩形周围/之间的潜在间隙尽可能小。矩形不能旋转，也不能重叠。\n（我需要自动排列游戏精灵，以便我可以创建精灵表并保存从动画师那里得到的各种图像的精灵位置。）\n例如：\n+---+ +----------+\n| 1 | | 2 |\n+---+ +----------+ +----------+.. +---+----------+\n | 2 |.. | 1 | 2 |\n+--------+ ===> +--------+-+-+ vs +---+----+-----+\n| | | | 1 | | |......\n| 3 | | 3 +---+ | 3 |......\n+--------+ +--------+.... +--------+......\n 未使用：8 未使用：18\n未使用的空间在图示中用点（.）表示。由于第一种结果具有较小的未使用空间的包围矩形，因此最好找到这种排列的输入矩形。\n是否已经有一种算法可以帮助解决这个问题？我进行了很多搜索，但大多数结果与寻找最小包围矩形或确定N个矩形是否覆盖了预定区域有关。
从上面的内容可以看出，问题的出现原因是现有的解决方法在放置矩形时存在一些问题，导致最后的结果不够优化。为了解决这个问题，提出了一种改进的方法。改进的方法主要包括两个方面的修改：一是在扩展包围盒的时候，不是按照最小面积来扩展，而是按照剩余矩形所需面积的最小值来扩展；二是在选择下一个矩形时，不是选择面积最大的矩形，而是选择边长最大的矩形。这样做的目的是为了在早期给予更多的空间，并防止在最后一刻总是没有足够的空间留下大部分空白边缘。
下面是整理的
在放置矩形以覆盖最小面积的问题上，现有的解决方法存在一些问题，导致结果不够优化。为了改进这个问题，有人提出了一种修改方法。这种修改方法包括两个方面的改进。首先是在扩展包围盒时，不再按照最小面积来扩展，而是按照剩余矩形所需面积的最小值来扩展。其次是在选择下一个矩形时，不再选择面积最大的矩形，而是选择边长最大的矩形。这样的改进方法的目的是为了在早期给予更多的空间，并防止在最后一刻总是没有足够的空间留下大部分空白边缘。
原有的解决方法中，扩展包围盒时是按照最小面积来扩展的，这可能导致在放置矩形的过程中，包围盒的面积一直很小，没有给予矩形足够的空间。而修改后的方法则是按照剩余矩形所需面积的最小值来扩展包围盒，这样可以提前给予更多的空间，使得矩形的放置更加合理。
另外，原有的解决方法中选择下一个矩形时是按照面积最大的矩形来选择的。然而，面积最大的矩形并不一定是最适合的选择。修改后的方法则是选择边长最大的矩形，这样可以更好地填充空间，避免在最后一刻没有足够的空间留下大部分空白边缘。
通过以上的修改，可以使得矩形的放置更加合理，从而覆盖的面积更小。这种改进方法可以提高算法的效果，得到更优化的结果。