Ответ 1

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

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

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

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

• предполагая, что вы знаете объединение сегментов S ₁... S _n состоит из сегментов непересекающихся D ₁... D < к югу > ксуб > . Добавление S _{n + 1} очень просто, вам просто нужно найти оба конца S _{n + 1} среди концов D ₁...D <югу > ксуб > .
• предполагая, что вы знаете объединение сегментов S ₁... S _n состоит из сегментов непересекающихся D ₁... D _k, удалив сегмент S _i (предполагая, что S _i был включен в D _j) означает перекомпоновку объединения сегментов что D _j состоял из, кроме S _i (используя статический алгоритм).

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

Ответ 2

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

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

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

Ответ 3

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

t = верхняя часть b = Botttom
l = слева
r = right -

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

Ответ 4

Здесь что-то, что от верхней части моей головы звучит так, как будто оно может работать:

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

  Словарь < Double, List < KeyValuePair < Rectangle, Boolean → > rectangles;

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

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

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

Пример: 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

Я бы предположил, что вариант алгоритма sort + enter/leave для проверки верхнего дна также выполним:

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

Для полосы 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 и суммировать эту разницу.

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

Ответ 5

Простейшее решение

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) - область перекрытия. Этот пример может легко обобщить на несколько прямоугольников.

Ответ 6

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

   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 с использованием аппаратного ускорителя, как и в моем другом ответе, не является такой убогой идеей, если разрешение приемлемо. Его также легко реализовать в гораздо меньшем количестве кода, чем описанный выше подход. Лошади для курсов.

Ответ 7

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

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

Ответ 8

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

Ответ 9

Существует решение, перечисленное по ссылке 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();
  }     

Ответ 10

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

Ответ 11

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

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

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

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

Ответ 12

Этот тип обнаружения столкновения часто называется AABB (Axis Aligned Bounding Boxes), что является хорошей отправной точкой для google search.

Ответ 13

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

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

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

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

Ответ 14

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

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

Ответ 15

Следующий ответ должен дать общую область только один раз. это предыдущие ответы, но теперь они реализованы на С#. Он работает также с поплавками (или двойным, если вам нужно [он не повторяет значения VALUES).

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

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

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