矩形覆盖

这里有一个分而治之的算法。一般情况下,案件的复杂程度是非常好的,我想说这是类似的 O(n log MaxCoords) O(n log n) 平均来说。

我想不出一个扫描线的解决方案,但对于我尝试过的测试来说,这是非常快的。

基本上,在蓝色矩形上使用递归函数。首先检查蓝色矩形是否被其他矩形完全覆盖。如果是,我们就完了。如果不是,则将其分成4个象限,并递归调用这些象限上的函数。所有4个递归调用都必须返回true。我包括一些绘制矩形的C代码。您也可以将其更改为使用更大的值,但在这种情况下请删除绘图过程,因为这些过程将永远需要。我已经用一百万个矩形和一个10亿边的正方形来测试它,这样它就不会被覆盖,并且给出了答案( false )在四核上花了大约一秒钟。

我已经在随机数据上测试过了,但似乎是正确的。如果结果不是这样,我就删除这个,但也许它会让你走上正确的道路。

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    List<Rectangle> Rects = new List<Rectangle>();

    private const int maxRects = 20;

    private void InitRects()
    {
        Random rand = new Random();

        for (int i = 0; i < maxRects; ++i) // Rects[0] is the model
        {
            int x = rand.Next(panel1.Width);
            int y = rand.Next(panel1.Height);

            Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y))));
        }
    }

    private void DrawRects(Graphics g)
    {
        g.DrawRectangle(Pens.Blue, Rects[0]);
        for (int i = 1; i < Rects.Count; ++i)
        {
            g.DrawRectangle(Pens.Red, Rects[i]);
        }
    }

    private bool Solve(Rectangle R)
    {
        // if there is a rectangle containing R
        for (int i = 1; i < Rects.Count; ++i)
        {
            if (Rects[i].Contains(R))
            {
                return true;
            }
        }

        if (R.Width <= 3 && R.Height <= 3)
        {
            return false;
        }

        Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));

        return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight);
    }

    private void Go_Click(object sender, EventArgs e)
    {
        Graphics g = panel1.CreateGraphics();
        panel1.Hide();
        panel1.Show();
        Rects.Clear();

        InitRects();
        DrawRects(g);

        textBox1.Text = Solve(Rects[0]).ToString(); 
    }

你在正确的轨道上扫线。从概念上讲,我们希望检测模型与扫描线的交点何时不被其他矩形覆盖。高级模板是将每个矩形分解为一个“左边缘”和一个“右边缘”事件,按x坐标对事件进行排序(如果矩形闭合,则将左置于右之前,如果矩形打开,则将右置于左之前),然后在O(logn)时间内处理每个事件。这基本上是家庭作业,所以我不会再说了。

这里有一个通用算法

1. 整个模型有没有长方形?
   如果是的话,你就完了
2. 如果没有,是否有任何矩形部分覆盖模型?
   如果是
3. 
   如果2。或者3个。如果答案是否定的,那么答案就是否定的,否则就是肯定的

现在的问题是如何有效地做到这一点。上面的步骤可以在所有多边形上的一个循环中完成,所以我认为您看到的是O(n)时间。

如果您需要创建有效的算法来测试多个模型,或者如果您必须优化以获得尽可能快的答案(以准备数据为代价),那么您正在寻找一种结构,该结构允许快速回答矩形与矩形相交(或包含)的问题。

例如,如果你使用 kd-trees

我的猜想是,这个并集可以用O(k logk)来计算,所以如果k很小,那么你看的是O(logn),如果k与n相当,那么它应该是O(k logk)。

另请参见 this 问题。

编辑:

更详细地说,根据k<<n或k与n相当,我们有两种情况

• 登录到 find a range 在kd索引树(矩形)中,
• f(k)求交并的多项式时间

总数是O(k+logn+f(k)),它直接等于O(logn),因为大O只依赖于增长最快的项。

在这种情况下,算法更重要的部分是找到多边形。

b) 在k与n相当的情况下,我们必须研究交并算法的复杂性
如果k足够大,该算法就不再是求与矩形相交的矩形的算法,而更像是求多边形并集的算法。

但是,我相信kd树也有助于找到线段的交集(这是构建并集所必需的),所以即使是算法的这一部分也可能不需要k^2时间。 此时,我将研究计算并集面积的有效算法。

有一个小问题 O(N^2) 类似于所提出的“光栅”方法的方法。因为所有的矩形都是轴平行的,所以最多只能有 2N 不同的x和y维度。对所有x和y排序并重新映射: x_i -> i . 所以现在你有一个 2N x 2N 矩阵,你可以很容易地使用天真的 O(N^2) 算法。

好吧,现在看来我晚上都睡不着,因为我想到这个问题。。。但似乎我终于得到了一个 O(n对数n) 溶液,in 平均的 病例(但与对照组相比,出现病理输入的几率降低) @lVlad ).

我们都知道 技术。确保 O(n log n) 使用它,我们通常关注两点:

• 这个 分 和 应该是 O(n)
• 存在C>1,这样子问题的大小在每一步都减少一个系数C(在整个问题中保持不变)

考虑到这些约束,我详细阐述了下面的算法,这让人想起 qsort ,从而遭受相同的陷阱(即分形输入)。

算法

1. 剪辑 :我们只考虑 red 与…相交的 blue ,它们被插入哈希集中以删除重复项--> O(n)
2. 数据透视选择 :稍后详细介绍-->
3. 隔板 ^d级 分区,其中一个为轴,d为尺寸(d=1表示线段,2表示矩形,3表示立方体等)
4. 重新划分 :我们把 红色 在分区中,应用剪裁技术,请注意 可能会在不同的分区中给出几个块
5. 递归 :我们递归地(从步骤2开始)应用于每个分区,从填充最少的分区开始,一旦一个分区没有被覆盖就停止

这个 数据透视选择 是算法的基石,如果分区裁剪不当,则无法达到所需的复杂度。此外,它必须在 O(n) . 到目前为止,我有两个建议:

• Maximum Area :使用面积最大的矩形,因为这意味着分区之后的面积将最小,但是它很容易被忽略
• Median of 3

我提议把它们混在一起:

• 选取3个面积最大的元素,选择中间带,在轴上使用
• 如果在重新分区之后发现其中一个分区填充了多个N/C(待定制)元素,则随机选取3个元素,选择中间值,然后进行重新分区(此处不勾选)

实施的另一个方面是 尾巴 关于递归。就像 很可能这种算法对于小型计算机是低效的 n . 我建议使用 introsort 不 小于12,则改用以下算法:

• 对于每个轴,投影每个轴 红色 在轴上(仅边缘)并对其排序(ala introsort)
• 这定义了n的光栅 区域,检查每个区域是否被覆盖

维度不可知

该算法被形式化地定义为适用于任意给定维,具有相同的渐近复杂度 平均O(n log n)

病理输入

就像 它的模型是明智的阶乘输入。阶乘输入是指:

1.......6...9.11.13

每当你选择你的时间间隔的平均值时,所有的元素都在它的一边。

有了这样的投入,即使选择中位数3也不太可能产生非常好的削减。

编辑:

我将用一个小方案来展示分区的思想,如下所示 注意到有点模糊。

+----------------+----+---------+
|       1        | 2  |   3     |
+----------------+----+---------+
|       8        | P  |   4     |
+----------------+----+---------+
|       7        | 6  |   5     |
+----------------+----+---------+

好的,我们检查覆盖范围的矩形现在被分成9个子矩形。我们忽略P,它是我们的轴心。

现在,我们真的希望每个子矩形被较少的 红色 比 N . 轴心被选为中心的重心,因此这意味着如果我们的“随机”选择成立的话,大约有 红色 s在枢轴的每个方向上居中。

我很高兴如果有人能把这一点正规化,我是一个工程师,而不是一个计算机科学家,我的数学落后于。。。

我一直在想,我想我终于明白了 @algorithmist 意思是 sweep line . 然而 sorting 运营意味着我有:

• O(n log n) 在里面 平均的
• O(n**2) 最坏的情况

扫描线

首先,我们需要一些分类,因为我们的 sweep line 将包括走一个有序的集合。

此有序集将具有 top 和 bottom 每行 red s、 只要他们在 顶部 底部 blue . 这把我们的空间分成(最多) n*2 水平条。

现在,我们需要确保 strip ,整个 已覆盖,并且此操作的 O(log n) 复杂性,如果我们有(每一条带)一个覆盖区间的列表,这是可以做到的。 这是“事件” @算法学家 是指

为了处理这个事件,我们将使用下面描述的二叉树来处理添加或删除一个矩形 O(对数n) 操作并产生树所覆盖的最右边的间隔,我们用它来判断 蓝色 是否覆盖。

二叉树

首先,我要索引 红色 矩形。我们使用以下函数对它们进行排序:

def __lt__(lhs, rhs):
  return (lhs.left <  rhs.left)
      or (lhs.left == rhs.left and lhs.right < rhs.right)

然后我将创建一个专用的二叉树。

• 一定会的 N 叶子,每一片代表 红色 矩形,表示它的存在或不存在。它们是根据索引排序的。
• 每个中间节点的值都是其子节点覆盖的最右边的间隔

处理“代码块不能跟随列表”错误:

class Node:
  def __init__(self):
    self.interval = []
    self.left  = None
    self.right = None

现在我们有两种可能,假设孩子们 [a,b] [c,d] :

• 如果 c <= b [a,d]
• 否则就可以了 [c,d]

        _ [1,9] _
       /         \
   [1,7]         [6,9] <-- Special node merge
   /   \         /   \
  /     \       /     \
[1,3] [2,7]   [3,5] [6,9]

特殊节点忽略 [3,5] 因为这不是最右边的间隔。理由是矩形是有序的:

• 右边没有矩形 [6,9] [5,6] 从之后开始的间隔 6
• 左边的矩形 [3,5] 3 所以如果他们把失踪的人 [5,6] 他们会掩护的 [3,5] 无论如何

根可能不表示覆盖的确切间隔集:只显示覆盖的最右边的间隔。但是,我们完全可以判断 蓝色 是否完全覆盖!

此树上有两个可用操作:

• 将矩形标记为存在
• 将矩形标记为不存在

• 如果矩形已处于此状态,则不执行任何操作

递归位需要 . 这是平衡二叉树的一个经典性质。一旦完成了,我们就得到了根所覆盖的最右边的间隔,这个间隔足以判断 蓝色 段是否完全覆盖。

复杂性

• 我们有 O(n) 事件
• 每个事件都在 O(对数n)

这就产生了 O(n对数n) 核心部分。

sort 操作:

• 一个用于分类事件(用于扫描线)
• 另一个用来分类矩形(对于二叉树)

每个人都应 在里面 平均的 ,但可能退化为 在最坏的情况下,取决于所使用的排序算法。

很难知道你在找什么,但对我来说这听起来像是 R-tree 可能有用吗?

如果数据表示为光栅,则一种算法很简单:

1. 创建一个表示模型(即蓝色)矩形的布尔数组。将所有元素设置为FALSE(表示“未覆盖”)
2. 对于每个红色矩形(忽略那些不能与蓝色重叠的),如果数组中的所有元素都在红色矩形内,则将它们设置为TRUE。
3. 最后,检查数组的每个元素是否都设置为TRUE。

如果数据是矢量的,就有点复杂了。首先定义一个函数,返回表示两个矩形相交(如果有的话)的矩形。这很简单。然后继续:

1. 创建一个名为“UnCoveredRectangle”的变量,该变量被初始化为与蓝色矩形相同。

2. 再说一次,只需注意与蓝色矩形相交的红色矩形。对于每个红色矩形,计算矩形与未覆盖矩形的交集。交叉口将导致以下情况之一:

   2.1交点等于未覆盖的转角。工作完成了。

3. 如果在UnCoveredRectangle的(部分)区域被发送到0之前用完了红色矩形,那么就完成了。

好吧,我还不知道这个算法的复杂性,但是除非矩形的数目很大,否则我不会太担心,尽管@den可能是。我遗漏了很多细节。我不能像@den那样画漂亮的图表,所以你得自己画出来。

注意 :这不是O(n logn),更像O(n^2)。然而,这是一个解决办法。如果O(n logn)是一个要求,则可能不是答案。

1. 创建左边缘和右边缘的所有唯一X坐标的列表(在同一列表中)
2. 构建此列表时,对于每个坐标,还将矩形列表与其关联,并在此列表中指示与列表关联的X坐标是矩形的左边缘还是右边缘
3. 对坐标列表进行排序,使其从左到右升序
5. 遍历坐标列表,并为其处理关联的矩形列表
6. 关联列表中表示为以坐标为左边缘的所有矩形都应添加到您在4中创建的列表中。
8. 实际上,添加和删除的顺序应该是相反的,首先要删除右边缘矩形,然后添加所有左边缘矩形
9. 现在,在从4中创建的列表中删除矩形之前,您需要处理它们。通过将它们视为“子矩形”来处理它们。它们的“新”左边缘坐标是您在循环的上一次迭代(在5中)中处理的X坐标,新的右边缘是当前正在处理的X坐标

因此,输出应为:

1. X=1..2,矩形=A
3. X=3..4,矩形=A,B,C
4. X=4..5,矩形=A,C
5. X=5..6,矩形=C

让我来说明目前的进程

+-------------------+
|A                  |
|        +----------+-----+
|        |C         |     |
|  +-----+----+     |     |
|  |B    |    |     |     |
|  |     +----+-----+-----+
|  |          |     |
+--+----------+-----+
   |          |
   +----------+

^  ^     ^    ^     ^     ^
1  2     3    4     5     6  <-- X-coordinates

关联矩形:

1. 左:A,右:(无)
2. 左:B,右:(无)
4. 左:(无),右:B
5. 左:(无),右:A
6. 左:(无),右:C

L=[] ,并开始处理坐标和关联的矩形:

X=1

列表为空,无需处理 没有要删除的内容 加A:L=[A]

X=2

列表包含矩形,将列表处理为左边缘为X=1,右边缘为X=2的矩形(到目前为止我们处理的两个坐标),并使用它们的原始顶部和底部坐标。 没有要删除的内容。 加上B:L=[A,B]

X=3

列表包含矩形,以相同的方式处理列表(A和B),将其视为临时具有X=2和X=3的左右坐标,并使用其原始的顶部和底部坐标。 没有要删除的内容 加上C:L=[A,B,C]

按上述方法处理三个矩形,临时左右坐标为X=3和X=4 删除B:L=[A,C] 没什么要补充的

X=5和X=6

以完全相同的方式处理这些。

这意味着您将以矩形的“条带”结束,如下图所示(我将它们分开一点以更清楚地说明它们是条带,但它们是并排连续放置的,如原始图中所示):

+--+ +-----+ +----+ ------+
|A | |     | |    | |     |
|  | |     | +----+ +-----+ +-----+
|  | |     | |C   | |     | |     |
|  | +-----| +----+ |     | |     |
|  | |B    | |    | |     | |     |
|  | |     | +----+ +-----| +-----+
|  | |     | |    | |     |
+--+ +-----+ +----+ +-----+
     |     | |    |
     +-----+ +----+
^  ^ ^     ^ ^    ^ ^     ^ ^     ^
1  2 2     3 3    4 4     5 5     6

好了,现在你有了你的输出,一组坐标对,每一对都有一个相关的矩形列表。

长条看起来像这样:

^     +----+ <-- 1
A     |    |
|   ^ +----+ <-- 2
|   C |    |
| ^ | +----+ <-- 3
| B | |    |
| | V +----+ <-- 4
| |   |    |
V |   +----+ <-- 5
  |   |    |
  V   +----+ <-- 6

矩形坐标列表:

1. 顶部=A,底部=(无)
2. 顶部=C,底部=(无)
3. 顶部=B,底部=(无)
4. 顶部=(无),底部=C
5. 顶部=(无),底部=A
6. 顶部=(无),底部=B

新空列表L=[]

处理坐标:

无需处理(L=[]) 添加到列表,L=[A]

Y=2

进程A的顶部和底部坐标暂时为Y=1和2(记住,它的左侧和右侧坐标暂时为X=3和4) 加上C,L=[A,C]

过程A和C,现在都有临时坐标(3,2)-(4,3) 加上B,L=[A,B,C]

Y=4

过程A、B和C,坐标均为(3,3)-(4,4)

Y=5

过程A和B,坐标(3,4)-(4,5) 删除A,L=[B]

Y=6

过程B,坐标(3,5)-(4,6)

最终输出:

Y坐标对,以及与其关联的矩形(也临时获得了新的X坐标):

• (3,1)-(4,2)-A
• (3,3)-(4,4)-A,B,C
• (3,4)-(4,5)-A,B
• (3,5)-(4,6)-B

现在,假设你想问这样一个问题:B是否完全被其他矩形的所有组合所覆盖。

答案如下:

1. 循环浏览上面最后一个列表中的所有矩形
2. 如果B是 不是 作为关联矩形的一部分,忽略此矩形
3. 如果有 任何 其他与坐标相关的原始矩形,则B的这部分被该/这些矩形覆盖
4. 如果没有与坐标相关联的其他原始矩形,则不包括B的这部分。

在上面的示例中,我们看到最终列表中的第3和第4个矩形包含B,但也包含其他矩形,因此覆盖了B的这些部分,但是列表中的最终矩形也包含B,但没有其他矩形,因此不覆盖此部分。

+--+-----+----+-----+
|A |A    |A   |A    |
|  |     +----+-----+-----+
|  |     |AC  |AC   |C    |
|  +-----+----+     |     |
|  |AB   |ABC |     |     |
|  |     +----+-----+-----+
|  |     |AB  |A    |
+--+-----+----+-----+
   |B    |B   |
   +-----+----+

如果我们现在重新看一下原始的图表,我已经将上面的算法发现的包含B的部分阴影掉了,但是没有其他矩形:

+-------------------+
|A                  |
|        +----------+-----+
|        |C         |     |
|  +-----+----+     |     |
|  |B    |    |     |     |
|  |     +----+-----+-----+
|  |          |     |
+--+-----+----+-----+
   |#####|####|
   +-----+----+

我真的希望我在这里能让别人明白我的意思。我有一些代码可以帮助你实现坐标列表中的每一次运行,但是现在已经过了午夜01:21,我要睡觉了,但是如果你想看到一些实际的代码,请留下评论。

或者自己去实现它是一个很好的练习:)

下面是指向包含所讨论方法的类的链接: RangeExtensions.cs .

方法是 Slice 方法,只需在页面中搜索它。所讨论的类型Range基本上是一个从一个值到另一个值的范围,因此除了上面的算法之外,还需要一些数据构造和维护。

下面介绍如何使扫掠线在O(n lgn)中工作。我将重点介绍BST工作原理中的棘手部分。

保持平衡的BST,其中包含与当前扫描线相交的每个矩形的起点和终点。BST的每个节点都包含两个辅助字段:minOverlap和deltaOverlap。字段minOverlap通常存储与该节点的子树覆盖的间隔中的任何点重叠的最小矩形数。但是,对于某些节点,该值稍微偏离。我们保持一个不变量,即minOverlap加上每个节点到根的deltaOverlap之和,在节点的子树中有一个区域重叠的真正最小矩形数。

当我们插入一个矩形起始节点时,我们总是在一个叶子处插入(可能还会重新平衡)。当我们沿着插入路径遍历时,我们将任何非零的deltaOverlap值“下推”到插入节点的访问路径的子节点,更新访问路径上节点的minOverlap。然后,我们需要在O(lgn)时间内增加树中插入节点右侧的每个节点。这是通过增加插入节点的所有右祖先的minOverlap字段和增加插入节点的右祖先的所有右子代的deltaOverlap来实现的。执行类似的过程来插入结束矩形的节点,以及删除点。通过仅修改旋转中涉及的节点的字段,可以执行重新平衡操作。你所要做的就是检查扫描中每个点的根,看看minOverlap是否为0。

我省略了处理重复坐标之类的细节(一个简单的解决方案就是将打开的矩形节点排在同一坐标的任何关闭的矩形节点之前),但希望它能给您一个想法,并且相当有说服力。

你知道最坏的情况吗 O(nlogn) the area of the union of rectangles ?

1. 您所在区域 不 矩形
2. 您所在区域 不 矩形和模型

如果这些面积相等,则模型完全被覆盖,否则就不是。

下面是一个使用一些内存的O(nlgn)运行时方法。

使用以下示例:

1,1 -> 6,6

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) 收集所有的x坐标 在模型矩形的边界内

1 3 4 5 6

2) 收集所有y坐标 在模型矩形的边界内 (顶部和底部)放入一个列表,然后对其排序并删除重复项

1 2 3 4 6

3) 按唯一x坐标之间的间距数*唯一y坐标之间的间距数创建二维数组。这可以使用每个单元的一个比特,并且可以考虑使用C++的STL的BITYVECUTE()来进行高效的表示。

4 * 4

4) 将所有矩形绘制到该网格中,绘制其所在的单元格:

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 2 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5) 如果任何细胞保持未上漆,你知道你的模型是不是完全闭塞(或任何你正在测试)。

采集坐标和绘制步骤为O(n),坐标的排序为O(n lg n)。

What is an Efficient algorithm to find Area of Overlapping Rectangles