矩形覆盖问题

Question

矩形覆盖问题

24

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

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

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

蓝色矩形是模型。

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

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

- den bardadym

也许一张图片可以帮助理解你所说的Ox和Oy的意思。 - pierroz

1

你的矩形是如何表示的？你认为矩形的边界是在矩形内部，还是仅在矩形内部？N的大小大约是多少？N个矩形中是否有任何交叉？你提供的信息越多，我们提供的帮助就越有用。 - High Performance Mark

1

这是一次性的计算，还是您将针对许多“模型”检查相同的N个矩形？ - Kobi

我只有一个模型-矩形。 - den bardadym

我终于找到了一种平均时间复杂度为O(n log n)的算法，它基于对qsort算法的改进。 - Matthieu M.

显示剩余12条评论

12个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas Ahle · Answer 1

你知道计算矩形并的常见最坏时间复杂度为O(nlogn)的算法吗？

在这里，你只需要计算两个面积：

你的N个矩形的面积
你的N个矩形和模型的面积

如果这些面积相等，则模型完全被覆盖，否则没有。

- Will · Answer 2

这里有一个使用一些内存的O(n lg n)运行时间方法。

使用示例：

我们仅对包含“模型”矩形的场景子部分感兴趣；在此示例中，“模型”矩形是1,1 -> 6,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)。

这是我对如何高效地找到重叠矩形的面积问题的回答之一。