Bei vielen horizontalen und vertikalen Linien, wie findet man alle Rechtecke, in denen sich ein Unterrechteck befindet?

Question

Ich habe viele horizontale und vertikale Linien, die Rechteck wie in diesem Beispiel bilden.

Gibt es einen Algorithmus oder Code, der jedes Rechteck lokalisieren kann, die nicht ein weiteres Rechteck enthält. Ich meine, das größte Rechteck in diesem Bild ist kein Rechteck, nach dem ich suche, weil es andere Rechtecke enthält.

Die Rechtecke, nach denen ich suche, müssen leer sein. Ich habe eine Liste der Startpunkte und Endpunkte jeder Zeile wie (a, b) bis (c, d). Ich möchte als Ergebnis eine Liste von Rechtecken (x, y, w, h) oder gleichwertig.

Beachten Sie, dass einige Linien Linien haben, die sie im rechten Winkel schneiden, zum Beispiel ist die obere Linie des breitesten Rechtecks ​​in diesem Bild eine einzelne Linie, die eine sich schneidende vertikale Linie nach unten hat.

Answer 1

Sind alle Linien parallel zur x- oder y-Achse? Oder alle Ihre Linien entweder parallel oder senkrecht?

Von dem Beispiel, das Sie gaben, nehme ich an, dass alle Ihre Linien parallel zur x- oder y-Achse sind. In diesem Fall werden Ihre Zeilen [(a, b), (a, d)] oder [(a, b), (c, b)] sein.

In jedem Fall ist die erste Aufgabe, die Ecken zu finden. das sind Punkte, an denen sich zwei senkrechte Linien treffen.

Die zweite Aufgabe besteht darin, Rechtecke zu erkennen. Für jedes Eckenpaar können Sie prüfen, ob sie Rechtecke bilden.

Die dritte Aufgabe besteht darin, herauszufinden, ob ein Rechteck irgendwelche Rechtecke in sich hat.

Für die erste Aufgabe müssen Sie Linien in zwei Sätze trennen: vertikal und horizontal. Danach sortiere einen der Sätze. Ex. Sortiere vertikale Linien nach ihren x-Koordinaten. Dann können Sie alle horizontalen Linien nehmen und eine binäre Suche durchführen, um alle Schnittpunkte zu finden.

Für die zweite Aufgabe, betrachten Sie jedes Paar Ecken und sehen Sie, ob die anderen zwei Ecken existieren. Wenn ja, dann sehen Sie, ob es Linien gibt, die all diese vier Ecken verbinden. Wenn ja, haben Sie ein Rechteck.

Für die dritte Aufgabe, fügen Sie alle Rechtecke in einem Intervallbaum. Danach können Sie prüfen, ob sich zwei Rechtecke überlappen.

Answer 2

Ich denke, eine andere Darstellung wird Ihnen helfen, Ihr Problem zu lösen. Betrachten Sie als Beispiel das große Rechteck (ohne den Block am Ende). Es gibt vier eindeutige x- und y-Koordinaten, sortieren und indizieren sie. Bildlich würde es so aussehen:

Wenn es eine Ecke eines Rechtecks ​​ist auf der Koordinate (x_i, y_j) es wie so in einer Matrix setzen:

__|_1__2__3__4_ 
1 | x x 0 x 
2 | x x 0 0 
3 | 0 x x x 
4 | x x x x 

nun per definitionem ein Rechteck in Realraum ist ein Rechteck auf den Matrixkoordinaten. Zum Beispiel gibt es ein Rechteck bei (3,2) (3,4) (4,4), (4,3), aber es ist kein "Basis" -Rechteck, da es ein Unterrechteck (3,3) (3,4), (4,4), (4,3) enthält. Ein rekursiver Algorithmus ist hier leicht zu erkennen, und für zusätzliche Geschwindigkeit verwenden Sie Memoization, um repetitive Berechnungen zu verhindern.

Answer 3

A sweep-line algorithm ...

Structures erforderlich:

• V = Ein Satz der vertikalen Linien, geordnet nach x-Koordinate.

• H = Eine Menge aller Anfangs- und Endpunkte der horizontalen Linien (und jeder Punkt enthält einen Verweis auf die Linie) und nach x-Koordinate sortiert.

• CH = Ein (zunächst leerer) sortierter (nach y-Koordinate) Satz von aktuellen horizontalen Linien.

• CR = Ein sortierter (nach y-Koordinate) Satz von aktuellen Rechtecke. Diese Rechtecke haben linke, obere und untere Koordinaten, aber noch keine rechte Koordinate. Beachten Sie, dass es in diesem Satz keine Überschneidungen gibt.

Algorithmus:

gleichzeitig bearbeiten V und H von links nach rechts.

Immer wenn ein horizontaler Zeilenanfang auftritt, fügen Sie die Zeile zu CH hinzu.

Immer wenn ein Ende der horizontalen Linie angetroffen wird, entfernen Sie dieses von CH.

Jedes Mal, wenn eine vertikale Linie angetroffen wird:

• Entfernen aus CR alle Rechtecke, die mit der Linie überlappen. Wenn das gesamte Rechteck innerhalb der Linie vollständig enthalten ist, vergleichen Sie seine Größe mit dem bisher besten Rechteck und speichern Sie es gegebenenfalls.

• Prozesse jedes Element in CH iterativ zwischen dem unteren Punkt und dem oberen Punkt der Linie, wie folgt:

  • ein Rechteck Fügen mit dem letzten verarbeiteten Punkt als unten nach Cr-, dem aktuellen Punkt als Spitze und die y-Koordinate der vertikalen Linie als links.

Erledigt.

Hinweis:

Wenn die x-Koordinate der horizontalen Startpunkte oder Endpunkte oder vertikale Linien gleich sind folgende Reihenfolge muss gepflegt werden: verpassen Sie

x of horizontal start < x of vertical line < x of horizontal finish 

Andernfalls Rechtecke.

Answer 4

Diese Art von Fragen werden größtenteils von einigen Standardalgorithmen beantwortet Computational Geometry. Ich kann mir einen vertical sweep line Algorithmus für dieses spezielle Problem vorstellen.

Angenommen, ein Rechteck wird durch ein Paar Punkte (p1, p2) dargestellt, wobei p1 die obere linke Ecke und p2 die untere rechte Ecke ist. Und ein Punkt hat zwei Attribute (kann als p.x und p.y zugegriffen werden).

Hier ist der Algorithmus.

1. Sortieren Sie alle Punktepaare - O(n log n)
2. eine Liste sweep line status genannt initialisieren. Dies wird alle Rechtecke enthalten, die bis jetzt angetroffen werden, das sind alive. Initialisieren Sie auch eine andere Liste namens event queue, die bevorstehende Ereignisse enthält. Diese event queue enthält derzeit Startpunkte aller Rectagles.
3. Verarbeiten Sie die Ereignisse, beginnend mit dem ersten Element in event queue.
   • Wenn das Ereignis ein start point ist, fügt dann dieses Rechteck auf sweep line status (in sortierter Reihenfolge von y-Koordinate) (in O(log n) Zeit) und fügt ihren unteren rechten Punkt zum event queue an der entsprechenden Position (durch die Punkte sortierte) (wieder in O(log n) Zeit). Wenn Sie es zu sweep line status hinzufügen, müssen Sie nur überprüfen, ob dieser Punkt in dem Rechteck liegt gerade darüber in der sweep line status. Wenn es innen liegt, ist dies nicht Ihr Rechteck, andernfalls fügen Sie dieses zu Ihrer Liste der erforderlichen Rechtecke hinzu. Wenn das Ereignis ein Endpunkt ist, entfernen Sie einfach das entsprechende Rechteck aus der sweep line status.

Laufzeit (für n Rechtecke):

• Sortierung nimmt O(n log n).
• Anzahl der Ereignisse = 2 * n = O(n)
• Jedes Ereignis nimmt O(log n) Zeit (für Einfügungen in event queue sowie sweep line status. So insgesamt O(n log n) ist.

Daher O(n log n).

Für Weitere Details finden Sie unter Bentley–Ottmann algorithm Das obige nur eine einfache Modifikation dieser.

EDIT:

Nur realisiert, dass die Eingabe in Bezug auf Liniensegmente ist, aber da sie immer Rechtecke bilden (je nach Frage), kann eine lineare Traversierung für einen Vorprozess sie in die Rechteckform (Punktpaar) konvertieren.