Как найти общую площадь нескольких прямоугольников

Зависит от того, пересекаются ли эти прямоугольники или нет. Если же ко всему прочему эти прямоугольники произвольно “ориентированы” на плоскости, то задача усложняется еще больше.

В целом алгоритм простой:
1) Находим сумму площадей прямоугольников (S0)
2) Находим сумму площадей попарных пересечений прямоугольников (S1)
3) Находим сумму площадей попарных пересечений фигур из п. 2 (S2) и т. д.
Ответом будет сумма: S0 – S1 + S2 – S3 + .

Либо можно поступить просто. Если прямоугольники расположены достаточно “компактно”, то можно найти вмещающий их прямоугольник, в нем случайным образом накидать N точек, из этого множества выделить n точек, попавших внутрь какого-нибудь из интересующих нас прямоугольников, и полученное отношение n/N даст оценку площади (метод Монте-Карло).

Либо можно избавиться от вероятностного характера оценки из предыдущего пункта, введя на вмещающем прямоугольнике дискретную двумерную сетку с шагом h, и подсчитав количество узлов сетки, попавших внутрь рассматриваемых прямоугольников. Но вычислительная сложность этого алгоритма будет O((1/h)^2).

Алгоритм поиска площади нескольких прямоугольников

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

Давайте возьмем гипотетическую задачу:

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

• Первым делом требуется создать 2 массива, один одномерный, другой двумерный. В первом массиве мы будем хранить координаты всех точек, второй будет представлять собой координатную плоскость
• Так же, нам надо запомнить самую маленькую и самую большую координату по оси ординат. Тоже и с осью абсцисс. Этими точками мы задаем размеры второго массива. Это нам надо для того, чтобы убедиться, что область, которую мы будем рассматривать (назовем ее областью А), полностью покрывает нашу зону интереса, что является необходимым и достаточным условием.
• Следом, мы проецируем прямоугольники на область А, т.е. координаты прямоугольников будут эквивалентны номерам некоторым элементам массива со смещением.
• Затем начинаем заполнять этот массив. Элементы этого массива могут принимать два значения: 0 и 1. 0 означает, что это «клеточка» не принадлежит ни одному прямоугольнику, 1- принадлежит. Проверяем элементы области А на принадлежность прямоугольнику для каждого отдельного прямоугольника. 1 не может быть заменен на 0. 0 может быть заменен на 1. Таким образом, мы получим матрицу, которая будет состоять из нулей и единиц, где единицами будут «нарисованы» прямоугольники.
• Последним пунктом, считаем сумму всех элементов массива. Задача решена!

В заключение статьи хотелось бы рассказать об плюсах и минусах данного алгоритма.

Плюсы:

— Скорость работы при прочих равных напрямую зависит от количества данных прямоугольников и их разброса.
— Нет кучи условных операторов, которые сильно портят жизнь.
— Не надо отслеживать пересечения прямоугольников, те «клетки», которые принадлежат двум или более прямоугольникам все равно будут посчитаны только 1 раз.
— Высокая читаемость кода (при достаточно прямых руках).
— Простота реализации.
— Одинаковый алгоритм обработки для всех частей координатной плоскости.

Минусы:

— Требует достаточно хорошего пространственного воображения.
— Наличие достаточно большого количества циклов.
— Не подходит для большинства задач даже с незначительно измененными условиями.

<span>но является простым так как последнее число степени четное</span>

1) 3 м 46 смХ75=3,46мХ75=259,5м. В одном метре 100 см, значит 46 см=0.46м
2) 196 км 20 м:9= 196.02км:9=21.78км В одном километре 1000 м, следовательно 20м=0.020км=0.02км
3) 3т 700 кг Х 97= 3.7тХ97=358.9т В одной тонне 1000кг, значит 700 кг=0.700т=0.7т 
4) 50кг 160г:16= 50.16:16=3.135кг В одном кг 1000 кг, следовательно 160г=0.160кг=0.16кг
5) 19 ч 36 мин:12= 19.6ч:12= 1 целая 19/30 В одном часе 60 минут. Если поделить 1 час на 10 частей, где одна часть будет составлять 1/10 всего и где одна часть = 6(60:10=6), то 36 минут = 36:6=6(6/10 частей или 0.6 часа)
6) 6 ц 25 кгХ15=6,25цХ15=93.75 ц В одном центнере 100 кг, значит 25 кг=0.25ц

1)48:3*2=32(км)- проехали в 1-ый день.
2)48-32=16(км)- проехали во 2-ой день.

9-(9+9+9):9=6   
9-(9:9)-(9:9)=7  
9+9-(9:9)-9=8

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

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

Соответственно, при добавлении прямоугольника в таблицу можно выбрать, прибавить площадь этого прямоугольника к общей площади или же вычесть.

A Swift-version solution with analysis and LeetCode test results.

/**
 Calculate the area of intersection of two given rectilinear rectangles.

 - Author:
 Cong Liu <congliu0704 at gmail dot com>

 - Returns:
 The area of intersection of two given rectilinear rectangles.

 - Parameters:
 - K: The x coordinate of the lower left point of rectangle A
 - L: The y coordinate of the lower left point of rectangle A
 - M: The x coordinate of the upper right point of rectangle A
 - N: The y coordinate of the upper right point of rectangle A
 - P: The x coordinate of the lower left point of rectangle B
 - Q: The y coordinate of the lower left point of rectangle B
 - R: The x coordinate of the upper right point of rectangle B
 - S: The y coordinate of the upper right point of rectangle B

 - Assumptions:
 All the eight given coordinates (K, L, M, N, P, Q, R and S) are integers
 within the range [-2147483648...2147483647], that is, Int32-compatible.
 K < M, L < N, P < R, Q < S

 - Analysis:
 The area of intersected is dyIntersected * dxIntersected.

 To find out dyIntersected, consider how y coordinates of two rectangles relate
 to each other, by moving rectangle A from above rectangle B down.

 Case 1: when N >  L >= S >  Q, dyIntersected = 0
 Case 2: when N >= S >  L >= Q, dyIntersected = S - L
 Case 3: when S >  N >  L >= Q, dyIntersected = N - L
 Case 4: when S >= N >= Q >  L, dyIntersected = N - Q
 Case 5: when N >  S >  Q >  L, dyIntersected = S - Q
 Cases 2 and 3 can be merged as Case B:
         when           L >= Q, dyIntersected = min(N, S) - L
 Cases 4 and 5 can be merged as Case C:
         when           Q >  L, dyIntersected = min(N, S) - Q
 Cases B and C can be merged as Case D:
         when      S >  L     , dyIntersected = min(N, S) - max(L, Q)

 Likewise, x coordinates of two rectangles relate similarly to each other:
 Case 1: when R >  P >= M >  K, dxIntersected = 0
 Case 2: when      M >  P     , dxIntersected = min(R, M) - max(P, K)

 - Submission Date:
 Sat 20 Jan 2018 CST at 23:28 pm

 - Performance:
 https://leetcode.com/problems/rectangle-area/description/
 Status: Accepted
 3081 / 3081 test cases passed.
 Runtime: 78 ms
 */
class Solution {
  public static func computeArea(_ K: Int, _ L: Int, _ M: Int, _ N: Int, _ P: Int, _ Q: Int, _ R: Int, _ S: Int) -> Int {
    let areaA : Int = Int((M - K) * (N - L))
    let areaB : Int = Int((R - P) * (S - Q))
    var xIntersection : Int = 0
    var yIntersection : Int = 0
    var areaIntersection : Int = 0

    if ((min(M, R) - max(K, P)) > 0) {
      xIntersection = Int(min(M, R) - max(K, P))
    }

    if ((min(N, S) - max(L, Q)) > 0) {
      yIntersection = Int(min(N, S) - max(L, Q))
    }

    if ((xIntersection == 0) || (yIntersection == 0)) {
      areaIntersection = 0
    } else {
      areaIntersection = Int(xIntersection * yIntersection)
    }

    return (areaA + areaB - areaIntersection)
  }
}

// A simple test
Solution.computeArea(-4, 1, 2, 6, 0, -1, 4, 3) // returns 42