python - 如何通过算法找到可以与其他矩形一起放入空间的最大矩形？

Question

所以我有一个 6m x 2.25m 的矩形，还有 4 个其他具有静态尺寸但随机放置在全局矩形内的矩形。

我需要一个函数来计算最大矩形的面积，该矩形可以容纳在外部矩形中，并且不会与其他矩形重叠。

我考虑过找出小矩形之间的最大 x 距离，但取决于它们是横向还是纵向，x 可能无法完成这项工作。在这一点上，我相当卡住了，我在网上找不到太多关于这样做的信息，但我确信这对于有经验的编码人员来说是一项非常普通的任务。

更新:这里有一个示例图像来显示我要描述的内容。彩色矩形以静态尺寸随机放置，我想找到可以容纳的最大矩形。

感谢您的宝贵时间!

Answer 1

作为起点。时间和空间复杂度上较小矩形数量的二次方。

高级方法

1) 根据较小子矩形的尺寸(图中紫色线)将大矩形划分为子矩形。最佳矩形的边框始终由这些子矩形组成。

2) 划掉不能成为最终结果一部分的填充子矩形(图中的红色和黄色矩形)

3) 现在我们有一个搜索问题。我们可以使用任何搜索算法(我使用的是 DFS)。您可以对此进行一些优化(例如缓存)，但为了简单起见:

伪代码

frontier = queue(all subrectangles)
largest_area = None

while frontier is not empty: 
    rectangle = pop a rectangle off frontier

    if all subrectangles to the right of rectangle are unoccupied:
        add (rectangle + extra subrectangles to the right) to frontier
        largest_area = max(area of new rectangle, largest_area)
    else if all subrectangles below rectangle are unoccupied:
        add (rectangle + extra subrectangles below) to the frontier
        largest_area = max(area of new rectangle, largest_area)

print largest_area

说明

说矩形是绿色矩形。可能的后继状态是添加带有蓝色星星的子矩形或添加带有粉色星星的子矩形。然而，粉红色的星星与黄色矩形重叠，所以我们不能添加它。