algorithm - 什么是找到重叠矩形区域的有效算法

Question

我的情况

• 输入:一组矩形
• 每个 rect 由 4 个 double 组成，如下所示:(x0,y0,x1,y1)
• 它们不会以任何角度“旋转”，它们都是相对于屏幕“上/下”和“左/右”的“正常”矩形
• 它们是随机放置的——它们可能在边缘接触、重叠或没有任何接触
• 我会有几百个矩形
• 这是用 C# 实现的

我需要找到

• 由它们重叠形成的区域 - Canvas 中被多个矩形“覆盖”的所有区域(例如，有两个矩形，它就是交集)
• 我不需要重叠的几何形状 - 只需要面积(例如:4 平方英寸)
• 重叠不应计算多次 - 例如想象 3 个具有相同大小和位置的矩形 - 它们恰好在彼此之上 - 该区域应计算一次(而不是三次)

例子

• 下图包含三个矩形:A,B,C
• A 和 B 重叠(如破折号所示)
• B 和 C 重叠(如破折号所示)
• 我正在寻找的是显示破折号的区域

-

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC

Answer 1

计算此区域的一种有效方法是使用扫描算法。让我们假设我们通过矩形 U 的并集扫过一条垂直线 L(x):

• 首先，您需要构建一个事件队列 Q，在本例中，它是矩形的所有 x 坐标(左和右)的有序列表。
• 在扫描过程中，你应该维护一个一维数据结构，它应该给你 L(x) 和 U 的交集的总长度。重要的是这个长度在两个连续事件 q 和 q' 之间是常数Q. 因此，如果 l(q) 表示与 U 相交的 L(q+)(即 L 恰好在 q 的右侧)的总长度，则事件 q 和 q' 之间 L 扫过的区域正好是 l(q)* (q' - q).
• 您只需将所有这些扫过的区域相加即可得出总数。

我们仍然需要解决一维问题。您需要一个 1D 结构，它动态计算(垂直)段的并集。动态地，我的意思是你有时添加一个新的段，有时删除一个。

我已经在对此 collapsing ranges question 的回答中进行了详细说明如何以静态方式进行(实际上是一维扫描)。所以如果你想要一些简单的东西，你可以直接应用它(通过重新计算每个事件的并集)。如果你想要更高效的东西，你只需要稍微调整一下:

• 假设您知道段 S₁...S_n 的并集由不相交的段 D₁...D<子>k。添加 S_n+1 非常简单，您只需在 D₁ 的两端中找到 S_n+1 的两端即可。 .D_k.
• 假设您知道段 S₁...S_n 的并集由不相交的段 D₁...D< sub>k，删除片段 S_i(假设 S_i 包含在 D_j 中)意味着重新计算片段的并集D_j 由 S_i 组成(使用静态算法)。

这是您的动态算法。假设您将使用带有日志时间位置查询的排序集来表示 D₁...D_k，这可能是您可以获得的最有效的非专用方法.