algorithm - 给定 4 个 "right"矩形(右边的矩形的边与 x 或 y 平行)，找到它们中的任何一个覆盖的区域

Question

请帮忙。我正在研究具有此要求的算法。

给定 4 个“右”矩形(右矩形的边平行于 x 或 y)，找出它们中的任何一个覆盖的区域

例如，灰色区域被下图中的 4 个矩形中的任何一个覆盖。 enter image description here

我不太明白这个问题。有人可以帮帮我吗？

Answer 1

一种方法是使用 Inclusion-Exclusion principle应用于领域。 这是 3 个矩形的情况:

A = Area( R[0]) + Area( R[1]) + Area( R[2])
  - ( Area( inter( R[0], R[1])) 
    + Area( inter( R[0], R[2]))
    + Area( inter( R[1], R[2]))
    )
  + Area( inter( inter( R[0], R[1]), R[2]))

在哪里

Area(R) gives the area of a rectangle R, and 
inter( R, S) is the rectangle that is the intersection of R and S

4 个矩形的情况会有点乏味，但我怀疑长手编程比使用循环更容易。