text: algorithm — Was ist ein effizienter Algorithmus, um überlappende Rechtecke zu finden?
  /Was ist ein effizienter Algorithmus, um überlappende Rechtecke zu finden?
  Eingabe: eine Reihe von Rechtecken
  jedes Rect besteht aus 4 Doubles wie folgt: (x0, y0, x1, y1)
  sie sind in keinem Winkel "gedreht", es handelt sich lediglich um "normale" Rechtecke, die in Bezug auf den Bildschirm "nach oben/unten" und "nach links/rechts" gehen
  sie werden zufällig platziert - sie berühren sich möglicherweise an den Rändern, überlappen sich oder haben keinen Kontakt
  Ich werde mehrere hundert Rechtecke haben
  dies ist in C # implementiert.
  Ich muss finden
  Der Bereich, der durch ihre Überlappung gebildet wird - der gesamte Bereich auf der Leinwand, den mehr als ein Rechteck "überdeckt" (z. B. mit zwei Rechtecken wäre dies die Schnittmenge).
  Ich brauche nicht die Geometrie der Überlappung - nur die Fläche (Beispiel: 4 Quadratzoll)
  Überlappungen sollten nicht mehrmals gezählt werden. Stellen Sie sich zum Beispiel 3 Rects vor, die die gleiche Größe und Position haben. Sie liegen direkt aufeinander.
  Das Bild unten enthält drei Rechtecke: A, B, C
  A und B überlappen sich (wie durch Striche angegeben)
  B und C überlappen sich (wie durch Striche angedeutet)
  Was ich suche, ist der Bereich, in dem die Striche angezeigt werden
  algorithmoptimizationgeometryperformance
  28.10.2008 namenlos
  Eine effiziente Methode zur Berechnung dieses Bereichs besteht in der Verwendung eines Sweep-Algorithmus. Nehmen wir an, wir streichen eine vertikale Linie L(x) durch die Vereinigung der Rechtecke U:
  zunächst müssen Sie eine Ereigniswarteschlange Q erstellen, die in diesem Fall die geordnete Liste aller X-Koordinaten (links und rechts) der Rechtecke ist.
  während des Sweeps sollten Sie eine 1D-Datenstruktur aufrechterhalten, die Ihnen die Gesamtlänge des Schnittpunkts von L(x) und U angibt. Wichtig ist, dass diese Länge zwischen zwei aufeinander folgenden Ereignissen q und q 'konstant ist. Wenn also l(q) die Gesamtlänge von L (q +) (dh L gerade auf der rechten Seite von q), die mit U geschnitten ist, bezeichnet, ist der Bereich, der mit L zwischen den Ereignissen q und q 'überstrichen ist, genau l (q) * (q '- q).
  sie müssen nur alle diese überstrichenen Bereiche zusammenfassen, um die Gesamtzahl zu erhalten.
  Wir müssen das 1D-Problem noch lösen. Sie möchten eine 1D-Struktur, die dynamisch eine Vereinigung von (vertikalen) Segmenten berechnet. Mit dynamisch meine ich, dass Sie manchmal ein neues Segment hinzufügen und manchmal ein Segment entfernen.
  Ich habe bereits ausführlich in meiner Antwort auf diese einklappende Bereichsfrage beschrieben, wie man dies statisch macht (was tatsächlich ein 1D-Sweep ist). Wenn Sie also etwas einfaches wollen, können Sie dies direkt anwenden (indem Sie die Vereinigung für jedes Ereignis neu berechnen). Wenn Sie etwas effizienteres wollen, müssen Sie es nur ein wenig anpassen:
  vorausgesetzt, Sie kennen die Vereinigung der Segmente S1... Sn besteht aus disjoints segmenten D1... dk. Hinzufügen von Sn + 1 ist sehr einfach, Sie müssen nur beide Enden von S findenn + 1 unter den Enden von D1... dk.
  vorausgesetzt, Sie kennen die Vereinigung der Segmente S1... Sn besteht aus disjoints segmenten D1... dk, Entfernen des Segments Sich (vorausgesetzt, dass Sich war in D enthaltenj) bedeutet, die Vereinigung der Segmente neu zu berechnen, die Dj bestand aus, außer Sich (unter Verwendung des statischen Algorithmus).
  Dies ist Ihr dynamischer Algorithmus. Angenommen, Sie verwenden sortierte Sätze mit Standortabfragen für Protokollzeiten, um D darzustellen1... dkDies ist wahrscheinlich die effizienteste, nicht spezialisierte Methode, die Sie erhalten können.
  29.10.2008 Camille
  Ein Ausweg besteht darin, es auf einer Leinwand zu plotten! Zeichnen Sie jedes Rechteck mit einer halbtransparenten Farbe. Die .NET-Laufzeitumgebung zeichnet das Zeichnen mit optimiertem, nativem Code - oder sogar mit einem Hardwarebeschleuniger.
  Dann müssen Sie die Pixel zurücklesen. Ist jedes Pixel die Hintergrundfarbe, die Rechteckfarbe oder eine andere Farbe? Es kann nur eine andere Farbe sein, wenn sich zwei oder mehr Rechtecke überlappen ...
  Wenn dies zu viel ist, würde ich den Quad-Tree wie einen anderen Antworter oder den r-Tree empfehlen.
  Dies ist ein schneller und schmutziger Code, den ich im TopCoder SRM 160 Div 2 verwendet habe.
  t = oben
  b = unten
  l = übrig
  r = richtig
  28.10.2008 LeppyR64
  In diesem Beispiel erstellen wir zwei Nullmatrizen, die der Größe der Leinwand entsprechen. Füllen Sie für jedes Rechteck eine dieser Matrizen mit denen, bei denen das Rechteck Platz beansprucht. Dann summieren Sie die Matrizen. Jetzt ist sum(A+B > 0) der Bereich der Vereinigung und sum(A+B > 1) der Bereich der Überlappung. Dieses Beispiel kann leicht auf mehrere Rechtecke verallgemeinert werden.
  18.08.2014 Rose Perrone
  Hier ist etwas, das sich aus meinem Kopf anhört, als könnte es funktionieren:
  Erstellen Sie ein Wörterbuch mit einer Doppeltaste und einer Liste mit Rechteck + booleschen Werten wie folgt:
  Dictionary <Double, List <KeyValuePair <Rechteck, Boolean >>> Rechtecke;
  Suchen Sie für jedes Rechteck in Ihrem Set die entsprechende Liste für die Werte x0 und x1, und fügen Sie der Liste das Rechteck hinzu. Der boolesche Wert ist true für x0 und false für x1. Auf diese Weise haben Sie jetzt eine vollständige Liste aller x-Koordinaten, die jedes Rechteck entweder in die x-Richtung einführt (true) oder belässt (false)
  Schnappen Sie sich alle Schlüssel aus diesem Wörterbuch (alle eindeutigen X-Koordinaten), sortieren Sie sie und durchlaufen Sie sie in der richtigen Reihenfolge. Stellen Sie sicher, dass Sie sowohl den aktuellen X-Wert als auch den nächsten (auch beide) benötigen ). Dadurch erhalten Sie individuelle Rechteckstreifen
  Behalten Sie eine Reihe von Rechtecken bei, die Sie gerade betrachten, die leer sind. Fügen Sie für jeden x-Wert, den Sie in Punkt 3 durchlaufen, das Rechteck mit einem echten Wert hinzu, fügen Sie es der Gruppe hinzu, andernfalls entfernen Sie es.
  Für einen Streifen sortieren Sie die Rechtecke nach ihrer y-Koordinate
  Durchlaufen Sie die Rechtecke des Streifens und zählen Sie sich überlappende Entfernungen (für mich ist noch unklar, wie dies effizient gemacht werden kann).
  Berechnen Sie die Breite der Streifenzeiten, um sich überlappende Entfernungen zu berechnen, um Bereiche zu erhalten
  Beispiel: 5 Rechtecke, übereinander zeichnen, von a bis e:
  Hier ist die Liste der x-Koordinaten:
  Die Liste wäre (wobei jedem v einfach eine Koordinate gegeben wird, die bei 0 beginnt und nach oben geht):
  Jeder Streifen wäre also (Rechtecke von oben nach unten sortiert):
  für jeden Streifen wäre die Überlappung:
  Ich könnte mir vorstellen, dass eine Variation des Sortier-/Eingabe/Verlass-Algorithmus für die Prüfung von oben nach unten ebenfalls möglich ist:
  sortiere die Rechtecke, die wir gerade im Streifen analysieren, von oben nach unten für Rechtecke mit derselben oberen Koordinate, sortiere sie auch nach der unteren Koordinate
  iterieren Sie durch die y-Koordinaten und fügen Sie ein Rechteck bei der Eingabe zum Satz hinzu. Wenn Sie ein Rechteck verlassen, entfernen Sie es aus dem Satz
  wenn der Satz mehr als ein Rechteck hat, haben Sie Überlappungen (und wenn Sie sicherstellen, dass Sie alle Rechtecke mit der gleichen oberen/unteren Koordinate, die Sie gerade betrachten, hinzufügen/entfernen, sind mehrere überlappende Rechtecke kein Problem
  Für den 1-2-Streifen oben würden Sie folgendermaßen iterieren:
  Sie müssten auch keine tatsächliche Menge hier beibehalten, nur die Anzahl der darin enthaltenen Rechtecke, wann immer dies von 1 nach 2 geht, speichern Sie das y, und wann immer es von 2 nach unten geht, berechnen Sie das aktuelle y - y gespeichert und summiert diese Differenz.
  Ich hoffe, das war verständlich, und wie ich sagte, ist dies aus meinem Kopf heraus und in keiner Weise getestet worden.
  29.10.2008 Lasse Vågsæther Karlsen
  Verwenden Sie das Beispiel:
  1) Sammeln Sie alle x-Koordinaten (links und rechts) in einer Liste, sortieren Sie sie und entfernen Sie Duplikate
  2) Sammeln Sie alle y-Koordinaten (sowohl oben als auch unten) in einer Liste, sortieren Sie sie und entfernen Sie Duplikate
  3) Erstellen Sie ein 2D-Array nach Anzahl der Lücken zwischen den eindeutigen x-Koordinaten * Anzahl der Lücken zwischen den eindeutigen y-Koordinaten.
  4) Malen Sie alle Rechtecke in dieses Raster und erhöhen Sie die Anzahl der Zellen, über denen sie auftritt:
  | 1 | 0 0 0
  0 0 | 1 | 1 |
  5) die Summe der Bereiche der Zellen im Gitter, deren Zählwert größer als eins ist, ist der Überlappungsbereich. Um bei spärlichen Anwendungsfällen eine bessere Effizienz zu erzielen, können Sie während des Malens der Rechtecke eine laufende Gesamtsumme der Fläche beibehalten, jedes Mal, wenn Sie eine Zelle von 1 auf 2 verschieben.
  In der Frage werden die Rechtecke als vier Doubles beschrieben. Doppelte enthalten in der Regel Rundungsfehler und können sich in den berechneten Überlappungsbereich einschleichen. Wenn die rechtlichen Koordinaten an endlichen Punkten liegen, sollten Sie eine Ganzzahldarstellung in Betracht ziehen.
  PS mit dem Hardwarebeschleuniger wie in meiner anderen Antwort ist keine schäbige Idee, wenn die Auflösung akzeptabel ist. Es ist auch leicht in viel weniger Code als der oben beschriebene Ansatz zu implementieren. Pferde für Kurse.
  18.11.2008 Will
  Hier ist der Code, den ich für den Gebiets-Sweep-Algorithmus geschrieben habe:
  13.04.2010 extraeee
  Sie können dieses Problem erheblich vereinfachen, wenn Sie jedes Rechteck in kleinere Rechtecke aufteilen. Sammeln Sie alle X- und Y-Koordinaten aller Rechtecke, und diese werden zu Ihren Trennpunkten. Wenn ein Rechteck die Linie kreuzt, teilen Sie es in zwei Teile. Wenn Sie fertig sind, haben Sie eine Liste von Rechtecken, die entweder 0% oder 100% überlappen. Wenn Sie sie sortieren, sollte es leicht sein, die identischen zu finden.
  29.10.2008 Mark Ransom
  Es gibt eine Lösung, die unter dem Link http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html aufgelistet ist, um die Gesamtfläche mehrerer Rechtecke zu ermitteln, die sich überlappen wird nur einmal gezählt.
  Die obige Lösung kann erweitert werden, um nur den überlappten Bereich (und auch diesen nur einmal zu berechnen, selbst wenn der überlappte Bereich von mehreren Rechtecken bedeckt ist) mit horizontalen Sweep-Linien für jedes Paar aufeinanderfolgender vertikaler Sweep-Zeilen.
  Wenn nur die Gesamtfläche ermittelt werden soll, die von allen Rechtecken abgedeckt wird, sind keine horizontalen Sweep-Linien erforderlich, und ein Zusammenfügen aller Rechtecke zwischen zwei vertikalen Sweep-Linien würde die Fläche ergeben.
  Wenn Sie dagegen nur den überlappten Bereich berechnen möchten, werden die horizontalen Sweep-Linien benötigt, um herauszufinden, wie viele Rechtecke zwischen den vertikalen (y1, y2) Sweep-Linien überlappen.
  Hier ist der Arbeitscode für die Lösung, die ich in Java implementiert habe.
  06.01.2016 tick_tack_techie
  Wenn Ihre Rechtecke spärlich sein werden (meistens nicht überlappend), ist es möglicherweise einen Blick auf das rekursive dimensionale Clustering wert. Ansonsten scheint ein Quad-Baum der richtige Weg zu sein (wie auf anderen Postern bereits erwähnt wurde).
  Dies ist ein häufiges Problem bei der Kollisionserkennung in Computerspielen, daher gibt es keinen Mangel an Ressourcen, die Lösungsansätze vorschlagen.
  Hier ist ein schöner Blogbeitrag, der RCD zusammenfasst.
  Hier ist ein Artikel von Dr.Dobbs, der verschiedene Kollisionserkennungsalgorithmen zusammenfasst, die geeignet wären.
  28.10.2008 Oliver Hallam
  In Anbetracht dessen haben wir zwei Rechtecke (A und B) und deren untere linke (x1, y1) und obere rechte (x2, y2) Koordination. Mit dem folgenden Code können Sie den überlappten Bereich in C++ berechnen.
  03.10.2016 user3048546
  Die folgende Antwort sollte die Gesamtfläche nur einmal angeben. Sie kommt aus den vorherigen Antworten, wurde aber jetzt in C # implementiert. Sie funktioniert auch mit Floats (oder doppelt, falls Sie dies benötigen). .
  BEARBEITEN: Das OP hat nach dem überlappenden Bereich gefragt - das ist natürlich sehr einfach:
  und dann lautet die Antwort:
  16.10.2017 ephraim
  Diese Art der Kollisionserkennung wird häufig als AABB (Axis Aligned Bounding Boxes) bezeichnet. Dies ist ein guter Ausgangspunkt für eine google-Suche .
  29.10.2008 grapefrukt
  Ich habe eine andere Lösung als den Sweep-Algorithmus gefunden.
  Da Ihre Rechtecke alle rechteckig platziert sind, bilden die horizontalen und vertikalen Linien der Rechtecke ein rechteckiges unregelmäßiges Gitter. Sie können die Rechtecke in diesem Raster "zeichnen"; Sie können also festlegen, welche Felder des Rasters ausgefüllt werden. Da die Gitterlinien aus den Grenzen der angegebenen Rechtecke gebildet werden, ist ein Feld in diesem Raster immer entweder vollständig leer oder vollständig mit einem Rechteck gefüllt.
  Ich musste das Problem in Java lösen, daher hier meine Lösung: http://Pastebin.com/03mss8yf
  Diese Funktion berechnet den gesamten von den Rechtecken belegten Bereich. Wenn Sie nur an dem überlappenden Teil interessiert sind, müssen Sie den Codeblock zwischen den Zeilen 70 und 72 erweitern. Möglicherweise können Sie einen zweiten Satz verwenden, um zu speichern, welche Gitterfelder mehr als einmal verwendet werden. Ihr Code zwischen Zeile 70 und 72 sollte durch einen Block wie folgt ersetzt werden:
  Die Variable usedLocations2 ist hier vom selben Typ wie usedLocations; es wird der gleiche Punkt konstruiert.
  Komplexitätsberechnungen sind mir nicht wirklich vertraut. Ich weiß also nicht, welche der beiden Lösungen (Sweep oder Grid-Lösung) besser funktioniert.