logo标签列表

N个矩形的并集周长

algorithmdata-structuressegment-tree
3
我希望了解如何高效地解决这个问题：

给定N个矩形，每个矩形都有一个左上角和右下角，请找出N个矩形联合的周长。

我只有O（N ^ 2）的算法，速度太慢了，请寻找更有效的算法。

您可以假设坐标值为正整数且小于100000。
编辑：
例如，在这种情况下，周长为30。

Example

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

最终的结果是答案。
它们是否相互包含？ - huseyin tugrul buyukisik
@huseyintugrulbuyukisik 我添加了示例，请查看。 - square1001
请告诉我们，为什么您认为我们会为您编写代码，而您自己却无法尝试编写任何代码？ - Ed Heal
@EdHeal 我写了一个O(N^2)的伪代码。 - square1001
3个回答
6
有一种O(n log 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

由于输入坐标是有界整数，一个可能的实现方式是使用 线段树。 （对于涉及实数输入的情况，可以通过将输入的y坐标排序并将其重新映射到小整数来进行扩展。）每个线段都有一些关联数据。

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

其范围是从它下降的细分段的并集，这些细分段存在于输入间隔中。（请注意，很长的段对树的最底层没有影响。）

covers_segment 的含义是具有此细分段的间隔数量。 covers_lower 的含义是如果与相同下端点的此段下降自此的细分段之一属于某个间隔的分解，则为真。 interior_perimeter 的含义是所描述的范围内段的1D周长。 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是线段树的根节点。

3
这可能对您的问题有所帮助：
请考虑以下内容，
 _______
|       |_
|         |
|        _|
|___    |
    |   |
    |___|

这个图形的周长与此相同：

 _________
|         |
|         |
|         |
|         |
|         |
|_________|
1
一方面，这个问题的经典解决方案是基于扫描线的“布尔合并”算法，它的原始形式建立这些矩形的并集，即建立结果的多边形边界。该算法可以很容易地修改为在不实际构建它的情况下计算结果边界的周长。
另一方面，基于扫描线的“布尔合并”可以针对任意多边形输入执行此操作。鉴于在您的情况下输入更加受限（并且简化）-只是一堆等距矩形-可能存在更轻量级和更聪明的解决方案。
顺便提一下，这些矩形的联合可能实际上是一个多连通多边形，即具有孔洞的区域。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接