¿Qué es un algoritmo eficiente para encontrar el área de rectangularjs superpuestos?

Mi situación

  • Entrada: un conjunto de rectangularjs
  • cada rect se compone de 4 dobles como esta: (x0, y0, x1, y1)
  • no están “girados” en ningún ángulo, todos son rectangularjs “normales” que van “arriba / abajo” e “izquierda / derecha” con respecto a la pantalla
  • se colocan al azar: pueden tocarse en los bordes, superponerse o no tener contacto
  • Tendré varios cientos de rectangularjs
  • esto se implementa en C #

necesito encontrar

  • El área que se forma por su superposición: toda el área del canvas que cubre más de un rectángulo (por ejemplo, con dos rectangularjs, sería la intersección)
  • No necesito la geometría de la superposición, solo el área (ejemplo: 4 pulgadas cuadradas)
  • Las superposiciones no se deben contar varias veces, por lo que, por ejemplo, imagine 3 rectas que tengan el mismo tamaño y posición, que estén una encima de la otra, esta área se contará una vez (no tres veces)

Ejemplo

  • La imagen a continuación contiene tres rectangularjs: A, B, C
  • Superposición A y B (como lo indican los guiones)
  • Superposición B y C (como lo indican los guiones)
  • Lo que estoy buscando es el área donde se muestran los guiones

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 

Una forma eficiente de calcular esta área es usar un algoritmo de barrido. Supongamos que barremos una línea vertical L (x) a través de la unión de rectangularjs U:

  • en primer lugar, debe construir una cola de eventos Q, que es, en este caso, la lista ordenada de todas las coordenadas x (izquierda y derecha) de los rectangularjs.
  • durante el barrido, debe mantener una estructura de datos 1D, que debe darle la longitud total de la intersección de L (x) y U. Lo importante es que esta longitud es constante entre dos eventos q consecutivos y q ‘de Q. Entonces , si l (q) denota la longitud total de L (q +) (es decir, L justo en el lado derecho de q) intersecado con U, el área barrida por L entre los eventos q y q ‘es exactamente l (q) * (q’ – q).
  • solo tiene que resumir todas estas áreas barridas para obtener el total.

Todavía tenemos que resolver el problema 1D. Desea una estructura 1D, que compute dinámicamente una unión de segmentos (verticales). Dinámicamente, quiero decir que a veces se agrega un nuevo segmento y, a veces, se elimina uno.

Ya detallé en mi respuesta a este colapso la pregunta de cómo hacerlo de una manera estática (que de hecho es un barrido 1D). Entonces, si quiere algo simple, puede aplicarlo directamente (volviendo a calcular la unión para cada evento). Si quieres algo más eficiente, solo necesitas adaptarlo un poco:

  • suponiendo que usted conoce la unión de los segmentos S 1 … S n consta de segmentos de desuniones D 1 … D k . Agregar S n + 1 es muy fácil, solo tiene que ubicar ambos extremos de S n + 1 entre los extremos de D 1 … D k .
  • suponiendo que usted sabe que la unión de los segmentos S 1 … S n consta de segmentos de desuniones D 1 … D k , eliminando el segmento S i (suponiendo que S i se incluyó en D j ) significa recalcular la unión de segmentos que D j consistió en, excepto S i (usando el algoritmo estático).

Este es tu algoritmo dynamic. Suponiendo que utilizará conjuntos ordenados con consultas de ubicación de tiempo de registro para representar D 1 … D k , este es probablemente el método no especializado más eficiente que puede obtener.

¡Un enfoque de salida es trazarlo a un canvas! Dibuja cada rectángulo usando un color semitransparente. El tiempo de ejecución de .NET hará el dibujo en código nativo optimizado, o incluso utilizando un acelerador de hardware.

Luego, tiene que volver a leer los píxeles. ¿Cada píxel es el color de fondo, el color del rectángulo u otro color? La única forma en que puede ser de otro color es si dos o más rectangularjs se superponen …

Si esto es demasiado trampa, recomendaría el árbol cuádruple como lo hizo otro respondedor, o el árbol-r .

Este es un código rápido y sucio que utilicé en el TopCoder SRM 160 Div 2.

t = arriba
b = botttom
l = izquierda
r = derecha

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

Aquí hay algo que suena como si fuera a funcionar:

  1. Cree un diccionario con una doble clave y una lista de valores rectangulares + booleanos, como este:

    Diccionario >> rectangularjs;

  2. Para cada rectángulo en su conjunto, busque la lista correspondiente para los valores x0 y x1, y agregue el rectángulo a esa lista, con un valor booleano de verdadero para x0 y falso para x1. De esta forma, ahora tiene una lista completa de todas las coordenadas x que cada rectángulo ingresa (verdadero) o deja (falso) la dirección x

  3. Toma todas las claves de ese diccionario (todas las distintas coordenadas x), ordénalas y recorrelas en orden, asegúrate de que puedes obtener tanto el valor x actual como el siguiente (los necesitas a ambos). ) Esto le da tiras individuales de rectangularjs

  4. Mantenga un conjunto de rectangularjs que está mirando actualmente, que comienza vacío. Para cada valor x itera en el punto 3, si el rectángulo está registrado con un valor verdadero, agréguelo al conjunto; de lo contrario, elimínelo.
  5. Para una tira, clasifique los rectangularjs por su coordenada y
  6. Haz un bucle a través de los rectangularjs en la tira, contando las distancias superpuestas (aún no está claro cómo hacerlo de manera eficiente)
  7. Calcule el ancho de la tira multiplicado por la altura de las distancias superpuestas para obtener áreas

Ejemplo, 5 rectangularjs, dibujar uno encima del otro, desde a hasta e:

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

Aquí está la 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 

La lista sería (donde a cada v simplemente se le da una coordenada que comienza en 0 y sube):

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

Cada tira sería así (rectangularjs ordenados de arriba a abajo):

 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 tira, la superposición sería:

 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 

Me imagino que una variación del algoritmo sort + enter / leave para la verificación superior-inferior sería factible también:

  1. ordene los rectangularjs que estamos analizando actualmente en la tira, de arriba a abajo, para rectangularjs con la misma coordenada superior, ordénelos por la coordenada inferior también
  2. iterar a través de las coordenadas y, cuando ingresa un rectángulo, agréguelo al conjunto, cuando sale de un rectángulo, elimínelo del conjunto
  3. siempre que el conjunto tenga más de un rectángulo, tiene solapamiento (y si se asegura de agregar / eliminar todos los rectangularjs que tienen la misma coordenada superior / inferior que está mirando actualmente, los múltiples rectangularjs superpuestos no serían un problema

Para la tira de 1-2 anterior, repetirás de esta manera:

 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 

En realidad, no tendría que mantener un conjunto real aquí, solo el recuento de los rectangularjs en los que se encuentra, siempre que esto vaya de 1 a 2, almacene y, y cada vez que vaya de 2 a 1, calcule la y – actual almacenado y, y sum esta diferencia.

Espero que esto sea comprensible, y como dije, esto está fuera de mi cabeza, no probado de ninguna manera.

La solución más simple

 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) 

En este ejemplo, creamos dos matrices cero que son del tamaño del canvas. Para cada rectángulo, complete una de estas matrices con aquellas donde el rectángulo ocupa espacio. Luego sum las matrices. Ahora sum(A+B > 0) es el área de la unión, y sum(A+B > 1) es el área de la superposición. Este ejemplo puede generalizarse fácilmente a múltiples rectangularjs.

Usando el ejemplo:

  1 2 3 4 5 6

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

1) recopile todas las coordenadas x (izquierda y derecha) en una lista, luego ordénelas y elimine duplicados

  1 3 4 5 6 

2) recoger todas las coordenadas y (arriba y abajo) en una lista, luego ordenarlas y eliminar duplicados

  1 2 3 4 6 

3) crear una matriz 2D por el número de espacios entre las coordenadas x únicas * el número de espacios entre las coordenadas y únicas.

  4 * 4 

4) pintar todos los rectangularjs en esta cuadrícula, incrementando el conteo de cada celda sobre la que ocurre:

    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) la sum total de las áreas de las celdas en la cuadrícula que tienen un recuento mayor que uno es el área de superposición. Para una mejor eficiencia en casos de uso dispersos, puede mantener un total acumulado del área a medida que pinta los rectangularjs, cada vez que mueve una celda de 1 a 2.


En la pregunta, los rectangularjs se describen como cuatro dobles. Los dobles suelen contener errores de redondeo, y el error puede aparecer en su área de superposición calculada. Si las coordenadas legales están en puntos finitos, considere usar una representación entera.


PD usar el acelerador de hardware como en mi otra respuesta no es una idea tan desagradable, si la resolución es aceptable. También es fácil de implementar con mucho menos código que el enfoque que describo arriba. Caballos de carreras.

Aquí está el código que escribí para el algoritmo de barrido 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) < 

Puede simplificar este problema bastante si divide cada rectángulo en rectangularjs más pequeños. Recoge todas las coordenadas X e Y de todos los rectangularjs, y estos se convierten en tus puntos de división: si un rectángulo cruza la línea, divídelo en dos. Cuando hayas terminado, tienes una lista de rectangularjs que se superponen ya sea al 0% o al 100%, si los clasificas, será fácil encontrar los rectangularjs idénticos.

Hay una solución en el enlace http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html para encontrar el área total de múltiples rectangularjs de manera que el área superpuesta se cuente solo una vez .

La solución anterior se puede extender para calcular solo el área superpuesta (y también solo una vez, incluso si el área superpuesta está cubierta por múltiples rectangularjs) con líneas de barrido horizontales para cada par de líneas de barrido verticales consecutivas.

Si el objective es solo descubrir el área total cubierta por todos los rectangularjs, entonces las líneas de barrido horizontales no son necesarias y solo una fusión de todos los rectangularjs entre dos líneas de barrido vertical daría el área.

Por otro lado, si desea calcular solo el área superpuesta, las líneas de barrido horizontal son necesarias para averiguar cuántos rectangularjs se superponen entre las líneas de barrido vertical (y1, y2).

Aquí está el código de trabajo para la solución que implementé en 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 

Si sus rectangularjs van a ser escasos (la mayoría no se intersectan), entonces puede valer la pena examinar los clústeres dimensionales recursivos. De lo contrario, un quad-tree parece ser el camino a seguir (como ha sido mencionado por otros carteles).

Este es un problema común en la detección de colisiones en juegos de computadora, por lo que no hay escasez de recursos que sugieran formas de resolverlo.

Aquí hay una buena publicación de blog que resume el RCD.

Aquí hay un artículo de Dr.Dobbs que resume varios algoritmos de detección de colisión, que serían adecuados.

Este tipo de detección de colisión a menudo se denomina AABB (Cajas de Límite Alineadas del Eje), ese es un buen punto de partida para una búsqueda en Google .

Puedes encontrar la superposición en la x y en el eje y y multiplicarlas.

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

Encontré una solución diferente que el algoritmo de barrido.

Como sus rectangularjs son todos rectangulares, las líneas horizontales y verticales de los rectangularjs formarán una cuadrícula rectangular irregular. Puedes “pintar” los rectangularjs en esta cuadrícula; lo que significa que puede determinar qué campos de la grilla se completarán. Dado que las líneas de la cuadrícula se forman a partir de los límites de los rectangularjs dados, un campo en esta cuadrícula siempre estará completamente vacío o completamente lleno por un rectángulo.

Tuve que resolver el problema en Java, así que aquí está mi solución: http://pastebin.com/03mss8yf

Esta función calcula el área completa ocupada por los rectangularjs. Si solo está interesado en la parte ‘superpuesta’, debe extender el bloque de código entre las líneas 70 y 72. Tal vez pueda usar un segundo conjunto para almacenar qué campos de cuadrícula se usan más de una vez. Su código entre la línea 70 y 72 debe reemplazarse por un bloque como:

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

La variable utilizadaLocations2 aquí es del mismo tipo que usedLocations; se construirá en el mismo punto.

No estoy muy familiarizado con los cálculos de complejidad; así que no sé cuál de las dos soluciones (barrido o mi solución de cuadrícula) funcionará / escalará mejor.

Teniendo en cuenta que tenemos dos rectangularjs (A y B) y tenemos su coordinación inferior izquierda (x1, y1) y superior derecha (x2, y2). El uso de la siguiente pieza de código puede calcular el área superpuesta en 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; } 

La siguiente respuesta debería dar el área total solo una vez. viene respuestas anteriores, pero ahora se implementa en C #. Funciona también con flotadores (o doble, si necesita [no itera sobre los VALORES)].

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

EDITAR: El OP solicitó el área de superposición, obviamente muy simple:

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

y luego la respuesta es:

 var overlappingArea =totArea-GetArea(rects) 

Aquí está el 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