在现有的、不重叠的矩形之间拟合一个矩形

Question

我有一个问题，也许可以用计算机屏幕上的窗口来最好地说明：创建另一个尽可能大的窗口，不与任何现有窗口重叠。

换句话说：在有限表面（一张纸或一块屏幕）上给定一组N个矩形，找到可以安装在这些矩形之间的最大矩形。（坐标可以是任意的，因此位图在这里不是可行的解决方案。

下面的照片显示了三个矩形(黑色)和最大的矩形(红色)。

http://www.irstafoto.se/blogmtrl/rectangle-illustration.jpg

我为此编写了一个简单的算法，它考虑了矩形使用的所有x和y坐标对。不幸的是，它是O(N^5)，因为在最坏的情况下，每个候选矩形必须与每隔一个矩形进行重叠检查。

还有更好的吗？

       max_area = 0;
       max_rect = nil

       xc = all rectangle x-coordinates [x1, ..., x6] in picture)
       yc = all rectangle y-coordinates (y1, ..., y6] in picture)
       xc = [0] + xc + [W]; /* W is width of area */
       yc = [0] + yc + [H]; /* H is height of area */

       sort(xc);
       sort(yc);

       for each x0 in xc
           for each x1 > x0 in xc
               for each y0 in yc
               for each y1 > y0 in yc
                       r = rect(x0,y0,x1,y1)
                       if (area(r) > max_area and !overlapping(r))
                           max_area = area(r)
                           max_rect = r

Answer 1

半四叉树方法怎么样？您可以创建一个具有9个属性的节点，矩形本身，4个矩形，其区域位于节点当前矩形的北部、南部、东部和西部；最后4个节点，每个节点在相应的区域都有子树。节点类看起来像这样：

class node 
{
    public var nr:Rectangle;
    public var sr:Rectangle;
    public var wr:Rectangle;
    public var er:Rectangle;

    public var nn:node = null;
    public var sn:node = null;
    public var wn:node = null;
    public var en:node = null;

    public var rect:Rectangle;
}

创建新节点时，应仅使用包含当前矩形边的线剪裁边界区域。这不是典型的四叉树。在这里，子节点的区域可能重叠。

两个更重要的行动。首先html" target="_blank">添加矩形。从第一个实心矩形开始，创建一个节点，然后为每个剩余的矩形将它们添加到树中。要将矩形添加到节点，您应该检查它是否与其任何区域重叠。如果是这样，请将其剪辑到该区域并将其向下推到该节点。如果节点为空（或空），请创建一个新节点。

终于找到一个最大的矩形。这是从根节点以递归方式完成的。您应该从覆盖所有4个区域的矩形中获得最大的矩形。这很容易，因为您已经将它们作为节点的属性。但是，有一个技巧 - 如果此区域中有一个子节点，则应使用此节点最大的矩形（这是递归）。

Answer 2

我的建议是:

独立地对X和Y进行排序，以便您可以将所有角坐标映射到范围[0,2N]内的整数索引。

在缩小坐标中空间被矩形占据的二进制图像中填充黑色。图像大小将为（2N1）x（2N1）。

找到可以放置在白色区域中的最大矩形。这可以按与图像区域成比例的时间完成。（请参阅文章“基于矩形列表的对象描述符：方法和算法”。

然后对于每个最大矩形，计算实际面积，给定真实坐标，并保持最大

这应该是一个完整的O（N²）过程。