矩形之间最佳负空间算法？

Question

给定大矩形R内的小矩形r[ ]，是否存在一种最优快速算法来确定填充r[ ]之间"negative space"的最小矩形数量？

例如，给定这三个蓝色矩形在紫色矩形内:

我如何快速确定像下面这样的绿色矩形列表（可能不是最佳配置，因此我发布了帖子）：

- jedierikb

---

看起来你的示例算法是从上到下扫描以寻找障碍物。当它发现一个障碍物时，它会完成当前的填充矩形并开始两个新的矩形。当它找到一个障碍物的结束时，它会完成当前相邻的填充矩形，并开始一个更大的新矩形。 - oosterwal

这可能与更一般的问题有关，即给定一组矩形，找到精确覆盖这些矩形的最小矩形数。我不确定是否存在解决该问题的算法，但如果有一种有效的解决方法，它应该能够为您提供一个高效的解决方案。 - templatetypedef

Answer 1

oosterwal所描述的是梯形分解的特殊情况，这是计算几何中一个众所周知的原始问题，通常用于平面子细分中的点定位。它可以在O(n log n)的时间内实现，并具有合理的常数。

当矩形处于一般位置时，它将返回一个“矩形化”结果，其中#绿色矩形=3 * #蓝色矩形+1，这是最优的。每个蓝色角落的L形邻域必须被一个绿色线段沿着一个方向或另一个方向切割（一般位置：我们不能为两个蓝色矩形使用相同的线段），因此对于每个蓝色矩形，我们添加4条绿色边缘8条绿色边缘和4个顶点（4个新边缘加上4个细分的边缘），在该过程中减少连接组件的数量1。根据多面体公式，结果是更多的三角形：

V-E+F=1+#连接组件。

---

例子：

 0123456789abc
0+-----------+
1|           |
2|  +--+     |
3|  |R | +-+ |
4|  +--+ |S| |
5|       | | |
6| +--+  | | |
7| |T |  +-+ |
8| +--+      |
9+-----------+

我们正在从上到下运行一条扫描线。这些事件是：

# (y, whichside, xmin, xmax)
(2, top, 3, 6)  # R
(3, top, 8, a)  # S
(4, bot, 3, 6)  # R
(6, top, 2, 5)  # T
(7, bot, 8, a)  # S
(8, bot, 2, 5)  # T

我们建立了一个按照 x 有序的二叉搜索树，用于保存部分构建好的绿色矩形。我将它写成列表形式。

# (xmin, xmax, ymin)
(0, c, 0)

现在我们开始处理事件。首先是 (2, top, 3, 6)。我们发现它嵌套在目前唯一的绿色矩形内，即 (xmin=0, xmax=c, ymin=0, ymax=2)。（只要蓝色矩形不相交，蓝色区间总是嵌套的。）我们在蓝色矩形两侧各开始一个新的绿色矩形，并且搜索树包含

(0, 3, 2) (6, c, 2)

现在我们处理 (3, top, 8, a)。区间 (8, a) 嵌套在 (6, c) 中，因此我们完成了另一个矩形（xmin=6，xmax=c，ymin=2，ymax=3），并开始了两个新的：

(0, 3, 2) (6, 8, 3) (a, c, 3)

现在我们处理(4, bot, 3, 6)。这将结束其左右两侧的绿色矩形，(xmin=0, xmax=3, ymin=2, ymax=4）和 (xmin=6, xmax=8, ymin=3, ymax=4）。搜索树为

(0, 8, 4) (a, c, 3)

我想这个时候应该很清楚了。这是已完成的矩形化:

 0123456789abc
0+-----------+
1|           |
2+--+--+-----|
3|  |R |-+-+-|
4+--+--+-|S| |
5|       | | |
6+-+--+--+ | |
7| |T +--+-+-+
8+-+--+------+
9+-----------+

关于处理退化情况的说明：将具有相同y坐标的顶部事件放在底部事件之前，并抑制面积为零的矩形。通常仍会存在“不必要”的矩形，更复杂的事件处理器可以避免这种情况（通过同时处理给定y坐标处的所有事件）。

- a dabbler

---

你能稍微详细解释一下吗？这看起来真的很酷，我很想看到更多关于它的细节。 - templatetypedef

正如oosterwal所说，您可以通过从上到下排序和处理蓝色水平线段来执行平面扫描。当您遇到蓝色顶部时，终止其上方的绿色矩形并开始两个新的矩形。当您遇到蓝色底部时，终止左右两侧的绿色矩形并开始一个新的矩形。这些操作中的每一个都是O(log n)，使用二叉树按x坐标顺序存储活动的绿色矩形。不过，处理退化情况有点麻烦... - a dabbler

好的，这么说“连接的组件”总是减少1有点粗糙。然而，在开始时，“蓝色矩形的数量+1”，在最后变成了1，所以数学上仍然成立；我们只需要分摊一下。 - a dabbler

我需要一些高层次的伪代码...我很难解析这个答案。 - jedierikb