我有N个边平行于 x 轴和 y 轴的矩形。还有另一个矩形，模型。我需要创建一个算法来判断模型是否完全被N个矩形覆盖。
我有一些想法。我认为首先，我需要对矩形进行左侧排序（可以在O(n log n)时间内完成），然后使用垂直扫描线。
+------------------------------------------------------------> x
|O
| +----+
| +---------+ | |
| | ++----+--+ |
| | +-++----+-+| |
| | | | +-++-+
| +------+ +-------++
| +---------+
|
|
|
|y
蓝色矩形是模型。
首先，我需要抽象算法。对于实现没有特殊要求。一个矩形可以表示为一对点（左上和右下）。
这是准备考试的任务之一。我知道最好的算法可以在O(n log n)时间内做到这一点。
这是一个分而治之的算法。平均案例复杂度非常好，我会说它类似于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();
}
有一种O(N^2)类似于提出的“光栅”方法的简单方法。由于所有矩形都是轴平行的，因此最多只能有2N不同的 x 和 y 维度。对所有 x 和 y 进行排序并重新映射： x_i -> i。所以现在你有一个2N x 2N矩阵，你可以轻松地使用朴素O(N^2)算法。
我一直在想它，我想我终于明白了sweep line@algorithmist是什么意思。然而，操作的存在意味着我有：sorting
O(n log n)平均而言O(n**2)在最坏的情况下扫描线
首先，我们需要一些排序，因为我们的sweep line意志包括遍历一个有序集合。
这个有序集合将具有每个 s 的top和bottom线red，只要它们在top和bottom之间blue。这将我们的空间划分为（最多）n*2水平条。
现在，我们需要确保在 eachstrip中，整个 ofblue都被覆盖，并且这个操作不能超过O(log n)复杂性，如果我们（对于每个条带）有一个覆盖区间的列表，就可以做到这一点。这就是“事件”@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叶子，每个叶子代表一个red矩形并指示它的存在或不存在。它们是根据索引排序的。处理“代码块不能跟随列表”的错误：
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]，因为它不是最右边的间隔。原因是矩形是有序的：
[6,9]不会覆盖缺失的[5,6]间隔，因为它们开始于6[3,5]begin before左侧的矩形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)
您在扫描线的正确轨道上。从概念上讲，我们想要检测模型与扫描线的交点何时未被其他矩形覆盖。高级模板是将每个矩形分成“左边缘”和“右边缘”事件，按 x 坐标对事件进行排序（如果矩形关闭则将左放在右之前，如果矩形打开则将右放在左之前），然后在 O(log n) 时间内处理每个事件。这基本上是功课，所以我不再多说。
这是一个通用算法
现在的问题是如何有效地完成上述工作。以上可以在所有多边形的单个循环中完成，所以我认为您正在查看 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 << n 的情况下并假设交集/并集的多项式复杂度（所以在这里我放弃猜测 O(k log k) ）我们有：
总数为 O(k + log n + f(k))，直接等于 O(log n)，因为大 O 仅取决于增长最快的项。
在这种情况下，算法更重要的部分是寻找多边形。
b）在 k 与 n 可比的情况下，我们必须看看交集和联合算法的复杂性（注意这里关于 RDBM 如何根据选择性使用索引或执行表扫描的并行；这是一个类似的选择到我们这里所拥有的）。
如果 k 足够大，该算法就不再是一种用于寻找与矩形相交的矩形的算法，而更像是一种用于计算多边形并集的算法。
但是，我相信 kd 树也可以帮助找到段的交集（这是建立联合所必需的），所以即使这部分算法也可能不需要 k^2 时间。在这一点上，我将研究计算联合面积的有效算法。
好吧，现在看来我什至晚上都睡不着，因为我想到了这个问题……但似乎我终于得到了一个O(n log n)解决方案，在平均情况下（但患病态的机会减少了）输入相比@lVlad）。
我们都知道分而治之的技术。为了确保O(n log n)使用它，我们通常关注2点：
O(n)考虑到这些约束，我详细阐述了以下算法，它让人联想到qsort，因此遭受相同的陷阱（即分形输入）。
算法
red中与 相交的部分blue，它们被插入到 HashSet 中以删除重复项 -->O(n)O(n)red放入分区中，应用 Clipping 技术，注意一个给定的red最终可能会在不同的分区中给出几个块枢轴选择是算法的基石，如果分区不合适，我们将无法达到所需的复杂度。此外，它必须在O(n). 到目前为止，我有 2 个建议：
Maximum Area：使用面积最大的矩形，因为这意味着分区之后将具有最小的面积，但是它的缺点是容易被王牌Median of 3：基于qsort，选取3个元素，选择中位数（中心靠近3个中心重心的那个）我建议将它们混合起来：
实现的另一个方面是递归的尾部。就像qsort该算法可能对 small 效率低下一样n。我建议不要一直到 1，而是使用introsort技巧：如果n小于 12，则改用以下算法：
red到轴上（仅边缘）并对它们进行排序（ala introsort）维度无关
该算法被正式定义为适用于具有相同渐近复杂度的任何给定维度，平均为 O(n log n)。这使我们有机会在维度 1 中进行测试以识别病理输入。
病理输入
就像qsort它所建模的那样，它对阶乘输入是明智的。通过阶乘输入，我的意思是：
1.......6...9.11.13
每当您选择间隔的平均值时，您都会在其一侧拥有所有元素。
有了这样的输入，即使选择 3 的中位数也不太可能产生非常好的切割。
编辑：
我将用一个小方案来展示分区的想法，正如我所@lVlad指出的那样，它有点模糊。
+----------------+----+---------+
| 1 | 2 | 3 |
+----------------+----+---------+
| 8 | P | 4 |
+----------------+----+---------+
| 7 | 6 | 5 |
+----------------+----+---------+
好的，所以我们检查覆盖范围的矩形现在被分成 9 个子矩形。我们忽略 P，这是我们的支点。
现在，我们真的希望每个子矩形都被小于red覆盖N。枢轴被选为中心的重心，因此这意味着如果我们的“随机”选择成立，那么red在枢轴的每个方向上大约有同样多的 s 中心。
那里有点模糊，因为一些特殊的配置可能会导致一步几乎没有增益（所有矩形都有相同的中心，我们只选择了较小的一个），但它会造成混乱，因此接下来的步骤将与众不同。
如果有人能将其正式化，我会很高兴，我是一名工程师，而不是计算机科学家，而且我的数学落后了......
这是一种不使用光栅化的方法，即仅使用纯数字。
注意：这不是 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 ]
List 包含矩形，将 list 处理为具有 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 ]
进程 A 的顶部和底部坐标暂时为 Y=1 和 2（请记住，它还具有临时的左右坐标 X=3 和 4 添加 C, L=[ A, C ]
进程 A 和 C，现在都具有 (3, 2)-(4, 3) 的临时坐标 Add 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 是否被其他矩形的所有任意组合完全覆盖。
答案可以如下计算：
在上面的示例中，我们看到最终列表中的第 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 lg n) 中制作扫描线的方法。我将专注于 BST 如何工作的棘手部分。
保持一个平衡的 BST，其中包含与当前扫描线相交的每个矩形的起点和终点。BST 的每个节点都包含两个辅助字段：minOverlap 和 deltaOverlap。字段 minOverlap 通常存储与该节点的子树覆盖的区间中的任何点重叠的最小矩形数。但是，对于某些节点，该值略有偏差。我们维护一个不变量，即 minOverlap 加上直到根节点的每个节点的 deltaOverlap 之和具有与节点子树中的区域重叠的真正最小矩形数。
当我们插入一个矩形起始节点时，我们总是在叶子处插入（并可能重新平衡）。当我们遍历插入路径时，我们将任何非零 deltaOverlap 值“下推”到插入节点的访问路径的子节点，更新访问路径上节点的 minOverlap。然后，我们需要在 O(lg n) 时间内将每个节点递增到树中插入节点的“右侧”。这是通过增加插入节点的所有右祖先的 minOverlap 字段并增加插入节点的右祖先的所有右子节点的 deltaOverlap 来实现的。对于结束矩形的节点的插入以及点的删除，执行类似的过程。可以通过仅修改轮换中涉及的节点的字段来执行重新平衡操作。您所要做的就是检查扫描中每个点的根，以查看 minOverlap 是否为 0。
我省略了处理重复坐标之类的细节（一个简单的解决方案是在相同坐标的任何闭合矩形节点之前对开放矩形节点进行排序），但希望它能给你这个想法，并且相当有说服力。
很难知道您在寻找什么，但在我看来，R-tree可能有用吗？
好的，我已经问了足够多的问题，这里有一个答案......
如果数据表示为栅格，则一种算法很简单：
如果数据是矢量，则要复杂一些。首先定义一个函数，该函数返回表示两个矩形的交集（如果有）的矩形。这很简单。然后继续：
同样，只关心与蓝色矩形相交的红色矩形。对于每个红色矩形，计算矩形与 UnCoveredRectangle 的交点。交叉点将导致以下情况之一：
2.1 交点等于 UnCoveredRectangle。作业完成了。
2.2 交叉点从 CoveredRectangle 中“咬”出一个矩形块。剩余的 UnCoveredRectangle 将是矩形、L 形块或 U 形块。如果它本身是一个矩形，则将 UnCoveredRectangle 设置为剩余的矩形，然后转到步骤 2。如果 UnCoveredRectangle 是 L 形或 U 形，则将其拆分为 2 或 3 个矩形并从步骤 2 递归..
如果在 UnCoveredRectangle 的（部分）区域被发送到 0 之前用完红色矩形，那么您就完成了。
好的，我对这个算法的复杂性一无所知，但除非矩形的数量很大，否则我不太担心，尽管@den 可能是。而且我省略了很多细节。而且我不能像@den 那样画出漂亮的图表，所以你必须自己画出来。
Do you know the usual worst-case O(nlogn) algorithm for the area of the union of rectangles?
All you need to do here is to compute the two areas:
If these areas are equal, the model is totally covered, otherwise it isn't.
这是使用一些内存的 O(n lg n) 运行时方法。
使用示例：
我们只对包含“模型”矩形的场景子部分感兴趣；在这个例子中，“模型”矩形是1,1 -> 6,6
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | 乙|
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1）将模型矩形（左右）边界内的所有x坐标收集到一个列表中，然后对其进行排序并删除重复项
1 3 4 5 6
2）将模型矩形（顶部和底部）边界内的所有y坐标收集到一个列表中，然后对其进行排序并删除重复项
1 2 3 4 6
3) 通过唯一 x 坐标之间的间隙数 * 唯一 y 坐标之间的间隙数创建一个 2D 数组。这可以使用每个单元格的单个位，并且您可以考虑使用 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)。
这改编自我的一个答案：什么是找到重叠矩形区域的有效算法