在现有的非重叠矩形之间拟合矩形 [英] Fitting a rectangle inbetween existing, non-overlapping rectangles

问题描述

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

I have a problem that can perhaps best be illustrated with windows on a computer screen: create another window, as large as possible, not overlapping any of the existing windows.

换句话说:给定在有限表面(一张纸或一个屏幕)上的N个矩形的集合，找到可以在这些矩形之间拟合的最大矩形. (坐标可以是任意的，因此位图在这里不是可行的解决方案.)

In other words: given a set of N rectangles on a finite surface (a sheet of paper, or a screen), find the largest rectangle that can be fitted inbetween these rectangles. (Coordinates can be arbitrary, so a bitmap is not a viable solution here.)

下面的照片显示了三个矩形(黑色)和可以安装的最大矩形(红色).

The following photo shows three rectangles (in black) and the largest rectangle that can be fitted (in red).

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

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

I have written a naive algorithm for this which considers all pairs of x- and y-coordinates used by the rectangles. It is, unfortunately, O(N^5) because in the worst case each rectangle candidate must be checked against every other rectangle for overlapping.

还有什么更好的吗?

       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

推荐答案

半四叉树方法怎么样?您可以创建一个具有9个属性的节点，即矩形本身，4个矩形，其面积在该节点当前矩形的北，南，东和西可用.最后是4个节点，每个节点在相应区域中都有子树.节点类看起来像这样:

What about semi quad-tree approach? You could create a node with 9 properties, the rectangle itself, 4 rectangles with area that is available north, south, east and west of the node's current rectangle; and finally 4 nodes each having subtree in corresponding areas. Node class would look something like this:

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;
}

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

When creating a new node you should just clip bounding area with lines containing sides of current rectangle. This is not a typical quad-tree. Here subnode's areas may overlap.

另外两个基本动作.首先添加矩形.从第一个实心矩形开始，创建一个节点，然后为剩余的每个矩形将它们添加到树中.要将矩形添加到节点，您应该检查矩形是否与它的任何区域重叠.如果是这样，请将其裁剪到该区域并将其向下推到该节点.如果节点为空(或为null)，请创建一个新节点.

Two more essential actions. First adding the rectangle. Starting with first solid rectangle you create a node and then for each of remaining rectangles you add them to the tree. To add rectangle to node you should check if it overlaps any of its areas. If so, clip it to the area and push it down to that node. If node is empty (or null) create a new one.

最后找到一个最大的矩形.从根节点开始递归地完成此操作.您应该从覆盖所有4个区域的矩形中得到最大的矩形.这很容易，因为您已经将它们作为节点的属性.但是，有一个技巧-如果在该区域中有一个子节点，则应使用最大的rect节点(这是递归).

Finally finding a largest rectangle. This is done recursively starting at the root node. You should get the largest rectangle from those that cover all 4 areas. It is quite easy as you already have them as properties of your node. There is one trick however - if there is a subnode in this area you should use this nodes largest rect (here's the recursion).

这篇关于在现有的非重叠矩形之间拟合矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！