高效算法返回表面上的所有矩形

Question

我的应用程序中有一个关键性的代码块，涉及到在二维平面上枚举所有矩形。这些矩形之间不相交，并且我必须能够枚举给定矩形边界内的所有矩形。

如果存在，我已经有一个函数来返回给定坐标的矩形。

GetRectangle( int row, int col )

这是我对产生的代码的称呼。

foreach( var rect in GetRectangles( row, col, rowCount, colCount ) ) {
   //..  my processing code here
}

显然，我可以对表面上的每个点调用函数GetRectangle()。 我也可以跳过从上一次调用返回的矩形的宽度，因为我知道它们不相交。 但是，这仍然不够高效。

你是否了解这样的算法？

更新：表面不一定由矩形覆盖，但某些特殊情况下可能会有矩形覆盖。 因此，函数GetRectangle（int row，int col）可能返回null。

将表面视为填充了随机矩形（不相交）的位图。 任务是返回所有在该表面上落在给定框架内（即相交）的矩形。 希望这能澄清问题。

谢谢。

- Kemal Erdogan

---

矩形可以旋转吗？编辑：好的，这个问题已经隐含地得到了回答，抱歉。 - Leif

嗨Kemal，你能更详细地说明一下吗？也许提供一个枚举2D表面上所有矩形的图表会更好？ - Dr. Andrew Burnett-Thompson

为什么你不能在矩形被添加到表面时跟踪它们？我错过了什么吗？ - Chris Dunaway

Answer 1

为了达到最佳效果，将你的矩形集合组织成空间查找结构。在这种情况下，R树可能是一个不错的选择。但如果你不能这样做，而GetRectangle是你唯一拥有的，那么我会这样做：计划维护一个整数列表x_j，其中0 ≤ j < rowCount，x_j是第j行上尚未找到覆盖它的矩形的最左边点。

1. 首先，对于所有的 j，将 x_j 初始化为 0。

2. 如果对于所有的 j，x_j = colCount，则我们完成了。停止。

3. 令 J = min(j | x_j = min(x_i))。然后，x_J 是我尚未找到覆盖它的矩形的最上面最左边的点。

4. 调用 GetRectangle(x_J, J)。如果这不返回一个矩形，则该点未被覆盖。设置 x_J := x_J + 1 并转到步骤 2。

5. 否则，我们有一个以 (x_J, J) 为左上角的矩形。将其宽度称为 w，高度称为 h。对于 J ≤ j < J + h，将 x_j := x_j + w。转到步骤 2。

这是该算法的一个示例运行。 xj 的列表由左侧的数字显示，其中最上面的最左边用粗体突出显示。橙色矩形是在算法的该步骤中发现的那个。

为了在第三步有效地发现最小值，您可能希望将x_j列表保存在堆中。

- Gareth Rees

---

嗨，Gareth，恐怕你的示例运行没有正确地粘贴到你的答案中。你能重新粘贴一下吗？谢谢。 - Kemal Erdogan