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

Question

我的情况输入：一组矩形每个rect都由4个double组成，例如：（x0，y0，x1，y1）它们不会以任何角度“旋转”，它们都是相对于屏幕“上/下”和“左/右”的“普通”矩形它们是随机放置的-它们可能在边缘接触，重叠或没有任何接触我将有数百个矩形这是用C＃实现的我需要找到由它们的重叠部分形成的区域-画布中一个以上矩形“覆盖”的所有区域（例如，对于两个矩形，将是交集）我不需要重叠的几何图形-只需面积（例如：4平方英寸）重叠不应被计算多次-例如，假设3个大小和位置相同的矩形-它们彼此重叠-该区域应被计算一次（而不是三次）例下图包含三个矩形：A，B，CA和B重叠（如破折号所示）B和C重叠（如破折号所示）我正在寻找的是显示破折号的区域--AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA--------------BBBAAAAAAAAAAAAAAAA--------------BBBAAAAAAAAAAAAAAAA--------------BBBAAAAAAAAAAAAAAAA--------------BBB                BBBBBBBBBBBBBBBBB                BBBBBBBBBBBBBBBBB                BBBBBBBBBBBBBBBBB                BBBBBB-----------CCCCCCCC                BBBBBB-----------CCCCCCCC                BBBBBB-----------CCCCCCCC                      CCCCCCCCCCCCCCCCCCC                      CCCCCCCCCCCCCCCCCCC                      CCCCCCCCCCCCCCCCCCC                      CCCCCCCCCCCCCCCCCCC

Answer 1

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

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

如果这太欺骗了，我建议像另外一个回答者一样推荐四叉树或r树。