Алгоритм / Java-программа для расчета площади пересечения для n перекрывающихся прямоугольников, где n> 2

Question

Как рассчитать общую площадь / площадь пересечения между n не перекрывающимися прямоугольниками, я получаю логику для 2 прямоугольников, но путаю с n прямоугольниками

Answer 1

наивное решение:

Возможно, это не самое эффективное / оптимальное решение, но его довольно легко понять

У вас есть логика для пересечения 2 прямоугольников. Это пересечение само по себе является прямоугольником. Если вы хотите вычислить пересечение с третьим прямоугольником, вычислите пересечение между третьим прямоугольником и прямоугольником, образованным пересечением двух предыдущих прямоугольников

Edit:

Как сказал @Kaddath в комментарии, это решение работает, только если прямоугольники выровнены, иначе это может быть другая форма

Answer 2

Найдите правый левый край любого из прямоугольников. Это левый край полученного пересечения, который также будет прямоугольником. Сделайте аналогично для остальных трех сторон.

Не забудьте принять во внимание особый случай: пересечения не должно быть. Это происходит, если любой прямоугольник имеет правый край слева от вычисленного левого края или любой прямоугольник имеет нижнюю точку выше, чем вычисленная верхняя часть результата.

Я предположил, что прямоугольники выровнены с вашей системой координат (как было бы обычно на дисплее компьютера). Если их можно повернуть на любой угол, это намного сложнее.

Answer 3

R1 ∩ R2 ∩ R3 = ( (R1 ∩ R2) ∩ R3) 

вы уже знаете, как сделать пересечение двух прямоугольников.