周边矩形

Question

我想知道有效的方式来解决这个问题：

鉴于给予左上角和右下角ñ矩形，请找的周边N个矩形的联合。

我只有O(N^2)算法，它的速度太慢，所以请找到更有效的算法。

可以假定坐标值是正整数，并且小于100000

编辑： 例如，在这种情况下，周长为30

为O（n^2）算法：

for x=0 to maxx 
    for i=0 to N 
     if lowx[i] = x 
     for j=lowy[i] to highy[i] 
      d[j]++ 
      if d[j] = 1 then ret++ 
     if highy[i] = x 
     for j=lowy[i] to highy[i] 
      d[j]-- 
      if d[j] = 0 then ret++ 
    for y=0 to maxy 
     if d[y] = 0 && d[y + 1] >= 1 then ret++ 
     if d[y] >= 1 && d[y + 1] = 0 then ret++ 

最终ret是答案。

Answer 1

一方面，这个问题的经典方法是基于扫掠线的“布尔合并”算法，它以原始形式建立这些矩形的联合，即构建结果的多边形边界。该算法可以很容易地进行修改，以计算边界的边界而不用物理构建边界。

另一方面，基于扫掠线的“布尔合并”可以对任意多边形输入执行此操作。鉴于在你的情况下输入受限得多（和简化） - 只是一堆等长矩形 - 很可能存在一个更轻量级和更聪明的解决方案。

注意，BTW，这样的矩形的联合可能实际上是多连接的多边形，即其中有孔的区域。

Answer 2

这可能会帮助你的问题的一些情况：

考虑到这一点，

_______ 
|  |_ 
|   | 
|  _| 
|___ | 
    | | 
    |___| 

具有相同周长这样的：

_________ 
|   | 
|   | 
|   | 
|   | 
|   | 
|_________| 

Answer 3

有一个O（N日志N ）时间扫描线算法。应用以下步骤来计算形状的垂直周长。转置输入并再次应用它们来计算水平周长。

对于每个矩形，准备由左侧x坐标（其值为y间隔）键入的开始事件，以及右侧x坐标（其值为y间隔）键入的停止事件。按x坐标排序这些事件并按顺序处理它们。在任何时候，我们都维护一个数据结构，能够报告边界与扫描线相交的点数。在事件点之间的2n-1个间隔中，我们将这个数字乘以该周界的间隔宽度。

我们需要的数据结构在时间O（log n）中支持以下操作。

insert(ymin, ymax) -- inserts the interval [ymin, ymax] into the data structure 
delete(ymin, ymax) -- deletes the interval [ymin, ymax] from the data structure 
perimeter() -- returns the perimeter of the 1D union of the contained intervals 

由于输入坐标是有界整数，因此一种可能的实现方式是通过segment tree。 （有一个扩展的实数输入涉及排序输入的y坐标，并将它们重新映射到小整数）。每个段具有一些相关联的数据

struct { 
    int covers_segment; 
    bool covers_lower; 
    int interior_perimeter; 
    bool covers_upper; 
}; 

，其范围是分段的联合从它下降是存在于输入区间中。 （请注意，很长的段对树的最底层没有任何影响。）

covers_segment的含义是它在分解中包含此段的区间数。 covers_lower的含义是，如果从具有相同较低端点的这一个下降的一个段属于某个间隔的分解，则这是真的。 interior_perimeter的含义是范围内段的一维周长（如上所述）。 covers_upper的含义类似于covers_lower，具有较高端点。

下面是一个例子。

0 1 2 3 4 5 6 7 8 9 

[---A---] 
    [---B---] [-D-] 
     [-C-] 

间隔，是A ([0, 4])和B ([2, 4], [4, 6])和C [3, 4] [4, 5]和D [7, 8] [8, 9]。

   c_s c_l i_p c_u 
[0, 1]   0 F 0 F 
    [0, 2]  0 F 0 F 
[1, 2]   0 F 0 F 
    [0, 4]  1 T 0 T 
[2, 3]   0 F 0 F 
    [2, 4]  1 T 1 T 
[3, 4]   1 T 0 T 
     [0, 8] 0 T 2 F 
[4, 5]   1 T 0 T 
    [4, 6]  1 T 1 T 
[5, 6]   0 F 0 F 
    [4, 8]  0 T 2 F 
[6, 7]   0 F 0 F 
    [6, 8]  0 F 1 F 
[7, 8]   1 T 0 T 
     [0, 9] 0 T 2 T 
[8, 9]   1 T 0 T 

要通过递增（递减）covers_segment插入（删除）的间隔，插入（删除）其组成段。然后，为受影响的所有的祖先，重新计算其他领域如下。

if s.covers_segment == 0: 
    s.covers_lower = s.lower_child.covers_lower 
    s.interior_perimeter = 
     s.lower_child.interior_perimeter + 
     (1 if s.lower_child.covers_upper != s.upper_child.covers_lower else 0) + 
     s.upper_child.interior_perimeter 
    s.covers_upper = s.upper_child.covers_upper 
else: 
    s.covers_lower = true 
    s.interior_perimeter = 0 
    s.covers_upper = true 

要实现perimeter，返回

(1 if root.covers_lower else 0) + 
root.interior_perimeter + 
(1 if root.covers_upper else 0) 

其中root是段树的根。