Was ist ein effizienter Algorithmus Bereich Overlapping Rectangles zu finden
https://stackoverflow.com/questions/244452
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Meine Situation
- Input: eine Reihe von Rechtecken
- jede rect besteht aus 4 Doppelzimmer wie folgt aus: (x0, y0, x1, y1)
- , die sie nicht „gedreht“ in jedem Winkel, alles, was sie „normal“ Rechtecken sind, die „up / down“ und „links / rechts“ in Bezug auf den Bildschirm gehen
- sie zufällig angeordnet sind - sie können an den Kanten berühren, überlappend oder keinen Kontakt haben
- Ich werde mehrere hundert Rechtecke haben
- dies in C # implementiert ist
muss ich
finden- Der Bereich, der durch ihre Überlappung gebildet wird, - die ganze Fläche in der Leinwand, dass mehr als ein Rechteck „umfasst“ (zum Beispiel mit zwei Rechtecken, würde es der Schnittpunkt sein)
- Ich brauche nicht die Geometrie der Überlappung - nur den Bereich (Beispiel: 4 sq Zoll)
- Überlappungen sollten nicht mehrfach gezählt werden - so zum Beispiel 3 Rects vorstellen, die die gleiche Größe und Position haben - sie rechts oben auf sie sind - dieser Bereich einmal gezählt werden soll (nicht dreimal)
Beispiel
- Das Bild unten enthält dre Rechtecke: A, B, C
- A und B überlappen (wie durch Striche angedeutet)
- B und C überlappen (wie durch Striche angedeutet)
- Was ich suche, ist der Bereich, wo die Striche angezeigt werden
-
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
Lösung
Ein effizienter Weg, um diesen Bereich der Berechnung ist ein Sweep-Algorithmus zu verwenden. Nehmen wir an, dass wir eine vertikale Linie L (x) durch die Vereinigung von Rechtecke U fegen:
- zunächst einmal, müssen Sie eine Ereigniswarteschlange Q bauen, die in diesem Fall ist die geordnete Liste aller x-Koordinaten (links und rechts) der Rechtecke.
- während des Sweeps, sollten Sie eine 1D-Datenstruktur erhalten, die Ihnen die Gesamtlänge der Kreuzung von L geben soll (x) und U. Das Wichtigste ist, dass diese Länge zwischen zwei aufeinanderfolgenden Ereignissen q und q konstant ist‘von Q. wenn also l (q) bezeichnet die Gesamtlänge L (q +) (dh L nur auf der right von q) durchteuft mit U, der überstrichene Fläche durch L zwischen Ereignissen q und q‘ist genau, l (q) * (q‘- q) .
- Sie müssen nur alle diese gefegt Bereiche zusammenzufassen, um die insgesamt einen.
Wir müssen noch das 1D-Problem zu lösen. Sie wollen eine 1D-Struktur, die dynamisch eine Vereinigung von (vertikal) Segmente berechnet. Durch die dynamischen, meine ich, dass man manchmal ein neues Segment hinzufügen, und manchmal eine entfernen.
ich bereits in meiner Antwort ausführlich auf dieses Kollabieren Bereiche in Frage , wie es in einer statischen Art und Weise zu tun (was in der Tat ein 1D-Sweep ist). Also, wenn Sie wollen etwas einfach, können Sie direkt die Anwendung (von der Union für jedes Ereignis neu berechnet). Wenn Sie etwas effizienter möchten, müssen Sie nur um es ein bisschen anpassen:
- unter der Annahme, dass Sie die Vereinigung von Segmenten S kennen 1 ... S n besteht aus disjoints Segmenten D 1 ... D < sub> k . Hinzufügen von S n + 1 ist sehr einfach, man muss nur beide Enden von S orten müssen n + 1 amongs die Enden von D 1 .. .D k .
- unter der Annahme, dass Sie die Vereinigung von Segmenten S kennen 1 ... S n besteht aus disjoints Segmenten D 1 ... D < sub> k , Entfernen von Segment S i (vorausgesetzt, dass S i wurde in D j ) ist die Vereinigung von Segmenten Neuberechnen dass D j bestand aus, mit Ausnahme S i (den statischen Algorithmus).
Dies ist Ihr dynamischer Algorithmus. Unter der Annahme, dass Sie sortierten Sets mit Log-Zeit Standortabfragen verwenden D darstellen 1 ... D k , ist dies wahrscheinlich die effizienteste nicht-spezialisierte Methode, die Sie bekommen können .
Andere Tipps
Ein Weg-out-Ansatz ist es auf eine Leinwand zu zeichnen! Zeichnen jedes Rechteck eine semi-transparente Farbe. Die .NET-Laufzeit wird die Zeichnung in optimierten, nativen Code tun -. Oder sogar ein Hardware-Beschleuniger mit
Dann müssen Sie die Pixel Read-Back. Ist jedes Pixel der Hintergrundfarbe, das Rechteck Farbe oder eine andere Farbe? Der einzige Weg, es eine andere Farbe sein kann, ist, wenn zwei oder mehr Rechtecken überlappen ...
Wenn dies zu viel von einem Betrüger ist, würde ich den Quadtree empfehlen als andere Antworter taten, oder die r-Baum .
Dies ist einige schnelle und schmutzige Code, den ich in der TopCoder SRM 160 Div 2 verwendet wird.
t = top
b = botttom
l = links
r = rechts
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;
}
}
Die einfachste Lösung
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 diesem Beispiel erstellen wir zwei Null-Matrizen, die die Größe der Leinwand sind. Für jedes Rechteck Füllen einer dieser Matrizen mit solchen, in denen das Rechteck Raum einnimmt. Zusammengefasst dann die Matrizen. Jetzt sum(A+B > 0) ist das Gebiet der Union, und sum(A+B > 1) ist der Bereich der Überlappung. Dieses Beispiel kann auf mehrere Rechtecke leicht verallgemeinern.
Hier ist etwas, das aus der Spitze von meinem Kopf klingt wie es funktionieren könnte:
-
Erstellen Sie ein Wörterbuch mit einem doppelten Schlüssel und eine Liste von Rechteck + Boolesche Werte, wie folgt aus:
Wörterbuch
-
Für jedes Rechteck in Ihrem Set, um die entsprechende Liste für die x0 finden und den x1-Wert, und fügen Sie das Rechteck auf diese Liste, mit einem Booleschen Wert true für x0 und falsch für x1. So können Sie jetzt eine komplette Liste aller haben x-Koordinaten, die jedes Rechteck entweder eintritt (true) oder Blätter (false) die x-Richtung
-
von diesem Wörterbuch alle Schlüssel Schnappen (alle verschiedene x-Koordinaten), sortieren und Schleife durch sie um, stellen Sie sicher, dass Sie sowohl an der aktuellen x-Wert, und die nächste bekommen als gut (Sie müssen sie beide). Dies gibt Ihnen einzelne Streifen von Rechtecken
- Achten Sie auf eine Reihe von Rechtecken Sie derzeit auf der Suche, die leer beginnt. Für jeden x-Wert, den Sie in Punkt iterieren 3, wenn das Rechteck mit einem wahren Wert registriert ist, fügen Sie es den Satz, es anders entfernen.
- für einen Streifen, sortieren, die Rechtecke in ihren Y-Koordinate
- Schleife durch die Rechtecke in dem Streifen, überlappende Entfernungen Zählung (mir unklar, als der noch, wie dies effizient zu tun)
- Berechnen Breite des Streifens mal Höhe Entfernungen von Überschneidungen zu bekommen Bereichen
B. 5 Rechtecken, auf dem jeweils anderen zeichnen, von a bis e:
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
ddddddddddddddddddddddddddddd
ddddddddddddddddddddddddddddd
ddddddddddddddeeeeeeeeeeeeeeeeee
ddddddddddddddeeeeeeeeeeeeeeeeee
ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc eeeeeeeeeeeeeeeeee
cccccccccccc eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc
Hier ist die Liste der x-Koordinaten:
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
Die Liste wäre (wobei jedes v einfach gegeben wird eine Koordinate beginnend bei 0 und geht nach oben):
0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b
Jeder Streifen würde somit werden (Rechtecken von oben nach unten geordnet):
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
für jeden Streifen, die Überlappung wäre:
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
Ich könnte mir vorstellen, dass eine Variation der Art + Enter / Leave-Algorithmus für die Oben-Unten-Überprüfung wäre auch machbar sein:
- sortieren Sie die Rechtecke wir zur Zeit in dem Streifen von oben nach unten zu analysieren, für Rechtecke mit dem gleichen Top-Koordinate, sortieren sie nach unten koordinieren und
- iterieren durch die y-Koordinaten, und wenn Sie ein Rechteck eingeben, fügen Sie es zu dem Satz, wenn Sie ein Rechteck verlassen, entfernen Sie sie aus dem Satz
- , wenn der Satz mehr als ein Rechteck hat, haben Sie überlappen (und wenn Sie alle Rechtecke stellen Sie sicher, hinzufügen / entfernen, die die gleiche oben / unten haben koordinieren Sie gerade betrachten, mehrere überlappende Rechtecke wäre kein Problem sein,
Für die 1-2 Streifen oben, du so laufen würde:
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
Sie würden nicht wirklich haben hier entweder einen tatsächlichen Satz zu erhalten, nur die Anzahl der Rechtecke Sie innen sind, wann immer dies 1 bis 2 geht, speichern Sie die y, und wenn er von 2 bis 1 geht, berechnen Strom y -. gespeichert y, und diese Differenz summiert
Hope dies war verständlich, und wie gesagt, das ist aus der Spitze von meinem Kopf, nicht in irgendeiner Art und Weise getestet.
Am Beispiel:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) sammelt all x-Koordinaten (links und rechts) in eine Liste, dann sortieren und Duplikate entfernen
1 3 4 5 6
2) Sammle alle y-Koordinaten (oben und unten) in eine Liste, dann Sortieren und Entfernen von Duplikaten
1 2 3 4 6
3) Erstellen einer 2D-Anordnung nach der Anzahl der Lücken zwischen den einzigartig x-Koordinaten * Anzahl der Lücken zwischen den einzigartigen Y-Koordinaten.
4 * 4
4) malen alle Rechtecke in dieses Raster, die Zählung jeder Zelle erhöht wird es erfolgt über:
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), wobei die Summe der Bereiche der Zellen in dem Gitter, die eine Anzahl größer als eins haben, ist der Bereich der Überlappung. Für eine bessere Effizienz bei der spärlichen Anwendungsfällen, können Sie tatsächlich eine laufende Summe der Fläche halten, wie Sie die Rechtecken malen, jedes Mal, wenn eine Zelle von 1 bis 2 bewegen.
In der Frage, werden die Rechtecke als vier Doppel beschrieben. Doubles enthalten typischerweise Rundungsfehler und Fehler kann schleichen sich in Ihrem berechneten Überlappungsbereich. Wenn die rechtlichen Koordinaten bei endlichen Punkte sind, sollten Sie eine Integer-Darstellung verwendet wird.
PS unter Verwendung des Hardware-Beschleuniger, wie in meiner anderen Antwort ist nicht so eine schäbige Idee, wenn die Auflösung akzeptabel ist. Es ist auch einfach, die ich oben skizziert in viel weniger Code als der Ansatz zu implementieren. Pferde für Kurse.
Hier ist der Code, den ich für den Bereich Sweep Algorithmus geschrieben:
#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;
}
Sie können dieses Problem ziemlich viel vereinfachen, wenn Sie jedes Rechteck in kleinere Rechtecke aufgeteilt. Sammeln Sie alle der X- und Y-Koordinaten aller Rechtecke, und diese werden Ihre Split-Punkte - wenn ein Rechteck, um die Linie überquert, spaltete es in zwei Teile. Wenn Sie fertig sind, haben Sie eine Liste der Rechtecke, die entweder 0% oder 100% überlappen, wenn man sie sortieren es einfach sein sollte, die identische zu finden.
Es gibt eine Lösung auf den Link http: //codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html für die Gesamtfläche mehrerer Rechtecken zu finden, so dass der Überlappungsbereich nur einmal gezählt wird.
Die obige Lösung kann nur den überlappenden Bereich (und das auch nur einmal, auch wenn der Überlappungsbereich durch mehrere Rechtecken abgedeckt ist) für jedes Paar von aufeinanderfolgenden vertikalen Durchlauflinien mit horizontalen Linien berechnen Sweep erweitert werden.
Wenn Ziel nur ist die Gesamtfläche durch die alle Rechtecke abgedeckt, um herauszufinden, dann sind horizontale Ablenkung Linien nicht benötigt und nur eine Zusammenführung aller Rechtecke zwischen zwei vertikalen Linien fegen würde sich die Fläche geben.
Auf der anderen Seite, wenn Sie den Überlappungsbereich nur berechnet werden sollen, werden die horizontale Schwung Linien benötigt, um herauszufinden, wie viele Rechtecken überschneiden sich in zwischen vertikalen (y1, y2) Sweep-Linien.
Hier ist der Arbeitscode für die Lösung, die ich in Java implementiert.
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();
}
Wenn Ihr Rechtecke spärlich sein wird (meist ich schneid nicht), dann könnte es einen Blick auf rekursive dimensional Clustering wert sein. Andernfalls wird ein Quad-Baum scheint der Weg zu gehen (wie von anderen Plakaten erwähnt.
Dies ist ein häufiges Problem bei Kollisionserkennung in Computerspielen, so gibt es keinen Mangel an Ressourcen Möglichkeiten, was darauf hindeutet, es zu lösen.
Hier ist eine schöne Blog-Post zusammenfassend RCD.
Hier ist ein Dr.Dobbs Artikel verschiedene Kollisionserkennungsalgorithmen zusammenfasst, was würde geeignet sein.
Diese Art der Kollisionserkennung häufig AABB (Axis Aligned Bounding Boxes) genannt wird, das ist ein guter Ausgangspunkt für ein google-Suche .
Sie können die Überlappung auf der x- und auf der y-Achse finden und diejenigen multiplizieren.
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);
}
fand ich eine andere Lösung als der Sweep-Algorithmus.
Da Ihr Rechtecke sind alle rechteckig angeordnet, die horizontalen und vertikalen Linien der Rechtecke wird eine rechteckige unregelmäßige Gitter bilden. Sie können ‚Farbe‘ die Rechtecke auf diesem Gitter; was bedeutet, können Sie bestimmen, welche Felder des Gitters ausgefüllt werden. Da die Gitterlinien von den Grenzen der gegebenen Rechtecke gebildet sind, ein Feld, in diesem Raster wird immer entweder vollständig leer oder vollständig durch ein Rechteck gefüllt.
ich das Problem in Java zu lösen hatte, also hier ist meine Lösung: http://pastebin.com/03mss8yf
Diese Funktion berechnet der gesamten Fläche durch die Rechtecke besetzt. Wenn Sie interessiert nur in der ‚Überlappung‘ Teil sind, müssen Sie den Code-Block zwischen den Zeilen 70 und 72 erstrecken Vielleicht können Sie einen zweiten Satz verwenden zu speichern sind, die Rasterfelder mehr als einmal verwendet. Ihr Code zwischen Zeile 70 und 72 sollte mit einem Block ersetzt werden, wie:
GridLocation gl = new GridLocation(curX, curY);
if(usedLocations.contains(gl) && usedLocations2.add(gl)) {
ret += width*height;
} else {
usedLocations.add(gl);
}
Die Variable usedLocations2 hier ist vom gleichen Typ wie usedLocations; es wird gebaut an der gleichen Stelle.
Ich bin nicht wirklich vertraut mit Komplexität Berechnungen; so weiß ich nicht, welche der beiden Lösungen (Sweep oder meine Grid-Lösung) wird / Maßstab besser.
In Anbetracht haben wir zwei Rechtecke (A und B), und wir haben ihre untere linke (x1, y1) und oben rechts (x2, y2) Koordination. Die Verwendung von folgendem Code können Sie den Überlappungsbereich in C ++ berechnen.
#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;
}
Die folgende Antwort soll die gesamte Fläche nur einmal geben. es kommt bisherige Antworten, aber jetzt in C # implementiert. Es funktioniert auch mit Schwimmern (oder doppelt, wenn Sie [es nicht über die Werte nicht itterate).
Credits: http://codercareer.blogspot.co. il / 2011/12 / no-27-Area-of-rectangles.html
EDIT: Die OP fragte nach dem Überlappungsbereich - das ist natürlich sehr einfach:
var totArea = rects.Sum(x => x.Width * x.Height);
und dann die Antwort lautet:
var overlappingArea =totArea-GetArea(rects)
Hier ist der Code:
#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
