Auf der Suche nach einem nicht "brute force" - Algorithmus zum entfernen von sich überschneidenden Bereichen eine Sammlung von Rects

Question

Ich habe eine n-size-Kollektion von Rects, von denen die meisten sich überschneiden.Ich möchte zu entfernen, die Kreuzungen und reduzieren die schneidende Rects in kleinere und nicht-schneidende rects.

Ich könnte leicht brute-force-Lösung, aber ich bin auf der Suche nach einem effizienten Algorithmus.

Hier ist eine Visualisierung:

Original:

Bearbeitet:

Im Idealfall ist die Signatur der Methode würde wie folgt Aussehen:

public static List<RectF> resolveIntersection(List<RectF> rects);

die Ausgabe wäre größer oder gleich der Eingang, wo die Ausgabe löst die oben genannten visuellen Darstellung.

Answer 1

dies ist ein problem, das ich gelöst in der Vergangenheit.Die erste Sache, die es zu Sortieren, die Rechtecke mit der x-oder y-Wert von einem der Ränder.Lets sagen, dass Sie, um in die y-Richtung, und verwenden Sie den oberen Rand.Das oberste Rechteck in Ihrem Beispiel ist in der ersten Reihenfolge sortiert.Für jedes Rechteck, das Sie wissen, seine Größe in der y-Richtung.

Nun, für jeden Eintrag (call it der der aktuelle Eintrag, es entspricht einem Rechteck)in der sortierten Liste, die Sie suchen vorwärts durch die Liste, bis Sie einen Eintrag größer als der aktuelle Eintrag + die entsprechende Rechteck Größe.(nenne es das stoppen von entry)

Alle Einträge in der sortierten Liste zwischen der aktuellen Eingabe und das stoppen der Eintrag möglichen Kreuzungen.Einfach überprüfen, ob die Rechtecke, die x-Bereiche überschneiden.

Bei der Auswahl Sortieren in der x-oder y-Richtung, es wird besser sein, wählen Sie die dimension, die größer ist, als dies bedeutet, dass weniger Kreuzung im Durchschnitt also weniger Kontrolle.

Hier ist ein Beispiel.Rechtecke sind definiert als R(x1,x2,y1,y2) wobei x1 der linken Seite, x2 rechten Seite, y1 ist top und y2 ist unten

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)

Sortieren nach y1 zu geben

#              y1  size
rectangle 1     0   4
rectangle 3     2   3
rectangle 4     3   4
rectangle 2     6   2
rectangle 5     9   6

so, Rechteck-1 y1 + size = 0 + 4 = 4 impliziert wird es möglicherweise intersect-rectangle 3 (y1-Wert = 3 < 4) und Rechteck 4 (y1-Wert = 3 < 4) aber nicht Rechteck 2 (y1-Wert = 6 > 4)...keine Notwendigkeit, zu überprüfen rectangels in der Liste nach 2

Rechteck 3 y2 + size = 2 + 3 = 5 was bedeutet es möglicherweise intersect-rectangle-4 (y1-Wert = 3 < 5) aber nicht recatngle 2 (y1-Wert = 6 > 5) keine Notwendigkeit zu überprüfen rectangels in der Liste nach 2

Rechteck 4 y2 + Größe = 3 + 4 = 7 implizieren, wird es möglicherweise intersect-rectangle 2 (y1-Wert = 6 < 7) aber nicht recatngle 5 (y1-Wert = 9 > 7)

Natürlich, mit einer großen Anzahl von Rechtecken, die Sie in der Regel nur zu überprüfen einen Bruchteil der möglichen Paare zur Kreuzung.

Answer 2

Sweepline -Algoithmen sind gut darin, Kreuzungen in 2D -Universen zu verarbeiten. Ich meine, sollten Sie eine horizontale Linie in Betracht ziehen, die sich von einer Rechteckkante bis zur nächsten Rechteckkante nach unten bewegt. Die Linie trifft eine Reihe von Rechtecken und bildet die sogenannten aktiven Listen. Die aktive Liste wird bei jedem Schritt aktualisiert.

Durch die Untersuchung der Abszisse entlang der horizontalen Linie können Sie die Überlappungen erkennen.

Eine sorgfältige Untersuchung aller Konfigurationen sollte es Ihnen ermöglichen, die Rechtecke so aufzuteilen, wie Sie es in einem einzigen Sweep mit geringerer Komplexität als Brute -Kraft gewünscht haben (näher bei 1,5 als n^2).

Answer 3

Was Sie dekriegen, ist das Packungsproblem, schauen Sie sich an Wikipedia

es bezieht sich auf Dies Artikel, der einen Algorithmus zum Verpacken von Rechtecken in Rechtecken beschreibt

Dies ist aus dem Artikel:

Dieser Artikel beschreibt einen schnellen Algorithmus, um eine Reihe von Rechtecken unterschiedlicher Breiten und Höhen in ein einzelnes umschließendes Rechteck zu packen, ohne dass sich überlappt und auf eine Weise die Menge an verschwendetem Raum im umschließenden Rechtecke minimiert.