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

Question

给定大矩形 R 内部的矩形 r[ ]，是否有最佳快速算法来确定填充 r[ ] 之间“negative space”的最小矩形数？

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

我怎样才能快速确定像下面这些绿色矩形的列表(这可能不是最佳配置，因此我的帖子):

Answer 1

oosterwal 描述的是梯形分解的特例，梯形分解是计算几何中易于理解的基元，通常用于平面分割中的点定位。它可以在时间 O(n log n) 内以合理的常数实现。

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

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 坐标处的所有事件)。