什么是找到重叠矩形区域的有效算法 [英] What is an Efficient algorithm to find Area of Overlapping Rectangles

问题描述

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

• 由它们重叠形成的区域 - 画布中一个以上矩形覆盖"的所有区域(例如两个矩形，它将是交集)
• 我不需要重叠的几何形状 - 只需要面积(例如: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

推荐答案

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

An efficient way of computing this area is to use a sweep algorithm. Let us assume that we sweep a vertical line L(x) through the union of rectangles U:

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

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

We still have to solve the 1D problem. You want a 1D structure, which computes dynamically a union of (vertical) segments. By dynamically, I mean that you sometimes add a new segment, and sometimes remove one.

我已经在我对这个折叠范围问题 如何以静态方式进行操作(实际上是一维扫描).所以如果你想要一些简单的东西，你可以直接应用它(通过重新计算每个事件的联合).如果你想要更高效的东西，你只需要稍微调整一下:

I already detailed in my answer to this collapsing ranges question how to do it in a static way (which is in fact a 1D sweep). So if you want something simple, you can directly apply that (by recomputing the union for each event). If you want something more efficient, you just need to adapt it a bit:

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

• assuming that you know the union of segments S₁...S_n consists of disjoints segments D₁...D_k. Adding S_n+1 is very easy, you just have to locate both ends of S_n+1 amongs the ends of D₁...D_k.
• assuming that you know the union of segments S₁...S_n consists of disjoints segments D₁...D_k, removing segment S_i (assuming that S_i was included in D_j) means recomputing the union of segments that D_j consisted of, except S_i (using the static algorithm).

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

This is your dynamic algorithm. Assuming that you will use sorted sets with log-time location queries to represent D₁...D_k, this is probably the most efficient non-specialized method you can get.

这篇关于什么是找到重叠矩形区域的有效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！