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

Question

我的情况

输入：一组矩形

每个rect都由4个double组成，例如：（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

Answer 1

一种解决方法是将其绘制到画布上！使用半透明颜色绘制每个矩形。.NET运行时将使用优化的本机代码-甚至使用硬件加速器来绘制图形。然后，您必须回读像素。每个像素是背景色，矩形色还是其他颜色？它可能是另一种颜色的唯一方法是两个或更多矩形重叠...如果这太欺骗了，我建议像另外一个回答者一样推荐四叉树或r树。