给定一个矩形区域和一组矩形，检查整个区域是否被它们覆盖

Question

这里的所有值都是具有最多两个浮点数的实数。

假设我们有一个矩形区域，。

然后给你一组矩形。我如何检查这些矩形是否合并，覆盖整个区域？

如果我们有

(0,0,50,75) 

显然，这不会发生，因为它仅覆盖一半的面积。如果我们有

(0,0,50,75) 
(50,0,50,75) 

那么这样做的工作，因为这两个矩形将有效地覆盖整个(100,75)。

有什么我试图

我试图（没有工作），使布尔的多维数组：

bool area[10000][7500]; 

这些区域的尺寸乘以减去100，这样我就不必处理浮点数。然后我只是迭代我的每个矩形（它们的值也乘以100），并且对于它们中的每个“像素”，我将布尔值变成true。

最终，我检查该区域的所有布尔值是否为true。

这被证明是非常愚蠢的。你能帮我找到一个更好的方法来做到这一点？

Answer 1

我觉得像这样的战略将工作：

1. 扔掉是完全你的任何区域外的矩形
2. 分裂您的区域在较小的矩形沿着矩形的边缘相对列表中一个轴
3. 分割在步骤2中沿相对封面列表中的矩形的边缘创建到其他轴
4. 你现在有长方形的两份名单，其中必须有一个在封面列表覆盖区域的矩形的列表每一个E片区矩形完全

Answer 2

一个概念上非常相似的方法来500 - 内部服务器错误的，避免了为O（n^2）由最终步搜索暗示是：

1. 建立垂直列表覆盖集合中每个矩形的边界;
2. 假设有n个边界，你在源矩形上有n + 1个垂直条带要考虑;
3. 每个条，得到重叠的所有矩形的列表（您可以通过从矩形推到垃圾桶，而不是向后搜索在O（n）的时间做到这一点）;
4. 从左到右排列列表（即O（n log n））;
5. 经过排序的列表，并设法找到一个缺口，其中一个跨度结束，没有别的开始，直到后来小（另一个为O（n）的任务）。

如果你找到一个合适的差距那么原来不是盖的。如果你不这样做。顺便说一下，这实际上是跨度缓冲如何工作的。

Answer 3

我相信你的“位图”的尝试失败，因为的（通常）浮点舍入的问题。不幸的是，你很难做到这一点。

现在的算法正确的，我会用减法技术接近它。

• 让我们把你的初始设置矩形R.
• 初始化第二组矩形S的最初包含单个矩形覆盖整个区域。
• 对于R中每个矩形：
  • 对于S中的每个矩形：
    • 如果两个R和S的矩形相交，替换与尽可能多的矩形在S矩形根据需要（0至4，如果我没有错误）覆盖从S矩形左侧的非相交部分。
    • 继续遍历S，注意不要计算你刚才添加的新的S矩形（我们已经知道不与的当前R矩形相交的）东西。
  • 继续遍历R，此时服用新的S矩形进去，直到：
    • 没有矩形留在S，在这种情况下，你的[R矩形做覆盖整个区域。
    • 或者，您遍历所有的R矩形且仍有s ^矩形离开，在这种情况下，你[R矩形不包括整个区域。

至于复杂，我不知道如何比较@ 500 - 内部 - 服务器错误或@汤米的解决方案，但是，嘿，至少我设法拿出东西，当我在开始阅读你的问题时，我认为我没有想到 - 我通常不太擅长空间问题。 :)