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

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

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

Здесь хорошее сообщение в блоге, суммирующее RCD.

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

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

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

Используя пример:

   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.

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

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

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

т = вершина
b = нижняя часть
л = уехал
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;
    }
}

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

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

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

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

Вот что-то, что первое, что пришло на ум кажется, что могло бы работать:

1. Создают словарь с двойным ключом и список значений rectangle+boolean, как это:

   Dictionary< Дважды, List< KeyValuePair< Прямоугольник, булевская переменная>>> прямоугольники;

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

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

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

Пример, 5 прямоугольников, тянут друг на друге, от до 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, и суммируйте это различие.

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

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

#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;
}