O que é um algoritmo eficiente para encontrar a área de retângulos sobrepostos

Minha situação

  • Entrada: um conjunto de retângulos
  • cada rect é composto por 4 duplas como esta: (x0, y0, x1, y1)
  • eles não são “girados” em qualquer ângulo, todos eles são retângulos “normais” que vão “para cima / baixo” e “esquerda / direita” em relação à canvas
  • eles são colocados aleatoriamente – eles podem estar tocando nas bordas, sobrepostos, ou não ter qualquer contato
  • Eu terei várias centenas de retângulos
  • isso é implementado em c #

eu preciso encontrar

  • A área que é formada por sua sobreposição – toda a área na canvas que mais de um retângulo “cobre” (por exemplo, com dois retângulos, seria a interseção)
  • Eu não preciso da geometry da sobreposição – apenas a área (exemplo: 4 polegadas quadradas)
  • As sobreposições não devem ser contadas várias vezes – por exemplo, imagine três retalhos que tenham o mesmo tamanho e posição – eles estão um em cima do outro – essa área deve ser contada uma vez (não três vezes)

Exemplo

  • A imagem abaixo contém três retângulos: A, B, C
  • A e B se sobrepõem (como indicado por traços)
  • B e C se sobrepõem (como indicado por traços)
  • O que estou procurando é a área onde os traços são mostrados

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 

Uma maneira eficiente de calcular essa área é usar um algoritmo de varredura. Vamos supor que varremos uma linha vertical L (x) através da união de retângulos U:

  • Primeiro de tudo, você precisa construir uma fila de events Q, que é, neste caso, a lista ordenada de todas as coordenadas x (esquerda e direita) dos retângulos.
  • durante a varredura, você deve manter uma estrutura de dados 1D, que deve lhe dar o comprimento total da interseção de L (x) e U. O importante é que esse comprimento seja constante entre dois events consecutivos q e q ‘de Q. , se l (q) denota o comprimento total de L (q +) (ie L apenas no lado direito de q) cruzado com U, a área varrida por L entre events q e q ‘é exatamente l (q) * (q’ – q).
  • você só precisa resumir todas essas áreas varridas para obter o total.

Ainda temos que resolver o problema 1D. Você quer uma estrutura 1D, que calcula dinamicamente uma união de segmentos (verticais). Por dinamicamente, quero dizer que às vezes você adiciona um novo segmento e às vezes remove um.

Eu já detalhei em minha resposta a este intervalo de colapsos como fazer isso de uma maneira estática (que é na verdade uma varredura 1D). Portanto, se você quiser algo simples, poderá aplicá-lo diretamente (recomputando a união de cada evento). Se você quer algo mais eficiente, você só precisa adaptar um pouco:

  • supondo que você saiba que a união dos segmentos S 1 … S n consiste em segmentos disjuntos D 1 … D k . Adicionando S n + 1 é muito fácil, você só precisa localizar ambas as extremidades de S n + 1 entre as extremidades de D 1 … D k .
  • supondo que você saiba que a união dos segmentos S 1 … S n consiste em segmentos disjuntos D 1 … D k , removendo o segmento S i (assumindo que S i foi incluído em D j ) significa recomputar a união de segmentos que D j consistiu em, exceto S i (usando o algoritmo estático).

Este é o seu algoritmo dynamic. Supondo que você usará conjuntos classificados com consultas de localização de tempo de log para representar D 1 … D k , esse é provavelmente o método não especializado mais eficiente que você pode obter.

Uma abordagem de saída é plotar em uma canvas! Desenhe cada retângulo usando uma cor semitransparente. O tempo de execução do .NET estará fazendo o desenho em código nativo otimizado – ou mesmo usando um acelerador de hardware.

Então, você tem que ler os pixels. Cada pixel é a cor do plano de fundo, a cor do retângulo ou outra cor? A única maneira que pode ser outra cor é se dois ou mais retângulos se sobrepõem …

Se isso for uma grande trapaça, eu recomendaria o quad-tree como outro respondedor, ou o r-tree .

Este é um código rápido e sujo que eu usei no TopCoder SRM 160 Div 2.

t = top
b = botttom
l = esquerda
r = direito

 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 > Rr || Rl > r || Rb > t || b > Rt); } public Rect Intersection(Rect R) { if(!this.Intersects(R)) return new Rect(0,0,0,0); int [] horiz = {l, r, Rl, Rr}; Array.Sort(horiz); int [] vert = {b, t, Rb, Rt}; Array.Sort(vert); return new Rect(horiz[1], vert[1], horiz[2], vert[2]); } public int Area() { return (t - b)*(rl); } public override string ToString() { return l + " " + b + " " + r + " " + t; } } 

Aqui está algo que em cima da minha cabeça parece que poderia funcionar:

  1. Crie um dictionary com uma chave dupla e uma lista de retângulo + valores booleanos, como este:

    Dicionário >> retângulos;

  2. Para cada retângulo em seu conjunto, encontre a lista correspondente para os valores x0 e x1 e adicione o retângulo a essa lista, com um valor booleano de verdadeiro para x0 e falso para x1. Desta forma, você agora tem uma lista completa de todas as coordenadas x que cada retângulo entra (verdadeiro) ou deixa (falso) a direção x

  3. Pegue todas as chaves daquele dictionary (todas as coordenadas x distintas), classifique-as e faça um loop por elas, para ter certeza de que você pode obter tanto o valor x atual quanto o próximo (você precisa dos dois ). Isso lhe dá tiras individuais de retângulos

  4. Mantenha um conjunto de retângulos que você está vendo atualmente, que começa vazio. Para cada valor de x que você iterar no ponto 3, se o retângulo estiver registrado com um valor verdadeiro, adicione-o ao conjunto, caso contrário, remova-o.
  5. Para uma faixa, classifique os retângulos pela coordenada y
  6. Passe pelos retângulos na faixa, contando as distâncias sobrepostas (não está claro para mim como fazer isso de forma eficiente)
  7. Calcular a largura da tira vezes a altura de distâncias sobrepostas para obter áreas

Exemplo, 5 retângulos, desenhados um em cima do outro, de a para e:

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

Aqui está a lista de coordenadas x:

 vvvvvvvvv |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 

A lista seria (onde cada v é simplesmente dado uma coordenada começando em 0 e subindo):

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

Cada faixa seria assim (retângulos ordenados de cima para baixo):

 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 

para cada faixa, a sobreposição seria:

 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 

Eu imagino que uma variação do algoritmo de sorting + input / saída para a verificação de cima para baixo também seria possível:

  1. classifique os retângulos que estamos analisando atualmente na faixa, de cima para baixo, para retângulos com a mesma coordenada superior, classifique-os por coordenadas de fundo também
  2. iterar através das coordenadas y, e quando você inserir um retângulo, adicioná-lo ao conjunto, quando você deixar um retângulo, removê-lo do conjunto
  3. sempre que o conjunto tiver mais de um retângulo, você terá sobreposição (e se você adicionar / remover todos os retângulos que tiverem a mesma coordenada superior / inferior que você está visualizando atualmente, vários retângulos sobrepostos não serão um problema

Para a faixa 1-2 acima, você faria uma iteração assim:

 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 

Você não teria que manter um conjunto real aqui, apenas a contagem dos retângulos em que você está dentro, sempre que isso vai de 1 a 2, armazene y, e sempre que for de 2 para 1, calcule y atual – armazene y e some essa diferença.

Espero que isso seja compreensível, e como eu disse, isso está fora do meu limite, não testado de forma alguma.

A solução mais simples

 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) 

Neste exemplo, criamos duas matrizes zero que são o tamanho da canvas. Para cada retângulo, preencha uma dessas matrizes com aquelas em que o retângulo ocupa espaço. Então some as matrizes. Agora sum(A+B > 0) é a área da união e sum(A+B > 1) é a área da sobreposição. Este exemplo pode generalizar facilmente para vários retângulos.

Usando o exemplo:

  1 2 3 4 5 6

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

1) coletar todas as coordenadas x (esquerda e direita) em uma lista, então classificá-la e remover duplicatas

  1 3 4 5 6 

2) coletar todas as coordenadas y (superior e inferior) em uma lista, depois classificá-la e remover duplicatas

  1 2 3 4 6 

3) crie um array 2D pelo número de intervalos entre as coordenadas x exclusivas * número de intervalos entre as coordenadas y exclusivas.

  4 * 4 

4) pinte todos os retângulos nessa grade, incrementando a contagem de cada célula em que ocorre:

    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) a sum total das áreas das células na grade que têm uma contagem maior do que uma é a área de sobreposição. Para uma melhor eficiência em casos de uso esparsos, você pode manter um total da área em execução enquanto pinta os retângulos, cada vez que você move uma célula de 1 para 2.


Na questão, os retângulos são descritos como sendo quatro duplos. Geralmente, os duplos contêm erros de arredondamento, e o erro pode se infiltrar em sua área computada de sobreposição. Se as coordenadas legais estiverem em pontos finitos, considere o uso de uma representação inteira.


PS usando o acelerador de hardware como na minha outra resposta não é uma idéia tão pobre, se a resolução for aceitável. É também fácil de implementar em muito menos código do que a abordagem que descrevi acima. Cavalos para cursos.

Aqui está o código que escrevi para o algoritmo de varredura de área:

 #include  #include  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] << " " <::iterator bin_search(vector &list, int begin, int end, Rectangle *rec) { cout < < begin << " " <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 &rects) { if (rects.size() == 0) { rects.push_back(rect); } else { vector::iterator it = bin_search(rects, 0, rects.size()-1, rect); rects.insert(it, rect); } } // remove rec from rets void remove_rec(Rectangle *rect, vector &rects) { vector::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 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 rects) { vector start = rects; vector end = rects; sort(start.begin(), start.end(), mycomp1); sort(end.begin(), end.end(), mycomp2); // active set vector 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---------------"<x[0] == current) { cout < < "add" <x[1] == current) { cout < < "remove" <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 < 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) < 

Você pode simplificar bastante este problema se dividir cada retângulo em retângulos menores. Colete todas as coordenadas X e Y de todos os retângulos, e estes se tornam seus pontos de divisão – se um retângulo cruzar a linha, divida-o em dois. Quando terminar, você terá uma lista de retângulos que se sobrepõem a 0% ou 100%. Se você os classificar, será fácil encontrar os mesmos.

Há uma solução listada no link http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html para encontrar a área total de vários retângulos, de forma que a área sobreposta seja contada apenas uma vez .

A solução acima pode ser estendida para computar apenas a área sobreposta (e isso também apenas uma vez, mesmo que a área sobreposta seja coberta por vários retângulos) com linhas de varredura horizontal para cada par de linhas de varredura verticais consecutivas.

Se o objective é apenas descobrir a área total coberta por todos os retângulos, então linhas horizontais de varredura não são necessárias e apenas uma junit de todos os retângulos entre duas linhas verticais de varredura daria a área.

Por outro lado, se você quiser computar apenas a área sobreposta, as linhas de varredura horizontal são necessárias para descobrir quantos retângulos estão sobrepostos entre as linhas de varredura vertical (y1, y2).

Aqui está o código de trabalho para a solução que implementei em 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 ox == this.x && oy == 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 && orequals(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 ol == this.l && ou == this.u; } @Override public String toString(){ return String.format("L = %d, U = %d", l, u); } } static class XComp implements Comparator{ @Override public int compare(RW rw1, RW rw2){ //TODO : revisit these values. Integer x1 = -1; Integer x2 = -1; if(rw1.start){ x1 = rw1.rx; }else{ x1 = rw1.rx + rw1.r.dx; } if(rw2.start){ x2 = rw2.rx; }else{ x2 = rw2.rx + rw2.r.dx; } return x1.compareTo(x2); } } static class YComp implements Comparator{ @Override public int compare(RW rw1, RW rw2){ //TODO : revisit these values. Integer y1 = -1; Integer y2 = -1; if(rw1.start){ y1 = rw1.ry; }else{ y1 = rw1.ry + rw1.r.dy; } if(rw2.start){ y2 = rw2.ry; }else{ y2 = rw2.ry + 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> rangeGroups = groupRects(rws, true); for(Range xrange : rangeGroups.keySet()){ List 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 rangeRects = rangeGroups.get(range); sum += getOverlapOrTotalArea(rangeRects, range, overlapOrTotal); } return sum; } static Map> groupRects(RW []rws, boolean isX){ //group the rws with either x or y coordinates. Map> rangeGroups = new HashMap>(); List rangeRects = new ArrayList(); int i=0; int prev = Integer.MAX_VALUE; while(i < rws.length){ int curr = isX ? (rws[i].start ? rws[i].rx : rws[i].rx + rws[i].r.dx): (rws[i].start ? rws[i].ry : rws[i].ry + rws[i].r.dy); if(prev < curr){ Range nRange = new Range(prev, curr); rangeGroups.put(nRange, rangeRects); rangeRects = new ArrayList(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 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> 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 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){ RW[] wrappers = new RW[rects.size() * 2]; for(int i=0,j=0;i 

Se os seus retângulos forem esparsos (a maioria não se cruzará), talvez valha a pena dar uma olhada no agrupamento dimensional recursivo. Caso contrário, um quad-tree parece ser o caminho a percorrer (como foi mencionado por outros cartazes.

Este é um problema comum na detecção de colisões em jogos de computador, portanto, não há escassez de resources sugerindo maneiras de resolvê-lo.

Aqui está uma boa postagem no blog resumindo o RCD.

Aqui está um artigo Dr.Dobbs resumindo vários algoritmos de detecção de colisão, o que seria adequado.

Esse tipo de detecção de colisão é geralmente chamado de AABB (Axis Aligned Bounding Boxes), que é um bom ponto de partida para uma pesquisa no google .

Você pode encontrar a sobreposição no eixo xe no eixo y e multiplicá-los.

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

Eu encontrei uma solução diferente do que o algoritmo de varredura.

Como seus retângulos são todos retangulares, as linhas horizontais e verticais dos retângulos formarão uma grade irregular retangular. Você pode “pintar” os retângulos nessa grade; o que significa que você pode determinar quais campos da grade serão preenchidos. Como as linhas de grade são formadas a partir dos limites dos retângulos dados, um campo nessa grade sempre estará completamente vazio ou completamente preenchido por um retângulo.

Eu tive que resolver o problema em Java, então aqui está a minha solução: http://pastebin.com/03mss8yf

Esta function calcula a área completa ocupada pelos retângulos. Se você estiver interessado apenas na parte ‘sobreposta’, você deve estender o bloco de código entre as linhas 70 e 72. Talvez você possa usar um segundo conjunto para armazenar quais campos de grade são usados ​​mais de uma vez. Seu código entre as linhas 70 e 72 deve ser substituído por um bloco como:

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

A variável usedLocations2 aqui é do mesmo tipo que usedLocations; será construído no mesmo ponto.

Eu não estou realmente familiarizado com cálculos de complexidade; então eu não sei qual das duas soluções (sweep ou my grid solution) irá executar / escalar melhor.

Considerando que temos dois retângulos (A e B) e temos a coordenação inferior esquerda (x1, y1) e superior direita (x2, y2). Usando a seguinte parte do código, você pode calcular a área sobreposta em C ++.

  #include  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 (ax2bx2 || 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; } 

A resposta a seguir deve fornecer a área total apenas uma vez. vem respostas anteriores, mas implementadas agora em C #. Ele também funciona com floats (ou double, se você precisar [itterar sobre os VALUES).

Créditos: http://codercareer.blogspot.co.il/2011/12/no-27-area-of-rectangles.html

EDIT: O OP pediu para a área de sobreposição – isso é obviamente muito simples:

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

e então a resposta é:

 var overlappingArea =totArea-GetArea(rects) 

Aqui está o código:

  #region rectangle overlapping ///  /// 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 ///  ///  ///  public static float GetArea(RectangleF[] rects) { List xs = new List(); foreach (var item in rects) { xs.Add(item.X); xs.Add(item.Right); } xs = xs.OrderBy(x => x).Cast().ToList(); rects = rects.OrderBy(rec => rec.X).Cast().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 rangesOfY = new List(); 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 rangesOfY) { rangesOfY = new List(); 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 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 AddRange(List lst, Range rng2add) { if (lst.isNullOrEmpty()) { return new List() { 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