Che cos'è un algoritmo efficiente per trovare l'area dei rettangoli sovrapposti
https://stackoverflow.com/questions/244452
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
La mia situazione
- Input: una serie di rettangoli
- ogni rettangolo è composto da 4 doppie in questo modo: (x0, y0, x1, y1)
- non sono " ruotato " ad ogni angolo, sono tutti " normale " rettangoli che vanno " su / giù " e " sinistra / destra " rispetto allo schermo
- sono posizionati in modo casuale: potrebbero toccare i bordi, sovrapporsi o non avere alcun contatto
- Avrò diverse centinaia di rettangoli
- questo è implementato in C #
Devo trovare
- L'area che si forma dalla loro sovrapposizione - tutta l'area nell'area di disegno che più di un rettangolo " copre " (ad esempio con due rettangoli, sarebbe l'intersezione)
- Non ho bisogno della geometria della sovrapposizione, ma solo dell'area (esempio: 4 pollici quadrati)
- Le sovrapposizioni non devono essere conteggiate più volte - quindi, ad esempio, immagina che 3 rect abbiano le stesse dimensioni e posizione - siano uno sopra l'altro - quest'area dovrebbe essere contata una volta (non tre volte)
Esempio
- L'immagine seguente contiene tre rettangoli: A, B, C
- A e B si sovrappongono (come indicato da trattini)
- B e C si sovrappongono (come indicato da trattini)
- Quello che sto cercando è l'area in cui sono mostrati i trattini
-
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
Soluzione
Un modo efficiente di calcolare quest'area è usare un algoritmo di sweep. Supponiamo di spazzare una linea verticale L (x) attraverso l'unione dei rettangoli U:
- prima di tutto, devi costruire una coda di eventi Q, che è, in questo caso, l'elenco ordinato di tutte le coordinate x (sinistra e destra) dei rettangoli.
- durante lo sweep, dovresti mantenere una struttura di dati 1D, che dovrebbe darti la lunghezza totale dell'intersezione di L (x) e U. L'importante è che questa lunghezza sia costante tra due eventi consecutivi q e q 'di Q. Quindi, se l (q) indica la lunghezza totale di L (q +) (cioè L proprio sul lato destro di q) intersecata con U, l'area travasata da L tra gli eventi q e q 'è esattamente l (q) * (q '- q).
- devi solo riassumere tutte queste aree spazzate per ottenere quella totale.
Dobbiamo ancora risolvere il problema 1D. Volete una struttura 1D, che calcola dinamicamente un'unione di segmenti (verticali). Per dinamicamente, intendo che a volte aggiungi un nuovo segmento e talvolta rimuovi uno.
Ho già dettagliato nella mia risposta a questo domanda di intervalli collassanti come farlo in modo statico (che in realtà è una scansione 1D). Quindi, se vuoi qualcosa di semplice, puoi applicarlo direttamente (ricalcolando l'unione per ogni evento). Se vuoi qualcosa di più efficiente, devi solo adattarlo un po ':
- supponendo di conoscere l'unione dei segmenti S 1 ... S n è costituito da segmenti di disgiunzione D 1 ... D < sub> k . L'aggiunta di S n + 1 è molto semplice, devi solo individuare entrambe le estremità di S n + 1 tra le estremità di D 1 .. .D k .
- supponendo di conoscere l'unione dei segmenti S 1 ... S n è costituito da segmenti di disgiunzione D 1 ... D < sub> k , eliminando il segmento S i (supponendo che S i sia stato incluso in D j ) significa ricalcolare l'unione dei segmenti di cui D j consisteva, tranne S i (usando l'algoritmo statico).
Questo è il tuo algoritmo dinamico. Supponendo che utilizzerai set ordinati con query sulla posizione del tempo di log per rappresentare D 1 ... D k , questo è probabilmente il metodo non specializzato più efficiente che puoi ottenere .
Altri suggerimenti
Un approccio d'uscita è quello di tracciarlo su una tela! Disegna ogni rettangolo usando un colore semitrasparente. Il runtime .NET eseguirà il disegno in codice nativo ottimizzato, o anche utilizzando un acceleratore hardware.
Quindi, devi rileggere i pixel. Ogni pixel è il colore di sfondo, il colore del rettangolo o un altro colore? L'unico modo in cui può essere un altro colore è se due o più rettangoli si sovrappongono ...
Se questo è troppo di un imbroglione, consiglierei il quad-albero come ha fatto un altro risponditore, oppure r-tree .
Questo è un codice rapido e sporco che ho usato in TopCoder SRM 160 Div 2.
t = top
b = fondo
l = sinistra
r = giusto
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 soluzione più semplice
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)
In questo esempio, creiamo due matrici zero che hanno le dimensioni della tela. Per ogni rettangolo, riempire una di queste matrici con quelle in cui il rettangolo occupa spazio. Quindi sommare le matrici. Ora sum(A+B > 0) è l'area dell'unione e sum(A+B > 1) è l'area della sovrapposizione. Questo esempio può facilmente generalizzare in più rettangoli.
Ecco qualcosa che dalla parte superiore della mia testa sembra che potrebbe funzionare:
-
Crea un dizionario con una doppia chiave e un elenco di rettangolo + valori booleani, come questo:
dizionario lt &; Doppio, Elenco & Lt; & KeyValuePair lt; Rettangolo, booleano & Gt; & Gt; & Gt; rettangoli;
-
Per ogni rettangolo nel tuo set, trova l'elenco corrispondente per i valori x0 e x1 e aggiungi il rettangolo a tale elenco, con un valore booleano true per x0 e false per x1. In questo modo ora hai un elenco completo di tutte le coordinate x in cui ciascun rettangolo inserisce (true) o lascia (false) la direzione x
-
Prendi tutte le chiavi di quel dizionario (tutte le coordinate x distinte), ordinale e passale in sequenza, assicurati di poter ottenere sia il valore x corrente, sia quello successivo come bene (hai bisogno di entrambi). Questo ti dà singole strisce di rettangoli
- Mantieni una serie di rettangoli che stai guardando, che inizia vuota. Per ogni valore x ripetuto al punto 3, se il rettangolo è registrato con un valore vero, aggiungilo al set, altrimenti rimuovilo.
- Per una striscia, ordina i rettangoli in base alla loro coordinata y
- Attraversa i rettangoli nella striscia, contando le distanze sovrapposte (non mi è ancora chiaro come farlo in modo efficiente)
- Calcola la larghezza delle strisce volte l'altezza delle distanze sovrapposte per ottenere le aree
Esempio, 5 rettangoli, disegnati uno sopra l'altro, dalla a alla e:
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
ddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddd
ddddddddddddddeeeeeeeeeeeeeeeeee
ddddddddddddddeeeeeeeeeeeeeeeeee
ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc eeeeeeeeeeeeeeeeee
cccccccccccc eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc
Ecco l'elenco delle coordinate 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
L'elenco sarebbe (dove ad ogni v viene semplicemente data una coordinata che inizia da 0 e sale):
0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b
Ogni striscia sarebbe quindi (rettangoli ordinati dall'alto verso il basso):
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
per ogni striscia, la sovrapposizione sarebbe:
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
Immagino che una variante dell'algoritmo di ordinamento + invio / abbandono per il controllo dall'alto in basso sarebbe fattibile anche:
- ordina i rettangoli che stiamo attualmente analizzando nella striscia, dall'alto verso il basso, per i rettangoli con la stessa coordinata superiore, ordinali anche per la coordinata inferiore
- scorre le coordinate y e quando inserisci un rettangolo, aggiungilo al set, quando lasci un rettangolo, rimuovilo dal set
- ogni volta che l'insieme ha più di un rettangolo, hai sovrapposizioni (e se ti assicuri di aggiungere / rimuovere tutti i rettangoli che hanno le stesse coordinate superiore / inferiore che stai attualmente guardando, più rettangoli sovrapposti non sarebbero un problema
Per la striscia 1-2 sopra, faresti iter in questo modo:
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
Non dovresti effettivamente mantenere un set reale anche qui, solo il conteggio dei rettangoli che sei dentro, ogni volta che questo va da 1 a 2, memorizza la y e ogni volta che passa da 2 a 1, calcola y corrente - y memorizzato, e somma questa differenza.
Spero che questo sia comprensibile, e come ho detto, questo è fuori dalla mia testa, non testato in alcun modo.
Utilizzando l'esempio:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) raccogli tutte le coordinate x (sia a destra che a sinistra) in un elenco, quindi ordinale e rimuovi i duplicati
1 3 4 5 6
2) raccogli tutte le coordinate y (sia in alto che in basso) in un elenco, quindi ordinale e rimuovi i duplicati
1 2 3 4 6
3) crea un array 2D per numero di spazi tra le coordinate x uniche * numero di spazi tra le coordinate y uniche.
4 * 4
4) dipingi tutti i rettangoli in questa griglia, aumentando il conteggio di ogni cella su cui si verifica:
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 somma totale delle aree delle celle nella griglia che hanno un conteggio maggiore di una è l'area di sovrapposizione. Per una migliore efficienza in casi d'uso sparsi, puoi effettivamente mantenere un totale parziale dell'area mentre dipingi i rettangoli, ogni volta che sposti una cella da 1 a 2.
Nella domanda, i rettangoli sono descritti come quattro doppie. I doppi in genere contengono errori di arrotondamento e l'errore potrebbe insinuarsi nell'area di sovrapposizione calcolata. Se le coordinate legali sono in punti finiti, prendere in considerazione l'utilizzo di una rappresentazione intera.
PS usando l'acceleratore hardware come nella mia altra risposta non è un'idea così squallida, se la risoluzione è accettabile. È anche facile da implementare con molto meno codice rispetto all'approccio che ho descritto sopra. Cavalli per corsi.
Ecco il codice che ho scritto per l'algoritmo di area sweep:
#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;
}
Puoi semplificare un po 'questo problema se dividi ogni rettangolo in rettangoli più piccoli. Raccogli tutte le coordinate X e Y di tutti i rettangoli e questi diventano i tuoi punti di divisione: se un rettangolo attraversa la linea, dividila in due. Al termine, hai un elenco di rettangoli che si sovrappongono allo 0% o al 100%, se li ordini dovrebbe essere facile trovare gli stessi.
C'è una soluzione elencata al link http: //codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html per trovare l'area totale di più rettangoli in modo tale che l'area sovrapposta venga conteggiata una sola volta.
La soluzione sopra può essere estesa per calcolare solo l'area sovrapposta (e anche una sola volta anche se l'area sovrapposta è coperta da più rettangoli) con linee di sweep orizzontali per ogni coppia di linee di sweep verticali consecutive.
Se lo scopo è solo quello di scoprire l'area totale coperta da tutti i rettangoli, allora non sono necessarie linee di sweep orizzontali e solo una fusione di tutti i rettangoli tra due linee di sweep verticali darebbe l'area.
D'altra parte, se si desidera calcolare solo l'area sovrapposta, sono necessarie le linee di sweep orizzontale per scoprire quanti rettangoli si sovrappongono tra le linee di sweep verticali (y1, y2).
Ecco il codice di lavoro per la soluzione che ho implementato in 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();
}
Se i tuoi rettangoli saranno sparsi (per lo più non si intersecano), potrebbe valere la pena dare un'occhiata al raggruppamento dimensionale ricorsivo. Altrimenti un quad-albero sembra essere la strada da percorrere (come è stato menzionato da altri poster.
Questo è un problema comune nel rilevamento delle collisioni nei giochi per computer, quindi non mancano le risorse che suggeriscono modi per risolverlo.
Qui è un bel post sul blog che riassume RCD.
Qui è un articolo di Dr.Dobbs che sintetizza vari algoritmi di rilevamento delle collisioni, che essere adatto.
Questo tipo di rilevamento delle collisioni è spesso chiamato AABB (Axis Aligned Bounding Boxes), questo è un buon punto di partenza per un ricerca google .
Puoi trovare la sovrapposizione sull'asse xe sull'asse y e moltiplicarli.
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);
}
Ho trovato una soluzione diversa dall'algoritmo sweep.
Poiché i tuoi rettangoli sono tutti posizionati in modo rettangolare, le linee orizzontali e verticali dei rettangoli formeranno una griglia rettangolare irregolare. Puoi 'dipingere' i rettangoli su questa griglia; ciò significa che è possibile determinare quali campi della griglia verranno compilati. Poiché le linee della griglia sono formate dai confini dei rettangoli indicati, un campo in questa griglia sarà sempre completamente vuoto o completamente riempito da un rettangolo.
Ho dovuto risolvere il problema in Java, quindi ecco la mia soluzione: http://pastebin.com/03mss8yf
Questa funzione calcola l'intera area occupata dai rettangoli. Se sei interessato solo alla parte 'sovrapposizione', devi estendere il blocco di codice tra le righe 70 e 72. Forse puoi usare un secondo set per memorizzare quali campi della griglia sono usati più di una volta. Il tuo codice tra la riga 70 e 72 dovrebbe essere sostituito con un blocco come:
GridLocation gl = new GridLocation(curX, curY);
if(usedLocations.contains(gl) && usedLocations2.add(gl)) {
ret += width*height;
} else {
usedLocations.add(gl);
}
La variabile usedLocations2 qui è dello stesso tipo di usedLocations; sarà costruito allo stesso punto.
Non ho molta familiarità con i calcoli della complessità; quindi non so quale delle due soluzioni (sweep o la mia soluzione grid) funzionerà / ridimensionerà meglio.
Considerando che abbiamo due rettangoli (A e B) e abbiamo il loro coordinamento in basso a sinistra (x1, y1) e in alto a destra (x2, y2). Utilizzando il seguente pezzo di codice è possibile calcolare l'area sovrapposta in 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 seguente risposta dovrebbe fornire l'Area totale una sola volta. arrivano le risposte precedenti, ma implementate ora in C #. Funziona anche con float (o double, se necessario [non scorre sui VALORI).
Credits: http://codercareer.blogspot.co. Il / 2011/12 / no-27-area-di-rectangles.html
EDIT: L'OP ha chiesto l'area di sovrapposizione, ovviamente molto semplice:
var totArea = rects.Sum(x => x.Width * x.Height);
e quindi la risposta è:
var overlappingArea =totArea-GetArea(rects)
Ecco il codice:
#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
