N个矩形的并集周长 [英] Perimeter of union of N rectangles

问题描述

我想知道解决此问题的有效方法:

I want to know the efficient way to solve this problem:

给出给定左上角和右下角的N个矩形，请找到N个矩形的并集周长.

Given N rectangles that given a top-left and bottom-right corner, please find the perimeter of union of N rectangles.

我只有O(N^2)算法，而且速度太慢，因此请找到更有效的算法.

您可以假设坐标值为正整数且小于100000.

I only have O(N^2) algorithm and it's too slow, so please find more efficient algorithm.

You can assume that coordinate value is positive integer and less than 100000.

例如，在这种情况下，周长为30.

For example, in this case, the perimeter is 30.

一种O(n ^ 2)算法:

An O(n^2) algorithm:

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++

最后的答案就是答案.

推荐答案

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

There's an O(n log n)-time sweepline algorithm. Apply the following steps to compute the vertical perimeter of the shape. Transpose the input and apply them again to compute the horizontal perimeter.

对于每个矩形，准备一个以x坐标为y间隔的左x坐标作为起点的开始事件，以一个以yinterval为值的右x坐标作为key的停止事件.通过x坐标对这些事件进行排序，并按顺序处理它们.在任何时候，我们都保持一种数据结构，该结构能够报告边界与扫掠线相交的点的数量.在事件点之间的2n-1间隔上，我们将此数字乘以间隔宽度到周长.

For each rectangle, prepare a start event keyed by the left x-coordinate whose value is the y-interval, and a stop event keyed by the right x-coordinate whose value is the y-interval. Sort these events by x-coordinate and process them in order. At all times, we maintain a data structure capable of reporting the number of points at which the boundary intersects the sweepline. On the 2n - 1 intervals between event points, we add this number times the width of the interval to the perimeter.

我们需要的数据结构在时间O(log n)中支持以下操作.

The data structure we need supports the following operations in time 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坐标进行排序并将其重新映射为小整数.)每个段都有一些关联的数据

Since the input coordinates are bounded integers, one possible implementation is via a segment tree. (There's an extension to real inputs that involves sorting the y-coordinates of the input and remapping them to small integers.) Each segment has some associated data

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

其作用域是输入间隔中存在的从其继承的段的并集. (请注意，很长的一段不会影响树的最叶级.)

whose scope is the union of segments descended from it that are present in the input intervals. (Note that a very long segment has no influence on the leafmost levels of the tree.)

covers_segment的含义是它是分解中具有此段的间隔数. covers_lower的含义是，如果从该段下降的具有相同较低端点的段之一属于某个区间的分解，则为true. interior_perimeter的含义是范围内段的1D周长(如上所述). covers_upper的含义类似于covers_lower，具有较高的端点.

The meaning of covers_segment is that it's the number of intervals that have this segment in their decomposition. The meaning of covers_lower is that it's true if one of the segments descended from this one with the same lower endpoint belongs to the decomposition of some interval. The meaning of interior_perimeter is the 1D perimeter of segments in scope (as described above). The meaning of covers_upper is akin to covers_lower, with the upper endpoint.

这是一个例子.

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插入(删除)其组成段.然后，对于受影响细分的所有祖先，重新计算其他字段，如下所示.

To insert (delete) an interval, insert (delete) its constituent segments by incrementing (decrementing) covers_segment. Then, for all ancestors of the affected segments, recalculate the other fields as follows.

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是段树的根.

这篇关于N个矩形的并集周长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！