检测矩形重叠区域的高效算法是什么？

12 浏览
0 Comments

检测矩形重叠区域的高效算法是什么？

我的情况

  • 输入：一组矩形
  • 每个矩形由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

0