Разбор задачи на Reddit
https://www.reddit.com/comments/zaa0v.
Адаптировал под случай который указан в условии:
прямоугольник определяется значениями (x1, y1, x2, y2), где (x1, y1) - верхний левый угол, (x2, y2) - правый нижний угол.
x1,y1───────────┐
│ │
│ │
│ │
│ │
└───────────x2,y2
Алгоритм слудующий: находим сумму площадей всех прямоугольников и эту сумму вычитаем из площади полотна.
Площадь прямоугольника, в нашем случае, равна (x2 - x1) * (y1 - y2).
Случай 1. Прямоугольники не пересекаются.
Прямоугольники (0,3,4,0), (4,7,7,3) и (7,3,10,0) будут выглядеть примерно так:
* * *
* * *
* * *
* * *
* * * * * * *
* * * * * * *
* * * * * * *
Общая площадь этих трех прямоугольников проста для вычисления, это всего лишь сумма площадей каждого отдельного прямоугольника: (4 * 3) + (3 * 4) + (3 * 3)
Случай 2. Прямоугольники пересекаются, общее пересечение имеют 2 прямоугольника.
Рассмотрим три прямоугольника (0,3,4,0), (2,5,5,1) и (4,7,7,4):
* * *
* * *
* * + * *
* * *
* * + + *
* * + + *
* * * *
Вы видите, что прямоугольники пересекаются (области, где они пересекаются, отмечены символом "+" вместо "*"). Поэтому, если мы просто вычислим сумму площадей, как мы делали раньше, 12 + 12 + 9, мы получим слишком большое значение (33 вместо 28), потому что мы рассчитываем области с пересечением дважды.
Чтобы получить правильный ответ, мы должны вычесть области, в которых пересекаются два прямоугольника: (12 + 12 + 9) - (4 + 1) = 28.
Случай 3. Общее пересечение имеют сразу несколько прямоугольников.
Рассмотрим прямоугольники (0,3,4,0), (2,5,5,1) и (3,3,0,6)
* * *
* * *
* * + x + *
* * + x + *
* * * + * *
Теперь три прямоугольника перекрываются в точках, отмеченных символом "x" (как и раньше, знак "+", где перекрываются только два прямоугольника). Сумма площадей всех трех треугольников: 12 + 12 + 9. Затем мы должны вычесть сумму всех площадей, где пересекаются два прямоугольника 4 + 3 + 4 (прямоугольники 1 и 2 пересекаются в области с площадью 4, прямоугольники 1 и 3 пересекаются в области с площадью 3, и прямоугольники 2 и 3 пересекаются в области с площадью 4). Мы получили (12 + 12 + 9) - (4 + 3 + 4).
Однако, вычитая все области пересечения двух прямоугольников, мы вычитаем область, в которой три прямоугольника пересекаются (обозначено "x"), три раза. Поэтому мы должны добавить площадь пересечения трех прямоугольников, чтобы получить правильный результат. Таким образом, общая площадь, покрытая прямоугольниками:
A = (12 + 12 + 9) - (4 + 3 + 4) + (2) = 33 - 11 + 2 = 24
Общее правило, на самом деле, довольно простое. Если S1 - сумма площадей всех прямоугольников, S2 - сумма всех областей, где пересекаются два прямоугольника, S3 - сумма всех областей, где пересекаются три прямоугольника, S4 - сумма всех областей, где пересекаются четыре прямоугольника и т.д., значение общей площади равно:
A = S1 - S2 + S3 - S4 + S5 - S6 + S7 - S8 + ...
Это известно в математике как
принцип включений-исключений, потому что вы чередуете включение и исключение областей.
Значения в нашем примере соответствуют:
S1 = 12 + 12 + 9
S2 = 4 + 3 + 4
S3 = 2
Пример вычисления с использованием рекурсии
def bounding_box(rects):
return (min(r[0] for r in rects),
max(r[1] for r in rects),
max(r[2] for r in rects),
min(r[3] for r in rects))
def area(rect):
a, b, c, d = rect
return (c - a) * (b - d)
def clip(bb, rects):
if not rects:
return []
(x1, y1, x2, y2) = rects[0]
rs = rects[1:]
(a1, b1, a2, b2) = bb
if a1 == a2 or b1 == b2:
return []
if a1 >= x2 or a2 <= x1 or y1 <= b2 or y2 >= b1:
return clip(bb, rs)
result = [(max(a1, x1), min(b1, y1), min(a2, x2), max(b2, y2))]
return result + clip(bb, rs)
def cover(bb, rects):
if not rects:
return 0
rc = rects[0]
rs = rects[1:]
(a1, b1, a2, b2) = bb
(x1, y1, x2, y2) = rc
top = (a1, b1, a2, y1)
bottom = (a1, y2, a2, b2)
left = (a1, y1, x1, y2)
right = (x2, y1, a2, y2)
sum_area = sum(cover(x, clip(x, rs)) for x in [top, bottom, left, right])
return area(rc) + sum_area
def main():
width_canvas = 10
height_canvas = 10
rect1 = (0, 3, 4, 0)
rect2 = (2, 5, 5, 1)
rect3 = (3, 3, 6, 0)
rs = [rect1, rect2, rect3]
painted_area = cover(bounding_box(rs), rs)
canvas_area = width_canvas * height_canvas
unpainted_area = canvas_area - painted_area
print("Canvas area:", canvas_area)
print("Painted area:", painted_area)
print("Unpainted area:", unpainted_area)
if __name__ == '__main__':
main()
Код на GitHub Gist
Код на GitHub с тестами 
Но всё-таки, как я уже сказал, метод не совсем оптимален, поэтому ищутся и другие варианты решения.
