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

给定较大矩形 R 内的矩形 r[ ]，是否存在最佳快速算法来确定填充“的矩形的最小数量”负空间 https://i.stack.imgur.com/rnboe.png“ r[ ] 之间？

例如，假设紫色矩形内有这三个蓝色矩形：

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

奥斯特瓦尔描述的是梯形分解的一种特殊情况，梯形分解是计算几何中众所周知的原语，通常用于平面细分中的点定位。它可以在 O(n log n) 时间内以合理的常数实现。

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

V - E + F = 1 + # 个连通分量。

Example:

 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, 顶部, 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 坐标处的所有事件）。