我有N个矩形，其边平行于x和y轴。另外还有一个矩形model。 我需要创建一个算法来判断model是否完全被N个矩形覆盖。
我有一些想法。首先，我需要按其左侧对矩形进行排序（可以在O(n log n)时间内完成），然后使用垂直扫描线。
+------------------------------------------------------------> x
|O
| +----+
| +---------+ | |
| | ++----+--+ |
| | +-++----+-+| |
| | | | +-++-+
| +------+ +-------++
| +---------+
|
|
|
|y
蓝色矩形是模型。
首先，我需要抽象算法。对于实现没有特殊要求。矩形可以表示为一对点（左上角和右下角）。
这是为准备测试而完成的任务之一。我知道最好的算法可以在O(n log n)时间内完成此任务。
O(n log MaxCoords)。最坏情况下可能会是二次的，但我认为这样的测试会相当困难。为了使它更难，让递归函数调用的顺序变得随机。也许像 @Larry 建议的那样，平均可以达到 O(n log n)。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();
}
O(N log N) 算法，但最坏情况下是 O(N^2)。我真的很好奇答案！ - Larry我一直在思考，现在我终于明白了@algorithmist所说的sweep line是什么意思。然而，存在sorting操作意味着：
O(n log n)O(n**2)扫描线算法
首先，我们需要进行一些排序，因为我们的扫描线将由一个有序集合组成。
这个有序集合将包括每个red的top和bottom线，只要它们在blue的top和bottom之间。这将把我们的空间分成（最多）n*2个水平条带。
现在，我们需要确保在每个strip中，整个blue都被覆盖，并且此操作的复杂度不能超过O(log n)，如果我们对于每个strip都有一个已覆盖区间的列表，则可以完成此操作。 这就是@algorithmist所说的“事件”
为了处理此事件，我们将使用下面描述的二叉树，该树处理添加或删除矩形的操作，正好需要O(log n)次操作，并产生由树覆盖的最右侧间隔，我们用它来判断是否覆盖了blue的条带。
二叉树
首先，我将索引red矩形。 我们使用以下函数对它们进行排序：
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]为什么这有效？让我们举一个使用4个叶子的例子：
_ [1,9] _
/ \
[1,7] [6,9] <-- Special node merge
/ \ / \
/ \ / \
[1,3] [2,7] [3,5] [6,9]
[3,5]，因为它不是最右边的区间。原因是矩形是有序的：
[5,6]区间，因为它们从6开始3之前开始，因此如果它们覆盖了缺失的[5,6]，它们将无论如何覆盖[3,5]根节点可能不表示完全覆盖的精确区间集合：仅表示最右边的区间被覆盖。然而，这已经足够我们判断blue是否完全被覆盖！
该树有2个可用操作：
每个操作类似：
递归部分的时间复杂度为O(log n)。这是平衡二叉树的经典特性。一旦完成，我们就可以通过根节点覆盖最右边的区间，从而判断blue段是否完全被覆盖。
复杂度
算法的复杂度很简单：
O(n)个事件O(log n)的处理时间核心部分的时间复杂度为O(n log n)。
然而，我们也不能忘记还有两个sort操作：
每个操作在平均情况下需要O(n log n)的时间，但在最坏情况下可能会退化为O(n**2)，具体取决于所使用的排序算法。
O(log N)的时间进行。至少，这就是我遇到的困难，除非我漏掉了什么显而易见的东西。 - LarryO(log n) 的。它基于我们事先知道手头的区间这一事实。 - Matthieu M.好的，现在看起来我甚至晚上都无法入睡，因为我一直在思考这个问题...但是似乎我终于找到了一个O(n log n)的解决方案，在平均情况下（但与@lVlad相比，减少了出现病态输入的机会）。
我们都知道分治法技术。为了确保使用它的时间复杂度为O(n log n)，我们通常关注以下两点：
O(n)在考虑这些限制条件的基础上，我制定了以下算法，它类似于qsort，因此也会遇到相同的问题（即，分形输入）。
算法
蓝色相交的红色部分，将它们插入到一个HashSet中以去除重复项 --> O(n)O(n)红色放入分区中，应用剪裁技术，注意给定的红色可能会在不同的分区中产生多个块枢轴选择是该算法的基石，如果分区不合适，我们无法达到所需的复杂度。而且，它必须在O(n)时间内完成。我有两个提案：
最大面积：选择具有最大面积的矩形，因为这意味着分区后的面积最小，但它容易受到影响。3数中值：基于qsort，选择三个元素，选择中位数（其中心离三个中心的重心更近的那个）。我建议将它们混合使用：
实现的另一个方面是递归的尾部。像qsort一样，对于小的n，算法可能是低效的。我建议使用introsort技巧：如果n小于12，则改用以下算法：
red投影到轴上（仅边缘），并对它们进行排序（ala introsort）维度无关
该算法在任何给定维度中都被正式定义为具有相同的渐近复杂度，平均为O(n log n)。这使我们有机会在维度1中进行测试以识别病态输入。
病态输入
像其模型qsort一样，它对阶乘输入敏感。通过阶乘输入，我的意思是：
1.......6...9.11.13
+----------------+----+---------+
| 1 | 2 | 3 |
+----------------+----+---------+
| 8 | P | 4 |
+----------------+----+---------+
| 7 | 6 | 5 |
+----------------+----+---------+
好的，那么我们检查覆盖的矩形现在被分成了9个子矩形。我们忽略 P，它是我们的枢轴。
现在，我们非常希望每个子矩形都被少于 N 个 red 覆盖。选择重心作为中心点，这意味着如果我们的“随机”选择成立，那么每个方向上的 red 中心点大约相等。
这有点模糊，因为一些特殊的配置可能会使得在某一步骤中获得很小的收益（例如，所有矩形都具有相同的中心，我们只是选择了较小的一个），但这将会造成混乱，因此后续步骤将会有所不同。
如果有人能够正式化这个问题，我会很高兴，我是一名工程师，不是计算机科学家，我的数学落后了一些...
O(n)次检查的？你能发一些伪代码吗？ - IVladc == 2）。然而，我必须承认，尽管应该可以通过P由于其居中位置而选择，从而证明它能够正常工作，但证明其重新分配将起作用有些困难。可能是因为有些情况（如分形）是不适用的。 - Matthieu M.O(N)内完成，而不是每个递归调用的O(N)吗？你谈到通过投影将问题简化为1d，但我也不确定那些是如何工作的... - IVlad这里有一个通用算法：
现在的问题是如何高效地实现上述算法。可以通过单次循环遍历所有多边形来完成上述操作，因此时间复杂度为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)。
另请参见this问题。
编辑： 关于交集和并集的复杂性回应。
更详细地说，我们有两种情况，取决于k << n还是k与n相当
a) 如果k << n，并假设交集/并集的复杂度为多项式（因此我放弃了猜测O(k log k)），我们有：
总共是O(k + log n + f(k))，这直接等于O(log n)，因为大O仅取决于增长最快的术语。
在这种情况下，算法的重要部分是找到多边形。使用扫描线算法是正确的方向。从概念上讲，我们要检测模型与扫描线相交时是否未被其他矩形覆盖。高层次模板是将每个矩形分解为“左边缘”和“右边缘”事件，按x坐标排序事件（如果矩形封闭，则把左侧放在右侧前面，如果矩形开放，则把右侧放在左侧前面），然后在O(log n)时间内处理每个事件。这基本上是一份作业，所以我不会再多说。
有一个微不足道的O(N^2)方法与提出的“光栅”方法类似。由于所有矩形都是轴对齐的，因此最多只能有2N个不同的x和y维度。对所有x和y进行排序并重新映射：x_i -> i。现在您有一个2N x 2N矩阵，可以轻松使用朴素的O(N^2)算法。
O(N^2)解决方案 - 如果有其他方法，请告诉我。 - Larry这里有一种方法可以在不使用光栅化的情况下完成，也就是只使用纯数字。
注意：这不是O(n log n)，更像是O(n^2)。然而，它是一种解决方案。是否是答案，如果需要O(n log n)的话可能不是。
因此输出应为：
让我来说明一下目前的过程
+-------------------+
|A |
| +----------+-----+
| |C | |
| +-----+----+ | |
| |B | | | |
| | +----+-----+-----+
| | | |
+--+----------+-----+
| |
+----------+
^ ^ ^ ^ ^ ^
1 2 3 4 5 6 <-- X-coordinates
相关矩形：
现在创建一个空列表L=[]，并开始处理坐标和相关矩形：
列表为空，没有要处理的内容 没有要删除的内容 添加A：L=[ A ]
列表包含矩形，将列表中具有X=1左边缘和X=2右边缘（我们已经处理了两个坐标）的矩形作为矩形进行处理，并使用它们的原始顶部和底部坐标。 没有要删除的内容。 添加B：L=[ A, B ]
列表包含矩形，以相同方式处理列表中的A和B，将它们视为暂时具有左坐标和右坐标为X=2和X=3，并使用它们的原始顶部和底部坐标。 没有要删除的内容 添加C：L=[ A, B, C ]
以与上述相同的方式处理三个矩形，临时左右坐标为X=3和X=4 移除B：L=[A，C] 无需添加
以完全相同的方式处理这些内容。
这意味着您最终将得到矩形“条”，就像这样（我稍微拉开它们以更清楚地说明它们是条纹，但它们像原始图表中连续并排放置）：
+--+ +-----+ +----+ ------+
|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
带有矩形的坐标列表：
新的空列表L=[]
处理坐标：
没有要处理的内容（L=[]） 将A添加到列表中，L=[ A ]
使用临时的顶部和底部坐标为Y=1和2来处理A（并记住它还具有X=3和4的临时左右坐标） 添加C，L=[ A, C ]
处理A和C，两者现在都具有(3, 2)-(4, 3)的临时坐标 添加B，L=[ A, B, C ]
处理A、B和C，所有坐标都为(3, 3)-(4, 4) 删除C，L=[ A, B ]
进程A和B，坐标（3,4）-（4,5） 移除A，L=[B]
进程B，坐标（3,5）-（4,6）
最终输出：
与矩形相关联的Y坐标对（它们也暂时获得了新的X坐标）：
现在，假设您想问一个问题：B是否被其他矩形的任何组合完全覆盖。
答案可以按以下方式计算：
遍历上述最终列表中的所有矩形；如果B不是关联矩形的一部分，请忽略此矩形；如果任何其他原始矩形与坐标相关联，则B的此部分由该/这些矩形覆盖；如果没有其他原始矩形与坐标相关联，则该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 基本上是从一个值到另一个值的范围，因此除了上述算法之外，还需要一些数据构造和维护。
好的，我已经问了足够多的问题，这里是一个答案...
如果数据表示为栅格，则一个算法就很简单：
如果数据是向量，则会更加复杂。首先定义一个函数，该函数返回表示两个矩形交集（如果有）的矩形。这很简单。然后继续：
仅处理与蓝色矩形相交的红色矩形。对于每个红色矩形，计算矩形与UnCoveredRectangle的交集。交集将导致以下情况之一：
2.1 交集等于UnCoveredRectangle。工作完成。
2.2 交集从CoveredRectangle中“咬”出一个矩形块。剩余的UnCoveredRectangle将是一个矩形、L形或U形。如果它本身是一个矩形，则将UnCoveredRectangle设置为剩余的矩形，并转到步骤2。如果UnCoveredRectangle是L形或U形，则将其分成2个或3个矩形，并从步骤2递归。
如果在面积（部分）UnCoveredRectangle被送到0之前，你用完了所有的红色矩形，那么你就完成了。
好的，我对这个算法的复杂性一无所知，但除非矩形的数量很大，否则我不太担心，尽管@den可能会有所顾虑。我省略了很多细节。我也不能像@den那样画出漂亮的图表，所以你们得自己想象。
O（分成4个），甚至是 ||（分成两个）。排序也有助于您尽早了解矩形是否完全覆盖了区域。 - Kobi这里介绍如何在O(n lg n)的时间复杂度内实现扫描线算法。我将重点关注二叉搜索树的工作原理。
维护一个平衡的二叉搜索树，其中包含与当前扫描线相交的每个矩形的起始和结束位置。每个BST节点都包含两个辅助字段：minOverlap和deltaOverlap。minOverlap通常存储覆盖该节点子树范围内任何点的最小重叠矩形数。但是，对于某些节点，该值略有出入。我们保持一个不变量，即minOverlap加上每个节点到根节点的deltaOverlap之和等于该节点子树中重叠矩形数量的真实最小值。
当我们插入一个矩形起始节点时，我们总是在叶子节点中插入（并可能重新平衡）。当我们沿插入路径向下遍历时，我们将任何非零的deltaOverlap值“向下推”到插入节点访问路径的子节点上，更新访问路径上节点的minOverlap。然后，我们需要在O(lg n)时间内递增树中插入节点右侧的每个节点。通过递增插入节点的所有右祖先的minOverlap字段和递增插入节点右祖先的所有右子节点的deltaOverlap来实现这一点。类似的过程也用于结束矩形的节点插入以及点的删除。通过仅修改旋转涉及的节点的字段，可以执行重新平衡操作。您所要做的就是在扫描中的每个点检查根是否最小重叠为0。我省略了处理重复坐标等细节的细节（一个简单的解决方案就是将开放矩形节点按任何相同坐标的关闭矩形节点排序），但希望它能给您提供想法，并且具有合理的说服力。
O(n log n)的算法，它基于对qsort算法的改进。 - Matthieu M.