N个矩形的并集周长

Question

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

给定具有左上角和右下角的 N 个矩形，请找出 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

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

对于每个矩形，准备一个由值为 y 间隔的左 x 坐标键控的开始事件，以及由值为 y 间隔的右 x 坐标键控的停止事件。按 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

由于输入坐标是有界整数，因此一种可能的实现是通过线段树。（实际输入有一个扩展，涉及对输入的 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])andB ([2, 4], [4, 6])和C [3, 4] [4, 5]and 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是线段树的根。