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

Question

给定较大矩形R内部的矩形r [],是否有最优的快速算法来确定填充r []之间" 负空间 " 的最小矩形数？

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

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

Answer 1

oosterwal所描述的是梯形分解的一种特殊情况,这是计算几何中一种易于理解的基元,通常用于平面细分中的点位置.它可以在合理常数的时间O(n log n)内实现.

当矩形处于一般位置时,它将返回带有#green rectangles = 3*#蓝色矩形+ 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,顶部,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,机器人,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坐标处的所有事件).