Вы можете найти перекрытие по осям x и y и умножить их.

int LineOverlap(int line1a, line1b, line2a, line2b) 
{
  // assume line1a <= line1b and line2a <= line2b
  if (line1a < line2a) 
  {
    if (line1b > line2b)
      return line2b-line2a;
    else if (line1b > line2a)
      return line1b-line2a;
    else 
      return 0;
  }
  else if (line2a < line1b)
    return line2b-line1a;
  else 
    return 0;
}


int RectangleOverlap(Rect rectA, rectB) 
{
  return LineOverlap(rectA.x1, rectA.x2, rectB.x1, rectB.x2) *
    LineOverlap(rectA.y1, rectA.y2, rectB.y1, rectB.y2);
}

Один из выходов - нанести его на холст! Нарисуйте каждый прямоугольник полупрозрачным цветом. Среда выполнения .NET будет рисовать в оптимизированном собственном коде или даже с использованием аппаратного ускорителя.

Затем вы должны считывать пиксели. Является ли каждый пиксель цветом фона, цветом прямоугольника или другим цветом? Единственный способ, которым это может быть другой цвет, - это если два или более прямоугольника перекрываются ...

Если это слишком много читерства, я бы порекомендовал дерево квадратов, как это сделал другой ответчик, или r-дерево.

Это быстрый и грязный код, который я использовал в TopCoder SRM 160 Div 2.

t = top
b = низ
l = левый
r = правый

public class Rect
{
    public int t, b, l, r;

    public Rect(int _l, int _b, int _r, int _t)
    {
        t = _t;
        b = _b;
        l = _l;
        r = _r;
    }   

    public bool Intersects(Rect R)
    {
        return !(l > R.r || R.l > r || R.b > t || b > R.t);
    }

    public Rect Intersection(Rect R)
    {
        if (!this.Intersects(R))
            return new Rect(0,0,0,0);
        int [] horiz = {l, r, R.l, R.r};
        Array.Sort(horiz);
        int [] vert = {b, t, R.b, R.t};
        Array.Sort(vert);

        return new Rect(horiz[1], vert[1], horiz[2], vert[2]);
    } 

    public int Area()
    {
        return (t - b)*(r-l);
    }

    public override string ToString()
    {
        return l + " " + b + " " + r + " " + t;
    }
}

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

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

Здесь - хороший пост в блоге, в котором резюмируется RCD.

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

Этот тип обнаружения столкновений часто называется AABB (ограничивающие рамки с выравниванием по оси), это хорошая отправная точка для поиск Гугл.

Вот что-то, что у меня в голове звучит так, будто это может сработать:

1. Создайте словарь с двойным ключом и списком прямоугольных + логических значений, например:

   Dictionary <Double, List <KeyValuePair <Rectangle, Boolean >>> прямоугольники;

2. Для каждого прямоугольника в вашем наборе найдите соответствующий список для значений x0 и x1 и добавьте прямоугольник в этот список с логическим значением true для x0 и false для x1. Таким образом, теперь у вас есть полный список всех x-координат, которые каждый прямоугольник либо входит (true), либо оставляет (false) x-направление.

3. Возьмите все ключи из этого словаря (все отдельные координаты x), отсортируйте их и переберите их по порядку, убедитесь, что вы можете получить как текущее значение x, так и следующее (вам нужны оба ). Это дает вам отдельные полосы прямоугольников.

4. Сохраните набор прямоугольников, на которые вы сейчас смотрите, который вначале пуст. Для каждого значения x, которое вы перебираете в пункте 3, если прямоугольник зарегистрирован с истинным значением, добавьте его в набор, в противном случае удалите его.
5. Для полосы отсортируйте прямоугольники по их координате y.
6. Прокрутите прямоугольники на полосе, считая перекрывающиеся расстояния (мне пока неясно, как это сделать эффективно)
7. Вычислите ширину полосы, умноженную на высоту перекрытия, чтобы получить площади

Например, 5 прямоугольников, нарисуйте друг на друге от a до e:

aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
        ddddddddddddddddddddddddddddd
        ddddddddddddddddddddddddddddd
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

Вот список x-координат:

v       v  v   v      v   v         v  v  v   
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

Список будет таким (где каждому v просто дается координата, начинающаяся с 0 и повышающаяся):

0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b

Таким образом, каждая полоса будет (прямоугольники отсортированы сверху вниз):

0-1: a, c
1-2: a, d, c
2-3: a, d
3-4: d
4-5: d, e
5-6: b, d, e
6-7: b, e
7-8: b

для каждой полосы перекрытие будет:

0-1: none
1-2: a/d, d/c
2-3: a/d
3-4: none
4-5: d/e
5-6: b/d, d/e
6-7: none
7-8: none

Я предполагаю, что вариант алгоритма сортировки + входа / выхода для проверки сверху-снизу также будет возможен:

1. отсортируйте прямоугольники, которые мы в настоящее время анализируем в полосе, сверху вниз, для прямоугольников с одинаковой верхней координатой, также отсортируйте их по нижней координате
2. перебирать координаты y, и когда вы вводите прямоугольник, добавляете его в набор, когда вы покидаете прямоугольник, удаляете его из набора
3. всякий раз, когда в наборе более одного прямоугольника, у вас есть перекрытие (и если вы убедитесь, что добавили / удалили все прямоугольники с одинаковой верхней / нижней координатой, на которую вы сейчас смотрите, несколько перекрывающихся прямоугольников не будут проблемой

Для полосы 1-2, приведенной выше, вы должны выполнить итерацию следующим образом:

0. empty set, zero sum
1. enter a, add a to set (1 rectangle in set)
2. enter d, add d to set (>1 rectangles in set = overlap, store this y-coordinate)
3. leave a, remove a from set (now back from >1 rectangles in set, add to sum: y - stored_y
4. enter c, add c to set (>1 rectangles in set = overlap, store this y-coordinate)
5. leave d, remove d from set (now back from >1 rectangles in set, add to sum: y - stored_y)
6. multiply sum with width of strip to get overlapping areas

На самом деле вам также не нужно поддерживать фактический набор здесь, просто количество прямоугольников, которые вы внутри, всякий раз, когда он идет от 1 до 2, сохраняйте y, и всякий раз, когда он идет от 2 до 1, вычисляйте текущий y - сохраненные y, и суммируйте эту разницу.

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

Вы можете немного упростить эту задачу, если разделите каждый прямоугольник на более мелкие. Соберите все координаты X и Y всех прямоугольников, и они станут вашими точками разделения - если прямоугольник пересекает линию, разделите его на две части. Когда вы закончите, у вас будет список прямоугольников, которые перекрываются либо на 0%, либо на 100%. Если вы отсортируете их, будет легко найти идентичные.

Эффективный способ вычисления этой области - использовать алгоритм развертки. Предположим, что мы проводим вертикальную линию L (x) через объединение прямоугольников U:

• Прежде всего, вам нужно построить очередь событий Q, которая в данном случае представляет собой упорядоченный список всех x-координат (левого и правого) прямоугольников.
• во время развертки вы должны поддерживать одномерную структуру данных, которая должна дать вам общую длину пересечения L (x) и U. Важно то, что эта длина постоянна между двумя последовательными событиями q и q 'Q. Итак , если l (q) обозначает общую длину L (q +) (т. е. L только справа от q), пересекающуюся с U, площадь, заметаемая L между событиями q и q ', равна l (q) * (q' - q).
• вам просто нужно просуммировать все эти области, чтобы получить общую.

Нам еще предстоит решить проблему 1D. Вам нужна одномерная структура, которая динамически вычисляет объединение (вертикальных) сегментов. Под динамически я имею в виду, что вы иногда добавляете новый сегмент, а иногда удаляете его.

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

• предполагая, что вы знаете, что объединение сегментов S₁ ... S_n состоит из непересекающихся сегментов D₁ ... D_k. Добавить S_n+1 очень просто, вам просто нужно найти оба конца S_n+1 среди концов D₁ ... D_k.
• предполагая, что вы знаете, что объединение сегментов S₁ ... S_n состоит из непересекающихся сегментов D₁ ... D_k, удаление сегмента S_i (предполагая, что S_i был включен в D_j) означает пересчет объединения сегментов, из которых состоял D_j, за исключением S_i (с использованием статический алгоритм).

Это ваш динамический алгоритм. Предполагая, что вы будете использовать отсортированные наборы с запросами местоположения во время журнала для представления D₁ ... D_k, это, вероятно, наиболее эффективный неспециализированный метод, который вы можете получить.

На примере:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) собрать все координаты x (как слева, так и справа) в список, затем отсортировать его и удалить дубликаты

1 3 4 5 6

2) соберите все координаты y (как верхние, так и нижние) в список, затем отсортируйте его и удалите дубликаты

1 2 3 4 6

3) создать 2D-массив по количеству промежутков между уникальными координатами x * количеству промежутков между уникальными координатами y.

4 * 4

4) закрасьте все прямоугольники в эту сетку, увеличивая счетчик каждой ячейки, в которой он встречается:

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 2 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5) сумма площадей ячеек в сетке, у которых счет больше единицы, является площадью перекрытия. Для большей эффективности в редких случаях использования вы можете фактически вести промежуточный итог по площади при рисовании прямоугольников каждый раз, когда вы перемещаете ячейку с 1 на 2.

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

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

Вот код, который я написал для алгоритма развертки области:

#include <iostream>
#include <vector>

using namespace std;


class Rectangle {
public:
    int x[2], y[2];

    Rectangle(int x1, int y1, int x2, int y2) {
        x[0] = x1;
        y[0] = y1;
        x[1] = x2;
        y[1] = y2; 
    };
    void print(void) {
        cout << "Rect: " << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << " " <<endl;
    };
};

// return the iterator of rec in list
vector<Rectangle *>::iterator bin_search(vector<Rectangle *> &list, int begin, int end, Rectangle *rec) {
    cout << begin << " " <<end <<endl;
    int mid = (begin+end)/2;
    if (list[mid]->y[0] == rec->y[0]) {
        if (list[mid]->y[1] == rec->y[1])
            return list.begin() + mid;
        else if (list[mid]->y[1] < rec->y[1]) {
            if (mid == end)
                return list.begin() + mid+1;
            return bin_search(list,mid+1,mid,rec);
        }
        else {
            if (mid == begin)
                return list.begin()+mid;
            return bin_search(list,begin,mid-1,rec);
        }
    }
    else if (list[mid]->y[0] < rec->y[0]) {
        if (mid == end) {
            return list.begin() + mid+1;
        }
        return bin_search(list, mid+1, end, rec);
    }
    else {
        if (mid == begin) {
            return list.begin() + mid;
        }
        return bin_search(list, begin, mid-1, rec);
    }
}

// add rect to rects
void add_rec(Rectangle *rect, vector<Rectangle *> &rects) {
    if (rects.size() == 0) {
        rects.push_back(rect);
    }
    else {
        vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect);
        rects.insert(it, rect);
    }
}

// remove rec from rets
void remove_rec(Rectangle *rect, vector<Rectangle *> &rects) {
    vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect);
    rects.erase(it);
}

// calculate the total vertical length covered by rectangles in the active set
int vert_dist(vector<Rectangle *> as) {
    int n = as.size();

    int totallength = 0;
    int start, end;

    int i = 0;
    while (i < n) {
        start = as[i]->y[0];
        end = as[i]->y[1];
        while (i < n && as[i]->y[0] <= end) {
            if (as[i]->y[1] > end) {
                end = as[i]->y[1];
            }
            i++;
        }
        totallength += end-start;
    }
    return totallength;
}

bool mycomp1(Rectangle* a, Rectangle* b) {
    return (a->x[0] < b->x[0]);
}

bool mycomp2(Rectangle* a, Rectangle* b) {
    return (a->x[1] < b->x[1]);
}

int findarea(vector<Rectangle *> rects) {
    vector<Rectangle *> start = rects;
    vector<Rectangle *> end = rects;
    sort(start.begin(), start.end(), mycomp1);
    sort(end.begin(), end.end(), mycomp2);

    // active set
    vector<Rectangle *> as;

    int n = rects.size();

    int totalarea = 0;
    int current = start[0]->x[0];
    int next;
    int i = 0, j = 0;
    // big loop
    while (j < n) {
        cout << "loop---------------"<<endl;
        // add all recs that start at current
        while (i < n && start[i]->x[0] == current) {
            cout << "add" <<endl;
            // add start[i] to AS
            add_rec(start[i], as);
            cout << "after" <<endl;
            i++;
        }
        // remove all recs that end at current
        while (j < n && end[j]->x[1] == current) {
            cout << "remove" <<endl;
            // remove end[j] from AS
            remove_rec(end[j], as);
            cout << "after" <<endl;
            j++;
        }

        // find next event x
        if (i < n && j < n) {
            if (start[i]->x[0] <= end[j]->x[1]) {
                next = start[i]->x[0];
            }
            else {
                next = end[j]->x[1];
            }
        }
        else if (j < n) {
            next = end[j]->x[1];
        }

        // distance to next event
        int horiz = next - current;
        cout << "horiz: " << horiz <<endl;

        // figure out vertical dist
        int vert = vert_dist(as);
        cout << "vert: " << vert <<endl;

        totalarea += vert * horiz;

        current = next;
    }
    return totalarea;
}

int main() {
    vector<Rectangle *> rects;
    rects.push_back(new Rectangle(0,0,1,1));

    rects.push_back(new Rectangle(1,0,2,3));

    rects.push_back(new Rectangle(0,0,3,3));

    rects.push_back(new Rectangle(1,0,5,1));

    cout << findarea(rects) <<endl;
}

Я нашел другое решение, чем алгоритм развертки.

Поскольку все ваши прямоугольники прямоугольные, горизонтальные и вертикальные линии прямоугольников образуют прямоугольную неправильную сетку. Вы можете «раскрасить» прямоугольники на этой сетке; это означает, что вы можете определить, какие поля сетки будут заполнены. Поскольку линии сетки формируются из границ данных прямоугольников, поле в этой сетке всегда будет либо полностью пустым, либо полностью заполнено прямоугольником.

Мне пришлось решать проблему на Java, поэтому вот мое решение: http://pastebin.com/03mss8yf

Эта функция вычисляет всю площадь, занимаемую прямоугольниками. Если вас интересует только «перекрывающаяся» часть, вы должны расширить блок кода между строками 70 и 72. Возможно, вы можете использовать второй набор для хранения того, какие поля сетки используются более одного раза. Ваш код между строками 70 и 72 следует заменить блоком вроде:

GridLocation gl = new GridLocation(curX, curY);
if (usedLocations.contains(gl) && usedLocations2.add(gl)) {
  ret += width*height;
} else {
  usedLocations.add(gl);
}

Переменная usedLocations2 здесь того же типа, что и usedLocations; он будет построен в той же точке.

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

Самое простое решение

import numpy as np

A = np.zeros((100, 100))
B = np.zeros((100, 100))

A[rect1.top : rect1.bottom,  rect1.left : rect1.right] = 1
B[rect2.top : rect2.bottom,  rect2.left : rect2.right] = 1

area_of_union     = np.sum((A + B) > 0)
area_of_intersect = np.sum((A + B) > 1)

В этом примере мы создаем две нулевые матрицы размером с холст. Для каждого прямоугольника заполните одну из этих матриц матрицами, в которых прямоугольник занимает место. Затем просуммируйте матрицы. Теперь sum(A+B > 0) - это область объединения, а sum(A+B > 1) - область перекрытия. Этот пример можно легко обобщить на несколько прямоугольников.

По ссылке http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html можно найти решение для определения общей площади нескольких прямоугольников, при котором перекрывающаяся площадь учитывается только один раз.

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

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

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

Вот рабочий код решения, которое я реализовал на Java.

import java.io.*;
import java.util.*;

class Solution {

static class Rectangle{
         int x;
         int y;
         int dx;
         int dy;

         Rectangle(int x, int y, int dx, int dy){
           this.x = x;
           this.y = y;
           this.dx = dx;
           this.dy = dy;
         }

         Range getBottomLeft(){
            return new Range(x, y);
         }

         Range getTopRight(){
            return new Range(x + dx, y + dy);
         }

         @Override
         public int hashCode(){
            return (x+y+dx+dy)/4;
         }

         @Override
         public boolean equals(Object other){
            Rectangle o = (Rectangle) other;
            return o.x == this.x && o.y == this.y && o.dx == this.dx && o.dy == this.dy;
         }

        @Override
        public String toString(){
            return String.format("X = %d, Y = %d, dx : %d, dy : %d", x, y, dx, dy);
        }
     }     

     static class RW{
         Rectangle r;
         boolean start;

         RW (Rectangle r, boolean start){
           this.r = r;
           this.start = start;
         }

         @Override
         public int hashCode(){
             return r.hashCode() + (start ? 1 : 0);
         }

         @Override
         public boolean equals(Object other){
              RW o = (RW)other;
             return o.start == this.start && o.r.equals(this.r);
         }

        @Override
        public String toString(){
            return "Rectangle : " + r.toString() + ", start = " + this.start;
        }
     }

     static class Range{
         int l;
         int u;   

       public Range(int l, int u){
         this.l = l;
         this.u = u;
       }

         @Override
         public int hashCode(){
            return (l+u)/2;
         }

         @Override
         public boolean equals(Object other){
            Range o = (Range) other;
            return o.l == this.l && o.u == this.u;
         }

        @Override
        public String toString(){
            return String.format("L = %d, U = %d", l, u);
        }
     }

     static class XComp implements Comparator<RW>{
             @Override
             public int compare(RW rw1, RW rw2){
                 //TODO : revisit these values.
                 Integer x1 = -1;
                 Integer x2 = -1;

                 if (rw1.start){
                     x1 = rw1.r.x;
                 }else{
                     x1 = rw1.r.x + rw1.r.dx;
                 }   

                 if (rw2.start){
                     x2 = rw2.r.x;
                 }else{
                     x2 = rw2.r.x + rw2.r.dx;
                 }

                 return x1.compareTo(x2);
             }
     }

     static class YComp implements Comparator<RW>{
             @Override
             public int compare(RW rw1, RW rw2){
                 //TODO : revisit these values.
                 Integer y1 = -1;
                 Integer y2 = -1;

                 if (rw1.start){
                     y1 = rw1.r.y;
                 }else{
                     y1 = rw1.r.y + rw1.r.dy;
                 }   

                 if (rw2.start){
                     y2 = rw2.r.y;
                 }else{
                     y2 = rw2.r.y + rw2.r.dy;
                 }

                 return y1.compareTo(y2);
             }
     }

     public static void main(String []args){
         Rectangle [] rects = new Rectangle[4];

         rects[0] = new Rectangle(10, 10, 10, 10);
         rects[1] = new Rectangle(15, 10, 10, 10);
         rects[2] = new Rectangle(20, 10, 10, 10);
         rects[3] = new Rectangle(25, 10, 10, 10);

         int totalArea = getArea(rects, false);
         System.out.println("Total Area : " + totalArea);

         int overlapArea = getArea(rects, true);              
         System.out.println("Overlap Area : " + overlapArea);
     }


     static int getArea(Rectangle []rects, boolean overlapOrTotal){
         printArr(rects);

         // step 1: create two wrappers for every rectangle
         RW []rws = getWrappers(rects);       

         printArr(rws);        

         // steps 2 : sort rectangles by their x-coordinates
         Arrays.sort(rws, new XComp());   

         printArr(rws);        

         // step 3 : group the rectangles in every range.
         Map<Range, List<Rectangle>> rangeGroups = groupRects(rws, true);

         for(Range xrange : rangeGroups.keySet()){
             List<Rectangle> xRangeRects = rangeGroups.get(xrange);
             System.out.println("Range : " + xrange);
             System.out.println("Rectangles : ");
             for(Rectangle rectx : xRangeRects){
                System.out.println("\t" + rectx);               
             }
         }   

         // step 4 : iterate through each of the pairs and their rectangles

         int sum = 0;
         for(Range range : rangeGroups.keySet()){
             List<Rectangle> rangeRects = rangeGroups.get(range);
             sum += getOverlapOrTotalArea(rangeRects, range, overlapOrTotal);
         }
         return sum;         
     }    

     static Map<Range, List<Rectangle>> groupRects(RW []rws, boolean isX){
         //group the rws with either x or y coordinates.

         Map<Range, List<Rectangle>> rangeGroups = new HashMap<Range, List<Rectangle>>();

         List<Rectangle> rangeRects = new ArrayList<Rectangle>();            

         int i=0;
         int prev = Integer.MAX_VALUE;

         while(i < rws.length){
             int curr = isX ? (rws[i].start ? rws[i].r.x : rws[i].r.x + rws[i].r.dx): (rws[i].start ? rws[i].r.y : rws[i].r.y + rws[i].r.dy);

             if (prev < curr){
                Range nRange = new Range(prev, curr);
                rangeGroups.put(nRange, rangeRects);
                rangeRects = new ArrayList<Rectangle>(rangeRects);
             }
             prev = curr;

             if (rws[i].start){
               rangeRects.add(rws[i].r);
             }else{
               rangeRects.remove(rws[i].r);
             }

           i++;
         }
       return rangeGroups;
     }

     static int getOverlapOrTotalArea(List<Rectangle> rangeRects, Range range, boolean isOverlap){
         //create horizontal sweep lines similar to vertical ones created above

         // Step 1 : create wrappers again
         RW []rws = getWrappers(rangeRects);

         // steps 2 : sort rectangles by their y-coordinates
         Arrays.sort(rws, new YComp());

         // step 3 : group the rectangles in every range.
         Map<Range, List<Rectangle>> yRangeGroups = groupRects(rws, false);

         //step 4 : for every range if there are more than one rectangles then computer their area only once.

         int sum = 0;
         for(Range yRange : yRangeGroups.keySet()){
             List<Rectangle> yRangeRects = yRangeGroups.get(yRange);

             if (isOverlap){
                 if (yRangeRects.size() > 1){
                     sum += getArea(range, yRange);
                 }
             }else{
                 if (yRangeRects.size() > 0){
                     sum += getArea(range, yRange);
                 }
             }
         }         
         return sum;
     } 

    static int getArea(Range r1, Range r2){
      return (r2.u-r2.l)*(r1.u-r1.l);      
    }

    static RW[] getWrappers(Rectangle []rects){
         RW[] wrappers = new RW[rects.length * 2];

         for(int i=0,j=0;i<rects.length;i++, j+=2){
             wrappers[j] = new RW(rects[i], true); 
             wrappers[j+1] = new RW(rects[i], false); 
         }
         return wrappers;
     }

    static RW[] getWrappers(List<Rectangle> rects){
         RW[] wrappers = new RW[rects.size() * 2];

         for(int i=0,j=0;i<rects.size();i++, j+=2){
             wrappers[j] = new RW(rects.get(i), true); 
             wrappers[j+1] = new RW(rects.get(i), false); 
         }
         return wrappers;
     }

  static void printArr(Object []a){
    for(int i=0; i < a.length;i++){
      System.out.println(a[i]);
    }
    System.out.println();
  }     

Учитывая, что у нас есть два прямоугольника (A и B), и у нас есть их нижняя левая (x1, y1) и верхняя правая (x2, y2) координация. Используя следующий фрагмент кода, вы можете вычислить перекрывающуюся область в C++.

    #include <iostream>
using namespace std;

int rectoverlap (int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    int width, heigh, area;

    if (ax2<bx1 || ay2<by1 || ax1>bx2 || ay1>by2) {
        cout << "Rectangles are not overlapped" << endl;
        return 0;
    }
    if (ax2>=bx2 && bx1>=ax1){
        width=bx2-bx1;
        heigh=by2-by1;
    } else if (bx2>=ax2 && ax1>=bx1) {
        width=ax2-ax1;
        heigh=ay2-ay1;
    } else {
        if (ax2>bx2){
            width=bx2-ax1;
        } else {
            width=ax2-bx1;
        }
        if (ay2>by2){
            heigh=by2-ay1;
        } else {
            heigh=ay2-by1;
        }
    }
    area= heigh*width;
    return (area);
}

int main()
{
    int ax1,ay1,ax2,ay2,bx1,by1,bx2,by2;
    cout << "Inter the x value for bottom left for rectangle A" << endl;
    cin >> ax1;
    cout << "Inter the y value for bottom left for rectangle A" << endl;
    cin >> ay1;
    cout << "Inter the x value for top right for rectangle A" << endl;
    cin >> ax2;
    cout << "Inter the y value for top right for rectangle A" << endl;
    cin >> ay2;
    cout << "Inter the x value for bottom left for rectangle B" << endl;
    cin >> bx1;
    cout << "Inter the y value for bottom left for rectangle B" << endl;
    cin >> by1;
    cout << "Inter the x value for top right for rectangle B" << endl;
    cin >> bx2;
    cout << "Inter the y value for top right for rectangle B" << endl;
    cin >> by2;
    cout << "The overlapped area is " <<  rectoverlap (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) << endl;
}

В следующем ответе общая площадь должна быть указана только один раз. он приходит к предыдущим ответам, но реализован теперь на C#. Он также работает с числами с плавающей запятой (или с двойным числом, если вам нужно [он не превышает ЗНАЧЕНИЯ).

Кредиты: http://codercareer.blogspot.co.il/2011/12/no-27-area-of-rectangles.html

Обновлено: OP запросил перекрывающуюся область - это, очевидно, очень просто:

var totArea = rects.Sum(x => x.Width * x.Height);

и тогда ответ:

var overlappingArea =totArea-GetArea(rects)

Вот код:

   #region rectangle overlapping
        /// <summary>
        /// see algorithm for detecting overlapping areas here: https://stackoverflow.com/a/245245/3225391
        /// or easier here:
        /// http://codercareer.blogspot.co.il/2011/12/no-27-area-of-rectangles.html
        /// </summary>
        /// <param name = "dim"></param>
        /// <returns></returns>
        public static float GetArea(RectangleF[] rects)
        {
            List<float> xs = new List<float>();
            foreach (var item in rects)
            {
                xs.Add(item.X);
                xs.Add(item.Right);
            }
            xs = xs.OrderBy(x => x).Cast<float>().ToList();
            rects = rects.OrderBy(rec => rec.X).Cast<RectangleF>().ToArray();
            float area = 0f;
            for (int i = 0; i < xs.Count - 1; i++)
            {
                if (xs[i] == xs[i + 1])//not duplicate
                    continue;
                int j = 0;
                while (rects[j].Right < xs[i])
                    j++;
                List<Range> rangesOfY = new List<Range>();
                var rangeX = new Range(xs[i], xs[i + 1]);
                GetRangesOfY(rects, j, rangeX, out rangesOfY);
                area += GetRectArea(rangeX, rangesOfY);
            }
            return area;
        }

        private static void GetRangesOfY(RectangleF[] rects, int rectIdx, Range rangeX, out List<Range> rangesOfY)
        {
            rangesOfY = new List<Range>();
            for (int j = rectIdx; j < rects.Length; j++)
            {
                if (rangeX.less < rects[j].Right && rangeX.greater > rects[j].Left)
                {
                    rangesOfY = Range.AddRange(rangesOfY, new Range(rects[j].Top, rects[j].Bottom));
#if DEBUG
                    Range rectXRange = new Range(rects[j].Left, rects[j].Right);
#endif
                }
            }
        }

        static float GetRectArea(Range rangeX, List<Range> rangesOfY)
        {
            float width = rangeX.greater - rangeX.less,
                area = 0;

            foreach (var item in rangesOfY)
            {
                float height = item.greater - item.less;
                area += width * height;
            }
            return area;
        }

        internal class Range
        {
            internal static List<Range> AddRange(List<Range> lst, Range rng2add)
            {
                if (lst.isNullOrEmpty())
                {
                    return new List<Range>() { rng2add };
                }

                for (int i = lst.Count - 1; i >= 0; i--)
                {
                    var item = lst[i];
                    if (item.IsOverlapping(rng2add))
                    {
                        rng2add.Merge(item);
                        lst.Remove(item);
                    }
                }
                lst.Add(rng2add);
                return lst;
            }
            internal float greater, less;
            public override string ToString()
            {
                return $"ln{less} gtn{greater}";
            }

            internal Range(float less, float greater)
            {
                this.less = less;
                this.greater = greater;
            }

            private void Merge(Range rng2add)
            {
                this.less = Math.Min(rng2add.less, this.less);
                this.greater = Math.Max(rng2add.greater, this.greater);
            }
            private bool IsOverlapping(Range rng2add)
            {
                return !(less > rng2add.greater || rng2add.less > greater);
                //return
                //    this.greater < rng2add.greater && this.greater > rng2add.less
                //    || this.less > rng2add.less && this.less < rng2add.greater

                //    || rng2add.greater < this.greater && rng2add.greater > this.less
                //    || rng2add.less > this.less && rng2add.less < this.greater;
            }
        }
        #endregion rectangle overlapping

сообщение user3048546 содержит ошибку в логике в строках 12-17. Вот рабочая реализация:

int rectoverlap (int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    int width, height, area;

    if (ax2<bx1 || ay2<by1 || ax1>bx2 || ay1>by2) {
        cout << "Rectangles are not overlapped" << endl;
        return 0;
    }

    if (ax2>=bx2 && bx1>=ax1){
        width=bx2-bx1;
    } else if (bx2>=ax2 && ax1>=bx1) {
        width=ax2-ax1;
    } else if (ax2>bx2) {
        width=bx2-ax1;
    } else {
        width=ax2-bx1;
    }

    if (ay2>=by2 && by1>=ay1){
        height=by2-by1;
    } else if (by2>=ay2 && ay1>=by1) {
        height=ay2-ay1;
    } else if (ay2>by2) {
        height=by2-ay1;
    } else {
        height=ay2-by1;
    }

    area = heigh*width;
    return (area);
}