我的情况

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