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

Question

我的情况

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

我需要找到

• 由它们重叠形成的区域 - 画布中多个矩形"覆盖"的所有区域(例如,具有两个矩形,它将是交叉点)
• 我不需要重叠的几何形状 - 只需要区域(例如:4平方英寸)
• 重叠不应该被计算多次 - 例如,想象3个具有相同大小和位置的rects - 它们是相互重叠的 - 这个区域应该被计算一次(不是三次)

例

• 下图包含三角形矩形: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 +)(即刚好在q的右侧的L)的总长度,则在事件q和q'之间由L扫过的区域恰好是l(q)*(q' - q).
• 你只需要总结所有这些扫过的区域来获得总数.

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

我已经在我对这个崩溃范围问题的答案中详细说明了如何以静态方式(实际上是一维扫描).因此,如果您想要一些简单的东西,您可以直接应用它(通过为每个事件重新计算联合).如果你想要更高效的东西,你只需要调整一下:

• 假设你知道段的并集S ₁ ... S _n由脱离段D ₁ ... D _k组成.添加S _{n + 1}非常简单,只需要在D ₁ ... D _k的末端找到S _{n + 1}的两端.
• 假设你知道段的并集S ₁ ... S _n由脱离段D ₁ ... D _k组成,去除段S _i(假设S _i包含在D _j中)意味着重新计算D的段的并集_j由S _i组成(使用静态算法).

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

Answer 2

一种方法是将它绘制到画布上!使用半透明颜色绘制每个矩形..NET运行时将使用优化的本机代码进行绘制 - 甚至使用硬件加速器.

然后,您必须回读像素.每个像素是背景颜色,矩形颜色还是其他颜色？它可以是另一种颜色的唯一方法是两个或多个矩形重叠...

如果这是一个太多的作弊,我会推荐四叉树作为另一个回答者,或者r-tree.

Answer 3

这是我在TopCoder SRM 160 Div 2中使用的一些快速而脏的代码.

t = top
b = botttom
l = left
r = right

public class Rect
{
    public int t, b, l, r;

    public Rect(int _l, int _b, int _r, int _t)
    {
        t = _t;
        b = _b;
        l = _l;
        r = _r;
    }   

    public bool Intersects(Rect R)
    {
        return !(l > R.r || R.l > r || R.b > t || b > R.t);
    }

    public Rect Intersection(Rect R)
    {
        if(!this.Intersects(R))
            return new Rect(0,0,0,0);
        int [] horiz = {l, r, R.l, R.r};
        Array.Sort(horiz);
        int [] vert = {b, t, R.b, R.t};
        Array.Sort(vert);

        return new Rect(horiz[1], vert[1], horiz[2], vert[2]);
    } 

    public int Area()
    {
        return (t - b)*(r-l);
    }

    public override string ToString()
    {
        return l + " " + b + " " + r + " " + t;
    }
}

Answer 4

最简单的解决方案

import numpy as np

A = np.zeros((100, 100))
B = np.zeros((100, 100))

A[rect1.top : rect1.bottom,  rect1.left : rect1.right] = 1
B[rect2.top : rect2.bottom,  rect2.left : rect2.right] = 1

area_of_union     = np.sum((A + B) > 0)
area_of_intersect = np.sum((A + B) > 1)

在这个例子中,我们创建了两个零矩阵,它们是画布的大小.对于每个矩形,使用矩形占据空间的矩阵填充其中一个矩阵.然后总结矩阵.现在sum(A+B > 0)是联盟的区域,并且sum(A+B > 1)是重叠的区域.此示例可以很容易地推广到多个矩形.

Answer 5

这是我的头顶听起来像它可能工作的东西:

1. 创建一个带有双键的字典,以及一个矩形+布尔值列表,如下所示:

   Dictionary <Double,List <KeyValuePair <Rectangle,Boolean >>> rectangles;

2. 对于集合中的每个矩形,找到x0和x1值的相应列表,并将矩形添加到该列表,对于x0,布尔值为true,对于x1,布尔值为false.这样,您现在可以获得每个矩形进入(true)或离开(false)x方向的所有x坐标的完整列表

3. 从该字典中获取所有键(所有不同的x坐标),对它们进行排序,然后按顺序循环它们,确保您既可以获得当前的x值,也可以获得下一个x值(您需要它们两者) ).这为您提供了单独的矩形条带

4. 保持一组当前正在查看的矩形,这些矩形从空开始.对于在第3点迭代的每个x值,如果矩形注册了真值,则将其添加到集合中,否则将其删除.
5. 对于条带,按y坐标对矩形进行排序
6. 循环通过条带中的矩形,计算重叠距离(我还不清楚如何有效地执行此操作)
7. 计算条带的宽度乘以重叠距离的高度以获得区域

例如,5个矩形,从a到e绘制在彼此之上:

aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
        ddddddddddddddddddddddddddddd
        ddddddddddddddddddddddddddddd
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

这是x坐标列表:

v       v  v   v      v   v         v  v  v   
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

列表将是(其中每个v简单地给出一个从0开始向上的坐标):

0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b

因此每个条带(从上到下排列的矩形):

0-1: a, c
1-2: a, d, c
2-3: a, d
3-4: d
4-5: d, e
5-6: b, d, e
6-7: b, e
7-8: b

对于每个条带,重叠将是:

0-1: none
1-2: a/d, d/c
2-3: a/d
3-4: none
4-5: d/e
5-6: b/d, d/e
6-7: none
7-8: none

我想,上下检查的sort + enter/leave算法的变体也是可行的:

1. 对于我们当前在条带中分析的矩形,从上到下排序,对于具有相同顶部坐标的矩形,按底部坐标对它们进行排序
2. 迭代y坐标,当你输入一个矩形时,将它添加到集合中,当你离开一个矩形时,将它从集合中删除
3. 只要集合有多个矩形,就会有重叠(如果你确保添加/删除所有当前正在查看的顶部/底部坐标相同的矩形,那么多个重叠的矩形就不会成为问题

对于上面的1-2条,你会像这样迭代:

0. empty set, zero sum
1. enter a, add a to set (1 rectangle in set)
2. enter d, add d to set (>1 rectangles in set = overlap, store this y-coordinate)
3. leave a, remove a from set (now back from >1 rectangles in set, add to sum: y - stored_y
4. enter c, add c to set (>1 rectangles in set = overlap, store this y-coordinate)
5. leave d, remove d from set (now back from >1 rectangles in set, add to sum: y - stored_y)
6. multiply sum with width of strip to get overlapping areas

你实际上不必在这里维持一个实际的集合,只需要你在里面的矩形的数量,每当从1到2,存储y,并且每当它从2下降到1时,计算当前的y - 存储y,并总结这个差异.

希望这是可以理解的,正如我所说,这是我的头脑,没有以任何方式进行测试.