semi plugin español correccion complemento automatic atmosferica algorithm optimization geometry performance

algorithm - plugin - roi qgis



¿Qué es un algoritmo eficiente para encontrar el área de rectángulos superpuestos? (15)

Mi situación

  • Entrada: un conjunto de rectángulos
  • cada rect se compone de 4 dobles como esta: (x0, y0, x1, y1)
  • no están "girados" en ningún ángulo, todos son rectángulos "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 rectángulos
  • esto se implementa en C #

necesito encontrar

  • El área que se forma por su superposición: toda el área del lienzo que cubre más de un rectángulo (por ejemplo, con dos rectángulos, 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 rectángulos: 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

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 lienzo. Para cada rectángulo, complete una de estas matrices con aquellas donde el rectángulo ocupa espacio. Luego suma 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 rectángulos.

¡Un enfoque de salida es trazarlo a un lienzo! 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 rectángulos se superponen ...

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

Aquí está el código que escribí para el algoritmo de barrido de área:

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

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 <Double, List <KeyValuePair <Rectangle, Boolean >>> rectángulos;

  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 rectángulos

  4. Mantenga un conjunto de rectángulos 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 rectángulos por su coordenada y
  6. Haz un bucle a través de los rectángulos 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 rectángulos, 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:

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

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í (rectángulos 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 rectángulos que estamos analizando actualmente en la tira, de arriba a abajo, para rectángulos 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 rectángulos que tienen la misma coordenada superior / inferior que está mirando actualmente, los múltiples rectángulos 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 rectángulos 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 suma esta diferencia.

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

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

Como sus rectángulos son todos rectangulares, las líneas horizontales y verticales de los rectángulos formarán una cuadrícula rectangular irregular. Puedes "pintar" los rectángulos 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 rectángulos 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 rectángulos. 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.

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

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 .

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 rectángulos 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 rectángulos) con líneas de barrido horizontales para cada par de líneas de barrido verticales consecutivas.

Si el objetivo es solo descubrir el área total cubierta por todos los rectángulos, entonces las líneas de barrido horizontales no son necesarias y solo una fusión de todos los rectángulos 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 rectángulos 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 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(); }

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 /// <summary> /// see algorithm for detecting overlapping areas here: https://.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

Puede simplificar este problema bastante si divide cada rectángulo en rectángulos más pequeños. Recoge todas las coordenadas X e Y de todos los rectángulos, 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 rectángulos que se superponen ya sea al 0% o al 100%, si los clasificas, será fácil encontrar los rectángulos idénticos.

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

Si sus rectángulos 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.

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

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

Teniendo en cuenta que tenemos dos rectángulos (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 <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; }

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 rectángulos 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 rectángulos.
  • 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 dinámico. 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.

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 rectángulos 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 suma 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 rectángulos, cada vez que mueve una celda de 1 a 2.

En la pregunta, los rectángulos 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.