¿Qué es un algoritmo eficiente para encontrar el área de rectángulos superpuestos?
https://stackoverflow.com/questions/244452
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Mi situación
- Entrada: un conjunto de rectángulos
- cada rect está compuesto por 4 dobles como este: (x0, y0, x1, y1)
- no son " rotados " en cualquier ángulo, todos son " normal " rectángulos que van " arriba / abajo " y " izquierda / derecha " con respecto a la pantalla
- se colocan al azar: pueden tocar 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 en el lienzo que más de un rectángulo " cubre " (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 deben contarse varias veces, así que, por ejemplo, imagine 3 rectificaciones que tengan el mismo tamaño y posición, están una encima de la otra, esta área debe contarse una vez (no tres veces)
Ejemplo
- La imagen a continuación contiene tres rectángulos: A, B, C
- A y B se superponen (como lo indican los guiones)
- B y C se superponen (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
Solución
Una manera 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 los rectángulos U:
- en primer lugar, debe crear 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 proporcionar la longitud total de la intersección de L (x) y U. Lo importante es que esta longitud es constante entre dos eventos consecutivos q y q 'de P. Entonces, si l (q) denota la longitud total de L (q +) (es decir, L justo en el lado derecho de q) intersectado 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 calcule dinámicamente una unión de segmentos (verticales). Al decir dinámicamente, quiero decir que a veces agrega un nuevo segmento y, a veces, elimina uno.
Ya detallé en mi respuesta a esto pregunta de rangos de colapso cómo hacerlo de forma estática (que de hecho es un barrido 1D). Entonces, si desea 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 conoce la unión de los segmentos S 1 ... S n consiste en segmentos disjuntos D 1 ... D < sub> 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 conoce la unión de los segmentos S 1 ... S n consiste en segmentos disjuntos D 1 ... D < sub> k , eliminar el segmento S i (suponiendo que S i se haya incluido en D j ) significa volver a calcular la unión de segmentos que D j consistía, excepto S i (utilizando el algoritmo estático).
Este es su algoritmo dinámico. Suponiendo que usará 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 .
Otros consejos
¡Un enfoque de salida es trazarlo en 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 usará un acelerador de hardware.
Luego, debe volver a leer los píxeles. ¿Es cada píxel 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 engañoso, recomendaría el quad-tree como lo hizo otro respondedor, o el r-tree .
Este es un código rápido y sucio que utilicé en el TopCoder SRM 160 Div 2.
t = arriba
b = parte inferior
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;
}
}
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, llena una de estas matrices con unas donde el rectángulo ocupe 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.
Aquí hay algo que suena como que podría funcionar:
-
Cree un diccionario con una clave doble y una lista de rectángulos + valores booleanos, como este:
Diccionario < Doble, Lista & Lt; KeyValuePair & Lt; Rectángulo, booleano & Gt; & Gt; & Gt; rectángulos;
-
Para cada rectángulo en su conjunto, encuentre 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 manera, ahora tiene una lista completa de todas las coordenadas x que cada rectángulo ingresa (verdadero) o deja (falso) la dirección x
-
Tome todas las claves de ese diccionario (todas las coordenadas x distintas), ordénelas y recorralas en orden, asegúrese de que puede obtener tanto el valor x actual como el siguiente como bueno (los necesitas a ambos). Esto le proporciona tiras individuales de rectángulos
- Mantenga un conjunto de rectángulos que está viendo actualmente, que comienza vacío. Para cada valor x que repite en el punto 3, si el rectángulo está registrado con un valor verdadero, agréguelo al conjunto, de lo contrario, retírelo.
- Para una tira, ordena los rectángulos por su coordenada y
- Recorre los rectángulos en la tira, contando las distancias superpuestas (aún no tengo claro cómo hacerlo de manera eficiente)
- Calcular el ancho de la tira por la altura de las distancias superpuestas para obtener áreas
Ejemplo, 5 rectángulos, dibuje uno encima del otro, de a 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
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 cada v simplemente recibe 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 (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 de arriba a abajo también sería factible:
- 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 también por coordenada inferior
- itere a través de las coordenadas y, y cuando ingrese un rectángulo, agréguelo al conjunto, cuando deje un rectángulo, retírelo del conjunto
- cada vez que el conjunto tiene más de un rectángulo, tiene superposición (y si se asegura de agregar / eliminar todos los rectángulos que tienen la misma coordenada superior / inferior que está viendo actualmente, múltiples rectángulos superpuestos no serían un problema
Para la tira 1-2 anterior, iteraría así:
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
Tampoco tendrías que mantener un conjunto real aquí, solo el recuento de los rectángulos en los que estás dentro, cada vez que va de 1 a 2, almacena la y, y cada vez que va de 2 a 1, calcula actual y - almacenado y, y suma esta diferencia.
Espero que esto sea comprensible, y como dije, esto está fuera de mi alcance, no probado de ninguna manera.
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 los duplicados
1 3 4 5 6
2) recopile todas las coordenadas y (tanto superior como inferior) en una lista, luego ordénelo y elimine los duplicados
1 2 3 4 6
3) cree una matriz 2D por número de espacios entre las coordenadas x únicas * número de espacios entre las coordenadas y únicas.
4 * 4
4) pinta 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 arrastrarse a su área de superposición calculada. Si las coordenadas legales están en puntos finitos, considere usar una representación entera.
PS usando el acelerador de hardware como en mi otra respuesta no es una idea tan lamentable, si la resolución es aceptable. También es fácil de implementar en mucho menos código que el enfoque que describo anteriormente. Caballos para cursos.
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;
}
Puede simplificar un poco este problema si divide cada rectángulo en rectángulos más pequeños. Reúna todas las coordenadas X e Y de todos los rectángulos, y estos se convertirán en sus puntos de división: si un rectángulo cruza la línea, divídalo en dos. Cuando haya terminado, tiene una lista de rectángulos que se superponen 0% o 100%, si los ordena, debería ser fácil encontrar los idénticos.
Hay una solución listada en el enlace http: //codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html para encontrar el área total de varios rectángulos de modo que el área superpuesta se cuente solo una vez.
La solución anterior se puede extender para calcular solo el área superpuesta (y eso 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 encontrar el área total cubierta por todos los rectángulos, entonces no se necesitan líneas de barrido horizontales y solo una combinación de todos los rectángulos entre dos líneas de barrido verticales daría el área.
Por otro lado, si solo desea calcular el área superpuesta, las líneas de barrido horizontales son necesarias para averiguar cuántos rectángulos se superponen entre las líneas de barrido verticales (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();
}
Si sus rectángulos van a ser escasos (en su mayoría no se cruzan), entonces valdría la pena echar un vistazo al agrupamiento recursivo de dimensiones. De lo contrario, un árbol cuádruple parece ser el camino a seguir (como se ha mencionado en otros carteles.
Este es un problema común en la detección de colisiones en juegos de computadora, por lo que no faltan recursos que sugieran formas de resolverlo.
Aquí es una buena publicación de blog que resume RCD.
Aquí es un artículo de Dr.Dobbs que resume varios algoritmos de detección de colisión, que ser adecuado.
Este tipo de detección de colisión a menudo se llama AABB (Cajas delimitadas por ejes alineados), ese es un buen punto de partida para una búsqueda de google .
Puede encontrar la superposición en el eje xy en el eje y y multiplicarlos.
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 al algoritmo de barrido.
Dado que sus rectángulos son todos rectangulares, las líneas horizontales y verticales de los rectángulos formarán una cuadrícula rectangular irregular. Puede 'pintar' los rectángulos en esta cuadrícula; lo que significa que puede determinar qué campos de la cuadrícula 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 le interesa 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 con 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 usedLocations2 aquí es del mismo tipo que usedLocations; será construido en el mismo punto.
No estoy realmente 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.
Considerando que tenemos dos rectángulos (A y B) y tenemos su coordinación inferior izquierda (x1, y1) y superior derecha (x2, y2). Usando el siguiente fragmento 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;
}
La siguiente respuesta debería dar el Área total solo una vez. viene respuestas anteriores, pero implementado ahora en C #. Funciona también con flotadores (o dobles, si lo necesita [no se 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 superpuesta, eso obviamente es 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://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
