矩形的算法之间的最优负空间？ [英] optimal negative space between rectangles algorithm?

问题描述

由于矩形 - [R []放大矩形R里面，有一个最佳的快速算法确定矩形是填写的最小数量的负空间R之间的[]？

Given rectangles r[ ] inside of larger rectangle R, is there an optimal speedy algorithm for determining the minimum number of rectangles that fill in the "negative space" between r[ ]?

例如，鉴于这三个蓝色矩形紫色长方形内：

For example, given these three blue rectangles inside of the purple rectangle:

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

How could I quickly determine a list of rectangles like these in green below (which may not be the optimal configuration, hence my post):

推荐答案

什么oosterwal描述为梯形分解，一个易于理解的原始计算几何通常用于点定位在一个平面细分一个特例。它可以在时间为O来实现（N log n）的一个合理的常数。

What oosterwal describes is a special case of trapezoidal decomposition, a well-understood primitive in computational geometry typically used for point location in a planar subdivision. It can be implemented in time O(n log n) with a reasonable constant.

在矩形是一般的位置，它会返回一个rectangulation与＃绿色长方形= 3 *＃蓝色的矩形+ 1，这是最佳的。每个蓝色的角落L形附近的必须的被压在一个方向或另一个由绿色段（总的立场：我们不能用同一网段的两个蓝色矩形），所以对于每个蓝色矩形，我们在这个过程中添加<打击> 4绿边 8绿色的边缘地带和4个顶点（4新边加4细分），减少连接元件的数量由1。结果由多面体公式为3个面（矩形）：

When the rectangles are in general position, it will return a "rectangulation" with # green rectangles = 3 * # blue rectangles + 1, and this is optimal. The L-shaped neighborhood of each blue corner must be cut in one direction or the other by a green segment (general position: we can't use the same segment for two blue rectangles), so for each blue rectangle, we add 4 green edges 8 green edges and 4 vertices (4 new edges plus 4 subdivided), decreasing the number of connected components by 1 in the process. The result by the polyhedral formula is 3 more faces (rectangles):

v - 输出E + F = 1 +＃连接组件

V - E + F = 1 + # connected components.

例如：

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

我们正在运行的扫描线从顶部到底部。该事件是

We're running a sweep line from top to bottom. The events are

# (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二叉搜索树持有的部分建绿色长方形。我会写它作为一个清单。

We set up a binary search tree ordered by x that holds the partially constructed green rectangles. I'll write it as a list.

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

现在我们开始处理事件。第一种是（2，顶端，3，6）。我们发现，它的嵌套唯一的绿色矩形内，到目前为止，（XMIN = 0，XMAX = C，YMIN = 0，YMAX = 2）。 （蓝色区间始终巢只要蓝色矩形不相交）。我们启动两个新的绿色长方形，一个在蓝色矩形的两侧，和搜索树包含

Now we start processing events. First is (2, top, 3, 6). We find that it's nested inside the only green rectangle so far, (xmin=0, xmax=c, ymin=0, ymax=2). (The blue interval always nests as long as the blue rectangles don't intersect.) We start two new green rectangles, one on each side of the blue rectangle, and the search tree contains

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

现在我们处理（3，顶部，8，一个）。的间隔（8，一个）的内部巢（6，c）中，所以我们完成另一个矩形（XMIN = 6，XMAX = C，YMIN = 2，YMAX = 3），并开始两个：

Now we process (3, top, 8, a). The interval (8, a) nests inside (6, c), so we finish another rectangle (xmin=6, xmax=c, ymin=2, ymax=3) and start two more:

(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）。搜索树是

Now we process (4, bot, 3, 6). This ends the green rectangles to its left and right, (xmin=0, xmax=3, ymin=2, ymax=4) and (xmin=6, xmax=8, ymin=3, ymax=4). The search tree is

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

我觉得事情应该清楚这一点。这是成品rectangulation：

I think things should be clear by this point. Here is the finished rectangulation:

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

在处理简并的说明：把底事件具有相同的Y坐标和副preSS矩形零区域顶级赛事之前。仍然会有在一般的不必要的矩形，其中一个更复杂的事件处理器可避免（通过处理所有事件在给定的y坐标在一次）。

A note on handling degeneracies: put bottom events before top events with the same y-coordinate, and suppress rectangles with zero area. There will still be "unnecessary" rectangles in general, which a more sophisticated event processor could avoid (by handling all events at a given y-coordinate at once).

这篇关于矩形的算法之间的最优负空间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！