1

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

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

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

如果我们有

(0,0,50,75)

显然这不会发生，因为它只覆盖了一半的区域。如果我们有

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

那么这确实有效，因为两个矩形都将有效地覆盖整个(100,75).

我试过什么

我试图（没有工作）制作一个多维布尔数组：

bool area[10000][7500];

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

最终，我检查该区域中的所有布尔值是否都是true.

事实证明这是非常愚蠢的。你能帮我找到更好的方法吗？

4

3 回答 3

4

我认为这样的策略会奏效：

  1. 扔掉完全超出您所在区域的所有矩形
  2. 沿着列表中矩形的边缘相对于一个轴将您的区域拆分为较小的矩形
  3. 将步骤 2 中创建的区域矩形列表沿覆盖列表中矩形的边缘相对于另一个轴拆分
  4. 您现在有两个矩形列表，其中封面列表中必须有一个完全覆盖每个区域矩形
于 2013-04-23T23:17:24.417 回答
2

我相信您的“位图”尝试由于（通常的）浮点舍入问题而失败。不幸的是，您对此无能为力。

现在对于正确的算法，我将使用减法技术来处理它。

  • 让我们称您的初始矩形集为 R。
  • 初始化第二组矩形 S，它最初包含一个覆盖整个区域的矩形。
  • 对于 R 中的每个矩形：
    • 对于 S 中的每个矩形：
      • 如果两个 R 和 S 矩形相交，则将 S 矩形替换为所需数量的矩形（如果我没记错的话，为 0 到 4 个）覆盖 S 矩形左侧的非相交部分。
      • 继续迭代 S，注意不要为刚刚添加的新 S 矩形计算任何内容（我们已经知道它不会与当前 R 矩形相交）。
    • 继续迭代 R，这次考虑新的 S 矩形，直到：
      • S 中没有剩余矩形，在这种情况下，您的 R 矩形确实覆盖了整个区域。
      • 或者，您遍历了所有 R 矩形，但仍有 S 矩形，在这种情况下，您的 R 矩形不会覆盖整个区域。

至于复杂性，我不确定它与@500-Internal-Server-Error 或@Tommy 的解决方案相比如何，但是嘿，至少我设法想出了一些东西，当我阅读时我认为我做不到一开始你的问题——我通常不擅长空间的东西。:)

于 2013-04-23T23:36:14.633 回答
1

与 500 - Internal Server Error's 在概念上非常相似的方法可以避免最后一步所暗示的 O(n^2) 搜索：

  1. 从覆盖集中构建每个矩形的垂直边界列表；
  2. 假设有 n 个边界，你在源矩形上有 n+1 个垂直条要考虑；
  3. 对于每个条带，获取与其重叠的所有矩形的列表（您可以在 O(n) 时间内通过从矩形推到垃圾箱而不是向后搜索来完成此操作）；
  4. 从左到右对列表进行排序（即 O(n log n)）；
  5. 遍历排序列表并尝试找到一个间隔，其中一个跨度结束，直到稍后才开始（另一个 O(n) 任务）。

如果您找到合适的间隙，则不会覆盖原件。如果你不这样做，那就是。顺便说一下，这基本上就是跨度缓冲的工作原理。

于 2013-04-23T23:27:43.783 回答