Что такое эффективный алгоритм для нахождения области перекрывающихся прямоугольников

Question

Моя ситуация

• Ввод: набор прямоугольников
• каждый прямоугольник состоит из 4 двойных чисел, как это: (x0, y0, x1, y1)
• они не "повернуты" ни под каким углом, все они являются "нормальными" прямоугольниками, которые идут "вверх / вниз" и "влево / вправо" относительно экрана
• они расположены случайным образом - они могут касаться краев, перекрываться или не иметь никакого контакта
• У меня будет несколько сотен прямоугольников
• это реализовано в C #

Мне нужно найти

• Область, которая образована их перекрытием - вся область холста, которую "покрывает" более одного прямоугольника (например, двумя прямоугольниками, это будет пересечение)
• Мне не нужна геометрия перекрытия - просто площадь (пример: 4 кв. Дюйма)
• Наложения не должны учитываться несколько раз - например, представьте 3 рита одинакового размера и положения - они расположены прямо друг над другом - эта область должна учитываться один раз (а не три раза)

Пример

• Изображение ниже содержит три прямоугольника: A, B, C
• A и B перекрываются (как показано штрихами)
• B и C перекрываются (как показано штрихами)
• То, что я ищу, - это область, где отображаются штрихи

-

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC

Answer 1

Учитывая, что у нас есть два прямоугольника (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;
}

Answer 2

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

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

Мне пришлось решить проблему в 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; это будет построено в той же точке.

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

Answer 3

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

Answer 4

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

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

Здесь - это хорошее сообщение в блоге, в котором кратко изложено RCD.

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

Answer 5

Вы можете найти перекрытие по осям 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);
}