矩形覆盖

Question

我有 N 个矩形，其边平行于 x 轴和 y 轴。还有另一个矩形，模型。我需要创建一个算法来判断模型是否被 N 矩形完全覆盖。

我有一些想法。我认为首先，我需要按矩形的左侧对矩形进行排序（可以在 O(n log n) 时间内完成），然后使用垂直扫描线。

+------------------------------------------------------------> x
|O
|                  +----+
|   +---------+    |    |
|   |        ++----+--+ |
|   |      +-++----+-+| |
|   |      | |     +-++-+
|   +------+ +-------++
|          +---------+
|
|
|
|y

蓝色矩形是模型。

首先，我需要抽象算法。对于实现没有特殊要求。矩形可以表示为一对点（左上角和右下角）。

这是准备考试的任务之一。我知道最好的算法可以在 O(n log n) 时间内完成此操作。

Answer 1

这是一个分而治之的算法。 AVERAGE 案例复杂度非常好，我想说它类似于 O(n log MaxCoords)。最坏的情况可能是二次的，但我认为这样的测试很难创建。为了让它变得更难，使递归函数调用的顺序随机。也许@Larry 建议的平均时间复杂度为O(n log n)。

我无法找出扫描线解决方案，但对于我尝试过的测试来说，这非常快。

基本上，使用适用于蓝色矩形的递归函数。首先检查蓝色矩形是否被其他矩形之一完全覆盖。如果是，我们就完成了。如果不是，则将其分成 4 个象限，并在这些象限上递归调用该函数。所有 4 次递归调用都必须返回 true。我包含一些绘制矩形的 C# 代码。您也可以将其更改为使用更大的值，但在这种情况下请删除绘图过程，因为这些过程将永远持续下去。我用生成的一百万个矩形和一个边长为十亿的正方形进行了测试，使其未被覆盖，并且提供的答案（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(); 
    }

Answer 2

您的扫描线走在正确的轨道上。从概念上讲，我们想要检测模型与扫描线的交点何时未被其他矩形覆盖。高级模板是将每个矩形分解为“左边缘”和“右边缘”事件，按 x 坐标对事件进行排序（如果矩形关闭，则将左侧放在右侧之前，如果矩形打开，则将右侧放在左侧之前），然后在 O(log n) 时间内处理每个事件。这基本上就是功课，我就不多说了。

Answer 3

这是一个通用算法，

1. 有没有覆盖整个模型的矩形？
   如果是，则完成，
2. 如果否，是否有任何矩形部分覆盖模型？
   如果是，
3. 则矩形和模型的所有交集的并集等于模型
   如果 2. 或 3. 为否，则答案为否，否则为是。

现在的问题是如何有效地执行上述操作。上述操作可以在所有多边形上的单个循环中完成，所以我认为您正在考虑 O(n) 时间。

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

如果您使用，例如 kd-trees，我相信这可以在 O( log n) 时间 - 但该算法中的重要变量也是找到的矩形 k 的数量。您最终会得到类似 O(k + log n) 的结果，并且您还需要执行并集部分来测试模型是否被覆盖。

我的猜测是，并集可以在 O(k log k) 中计算，因此如果 k 很小，那么您正在查看 O(log n)，如果 k 与 n 相当，那么它应该是 O(k log k)。

另请参阅此问题。

编辑：
应对交集和并集的复杂性。

更详细地说，我们有两种情况，具体取决于 k << n或k与n a)相当

在k≤a)的情况下， 。 n 并假设交集/并集的多项式复杂度（所以这里我放弃猜测 O(k log k) ）我们有：

• 将 n 记录到 在 kd 索引树（矩形）中找到一个范围，
• k 步骤检索该“分支”中的所有矩形，
• f(k) 一些多项式时间来计算交集和并

集总计为 O(k + log n + f(k))，它直接等于 O(log n)，因为大 O 仅取决于增长最快的项。

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

b) 在 k 与 n 相当的情况下，我们必须看看交集和并集算法的复杂性
（请注意这里的并行关系，即 RDBM 如何根据选择性使用索引或执行表扫描；这与我们这里的选择类似）。
如果 k 足够大，该算法就不再是查找与矩形相交的矩形的算法，而更像是计算多边形并集的算法。

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

Answer 4

有一种简单的 O(N^2) 方法，类似于所提出的“光栅”方法。由于所有矩形都是轴平行的，因此最多只能有 2N 个不同的 x 和 y 维度。对所有 x 和 y 进行排序并重新映射：x_i ->我。现在您有了一个 2N x 2N 矩阵，您可以轻松地使用朴素的 O(N^2) 算法。

Answer 5

好吧，现在看来我什至晚上都睡不着了，因为我想到了这个问题......但似乎我终于得到了一个 O(n log n) 解决方案，平均值 情况（但与 @lVlad 相比，出现病态输入的可能性降低）。

我们都知道“分而治之”技术。为了确保O(n log n)使用它，我们通常关注两点：

• 除法和合并应该是O( n)
• 存在C> 1 这样，在每一步，子问题的大小都会减少一个因子 C（在整个问题中保持不变）

考虑到这些约束，我详细阐述了以下算法，这让人想起qsort，因此遭受同样的陷阱（即分形输入）。

算法

1. 裁剪：我们只考虑red与blue相交的部分，它们被插入到一个HashSet中删除重复项 --> O(n)
2. 枢轴选择：稍后会详细介绍 --> O(n)
3. 分区：一旦我们有了一个枢轴，我们就将空间细分为 3^d 个区域，其中一个是枢轴， d 是维度（d = 1 表示线段，2 表示矩形，3 表示立方体等...）
4. 重新分区：我们将红色 放入分区中，应用裁剪技术上，请注意，给定的red可能最终会在不同的分区中给出多个块
5. 递归：我们在每个分区上递归地应用（从步骤2开始），从填充最少的分区开始一旦没有被覆盖就停止

枢轴选择是算法的基石，如果分区不合适，我们就无法达到所需的复杂性。此外，它必须在 O(n) 内完成。到目前为止，我有 2 个建议：

• 最大面积：使用面积最大的矩形，因为这意味着分区之后的面积将是最小的，但它的缺点是很容易胜过
• 中位数of 3：基于qsort，选取3个元素，选择中位数（中心更接近3个中心的重心的那个）

我建议将它们混合在一起：

• 选取最大的3个元素区域，选择中位数，在枢轴处使用
• 如果重新分区后发现其中一个分区填充了超过 N/C（待定制）元素，则随机选取 3 个元素，选择中位数，然后执行重新分区（此处不检查）

实现的另一个方面是递归的尾部。与 qsort 一样，该算法对于较小的 n 可能效率较低。我建议使用 introsort 技巧，而不是一直到 1：如果 n 小于 12，则使用以下算法：

• 对于每个轴，将每个红色投影到轴上（仅边缘）并对它们进行排序（ala introsort）
• 这定义了n^d区域的栅格，检查每个区域是否都被覆盖

维度不可知的

算法被正式定义为适用于任何给定的维度，具有相同的渐近复杂度，即平均 O(n log n)。这使我们有机会在维度 1 中进行测试以识别病理输入。

病理输入

就像它所建模的qsort 一样，它对阶乘输入很敏感。我所说的阶乘输入是指：

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

每当您选择间隔的平均值时，所有元素都位于其一侧。

有了这样的输入，即使选择中位数 3 也不太可能产生很好的切割结果。

编辑：

我将用一个小方案来展示分区的想法，正如@lVlad指出的那样，它有点模糊。

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

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

现在，我们真的希望每个子矩形被较少的红色覆盖而不是N。枢轴被选择为中心的重心，因此这意味着如果我们的“随机”选择成立，则枢轴的每个方向上都有大约同样多的红色中心。

那里有点模糊，因为一些特殊的配置可能会使其在一步中几乎没有增益（所有矩形都有相同的中心，例如我们只选择了较小的一个），但它会造成混乱，因此下一步将有所不同。

如果有人能正式说明这一点，我很高兴，我是一名工程师，而不是计算机科学家，而且我的数学落后......

Answer 6

我一直在思考这个问题，我想我终于明白了 @algorithmist 的含义>扫线。然而，排序操作的存在意味着我有：

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

扫描线

首先，我们需要一些排序，因为我们的扫描线将包括走一个有序集。

此有序集将包含每个 red 的 top 和 bottom 线，只要它们位于 top< /code> 和 blue 的 bottom。这将我们的空间划分为（最多）n*2 水平条带。

现在，我们需要确保在每个strip中，整个blue被覆盖，并且这个操作不能超过O(log n)代码>复杂性，如果我们（对于每个条带）有一个覆盖间隔的列表，就可以做到这一点。 这是 @algorithmist 所说的“事件”

为了处理这个事件，我们将使用下面描述的二叉树，它可以精确地处理添加或删除矩形O(log 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] 和 < code>[c,d]：

• 如果c <= b，则节点保存[a,d]，
• 否则保存[c ,d]

为什么它有效？让我们以 4 个叶子为例：

        _ [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]< /code> 无论如何，它们都会覆盖 [3,5]

根可能不会指示所覆盖的确切间隔集：仅覆盖最右边的间隔。然而，我们完全足以判断 blue 是否被完全覆盖！

此树上有 2 个可用操作：

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

每个操作都是相似的：

• 如果矩形已经处于此状态，则不执行任何
• 其他操作，切换其状态，然后更新其父间隔（递归地，最多根）

递归位需要O(log n)。这是平衡二叉树的经典属性。一旦完成，我们就得到了根覆盖的最右边的区间，这足以判断蓝色段是否被完全覆盖。

复杂性

算法的复杂性很简单：

• 我们有 O(n) 个事件
• 每个事件都在 O(log n) 内处理，

结果是 < code>O(n log n) 为核心部分。

但是，我们不应该忘记，我们还有 2 个 sort 操作：

• 一个用于对事件进行分类（对于扫描线），
• 另一个用于对矩形进行分类（对于二叉树），

每个操作都应采用 平均为 O(n log n)，但在最坏的情况下可能退化为 O(n**2)，具体取决于所使用的排序算法。

Answer 7

很难知道你在寻找什么，但对我来说，它听起来像一个 R-tree可能有用吗？

Answer 8

好的，我已经问了足够多的问题，这里有一些答案......

如果数据表示为栅格，则一种算法很简单：

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

如果数据是矢量，那就有点复杂了。首先定义一个函数，该函数返回表示两个矩形的交集（如果有）的矩形。这很简单。然后继续：

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

2. 同样，只关心与蓝色矩形相交的红色矩形。对于每个红色矩形，计算该矩形与 UnCoveredRectangle 的交集。相交会导致以下情况之一：

   2.1 交集等于 UnCoveredRectangle。工作已经完成。

   2.2 交集从 CoveredRectangle 中“咬”出一个矩形块。剩余的 UnCoveredRectangle 将是矩形、L 形块或 U 形块。如果它本身是一个矩形，则将 UnCoveredRectangle 设置为剩余的矩形，然后转到步骤 2。如果 UnCoveredRectangle 是 L 形或 U 形，则将其分割为 2 个或 3 个矩形，并从步骤 2 递归。

3. 如果在 UnCoveredRectangle（部分）的面积发送到 0 之前用完红色矩形，则说明已完成。

好吧，我不知道这个算法的复杂性，但除非矩形的数量很大，否则我不太担心，尽管@den 可能会担心。而且我省略了很多细节。我无法像@den 那样画出漂亮的图表，所以你必须自己想象。

Answer 9

这是一种不使用光栅化（即仅使用纯数字）来完成此操作的方法。

注意：这不是 O(n log n)，更像是 O(n^2)。然而，它是一个解决方案。无论它是一个答案，如果 O(n log n) 是一个要求，则可能不是。

1. 创建左边缘和右边缘的所有唯一 X 坐标的列表（在同一个列表中）
2. 当您构建此列表时，对于每个坐标，还将一个矩形列表与其关联，并在此列表中表示 X 坐标是否与列表关联的坐标是矩形的左边缘或右边缘 对
3. 坐标列表进行排序，使其按升序排列，从左到右
4. 创建一个新的矩形列表，最初为空
5. 运行坐标列表，然后进行处理其关联的矩形列表
6. 关联列表中所有以坐标为左边缘的矩形都应添加到您在 4 中创建的列表中。
7. 所有以坐标为右边缘的矩形都应被删除。
8. 添加和删​​除的顺序实际上应该以相反的顺序完成，首先要删除右边缘矩形，然后添加所有左边缘矩形
9. 现在，在从创建的列表中删除矩形之前4、你要处理它们。您可以通过将它们视为“子矩形”来处理它们。它们的“新”左边缘坐标是您处理循环的上一次迭代（在 5 中）的 X 坐标，新的右边缘是当前正在处理的 X 坐标
10. 算法的输出是坐标对的集合（左右两个 X 坐标），每对都有一个关联的矩形列表（垂直条）

因此输出应为：

1. X=1..2, Rects=A
2. X=2..3, Rects=A , B
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、右：（无）
3. 左：C、右：（无）
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=4

将三个矩形同上处理，临时左右坐标分别为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

好的，所以现在您有了输出，即坐标对的集合，每对都有一个关联的矩形列表。

现在我们表演一个技巧。我们以完全相同的方式处理垂直条带，只是这次我们使用 Y 坐标作为分隔符。让我们处理上面 3 和 4 之间的条带。请记住，条带的左右坐标分别为 3 和 4。

条带看起来像这样：

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

矩形坐标列表：

1. Top=A，Bottom=(none)
2. Top=C，Bottom=(none)
3. Top=B，Bottom= (无)
4. Top=(无), Bottom=C
5. Top=(无), Bottom=A
6. Top=(无), Bottom=B

新空列表 L=[]

处理坐标:

Y=1

没有要处理的内容 (L= [])
将 A 添加到列表中，L=[ A ]

Y=2

进程 A 临时具有 Y=1 和 2 的顶部和底部坐标（请记住，它还具有 X=3 和 4 的临时左侧和右侧坐标
添加 C, L=[ A, C ]

Y=3

处理 A 和 C，现在两者的临时坐标均为 (3, 2)-(4, 3)
添加 B, L=[ A, B, C ]

Y=4

处理 A、B 和 C，坐标均为 (3, 3)-(4, 4)
去掉C, L=[ A, B ]

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, 2)-(4, 3) - A, C
• (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 的这部分不被覆盖。

在上面的例子中，我们看到最终列表中的第三个和第四个矩形包含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 基本上是从一个值到另一个值的范围，因此除了上述算法之外，还需要一些数据构建和维护。

Answer 10

以下是如何使扫描线在 O(n lg n) 中工作。我将重点讨论 BST 如何工作的棘手部分。

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

当我们插入一个矩形起始节点时，我们总是在叶子处插入（并且可能会重新平衡）。当我们沿着插入路径遍历时，我们将任何非零 deltaOverlap 值“下推”到插入节点的访问路径的子节点，从而更新访问路径上节点的 minOverlap。然后，我们需要在 O(lg n) 时间内将每个节点增加到树中插入节点的“右侧”。这是通过增加插入节点的所有右祖先的 minOverlap 字段并增加插入节点的右祖先的所有右子节点的 deltaOverlap 来完成的。对于插入矩形末端的节点以及删除点，执行类似的过程。可以通过仅修改参与轮换的节点的字段来执行重新平衡操作。您所要做的就是检查扫描中每个点的根，看看 minOverlap 是否为 0。

我省略了处理重复坐标之类的细节（一个简单的解决方案就是在任何节点之前对开放矩形节点进行排序）相同坐标的闭合矩形节点），但希望它能给您带来想法，并且相当有说服力。

Answer 11

你知道 矩形并集的面积？

这里您需要做的就是计算两个面积：

1. N 个矩形的面积
2. N 个矩形和模型的面积

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

Answer 12

这是使用一些内存的 O(n lg n) 运行时方法。

使用示例：

我们只对场景中包含“模型”矩形的子部分感兴趣；在此示例中，“模型”矩形为 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 坐标之间的间隙数创建一个 2D 数组* 唯一 y 坐标之间的间隙数。这可以为每个单元使用一位，并且您可以考虑使用 C++ STL 的 bit_vector() 来进行有效的表示。

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)。

这改编自我的答案之一：什么是查找重叠矩形面积的有效算法