Gegeben ein Satz Rechtecke, die als Tupel dargestellt werden (xmin, xmax, ymin, ymax) wobei xmin und xmax die linken und rechten Kanten sind und ymin und ymax die unteren bzw. oberen Kanten sind - gibt es ein Paar von überlappenden Rechtecken in der Menge?
Ein direkter Ansatz besteht darin, jedes Paar Rechtecke auf Überlappung zu vergleichen, aber das ist O(n^2) - es sollte möglich sein, es besser zu machen.
Aktualisierung: xmin , xmax , ymin , ymax sind ganze Zahlen . Eine Bedingung für die Überlappung von Rechteck 1 und Rechteck 2 ist also xmin_2 <= xmax_1 AND xmax_2 >= xmin_1 ; ähnlich für die Y-Koordinaten.
Wenn ein Rechteck ein anderes enthält, wird das Paar als überlappend betrachtet.
Sie können es in O (N log N) folgendermaßen machen:
Zuerst "quetschen" Sie Ihre y-Koordinaten. Sortieren Sie also alle y-Koordinaten (Ober- und Unterseiten) in einem Array und ersetzen Sie die Koordinaten in der Beschreibung des Rechtecks durch den Index in einem sortierten Array. Nun haben Sie alle y's ganze Zahlen von 0 bis 2n-1, und die Antwort auf Ihr Problem hat sich nicht geändert (falls Sie gleiche y's haben, siehe unten).
Jetzt können Sie die Ebene in 2n-1 Streifen teilen, jede Einheitshöhe, und jedes Rechteck überspannt mehrere davon. Bereiten Sie einen Segmentbaum für diese Streifen vor. (Siehe diesen Link für die Segmentbaumübersicht.)
Sortieren Sie anschließend alle fraglichen X-Koordinaten (linke und rechte Begrenzung) im selben Array, wobei Sie für jede Koordinate die Information beibehalten, aus welchem Rechteck sie kommt und ob dies eine linke oder rechte Grenze ist.
Gehen Sie dann durch diese Liste und pflegen Sie währenddessen die Liste aller Rechtecke, die momentan "aktiv" sind, dh für die Sie eine linke, aber noch keine rechte Grenze gesehen haben.
Genauer gesagt müssen Sie in Ihrem Segmentbaum für jeden Streifen festlegen, wie viele aktive Rechtecke ihn abdecken. Wenn Sie auf eine linke Grenze stoßen, müssen Sie 1 für alle Streifen zwischen dem unteren und oberen Rand eines entsprechenden Rechtecks hinzufügen. Wenn Sie auf eine rechte Grenze stoßen, müssen Sie eine davon abziehen. Sowohl Addition als auch Subtraktion können in O (log N) unter Verwendung der Massenaktualisierung (Lazy Propagation) des Segmentbaums durchgeführt werden.
Und um tatsächlich zu prüfen, was Sie brauchen, wenn Sie eine linke Grenze treffen, bevor Sie 1 hinzufügen, prüfen Sie, ob es mindestens einen Streifen zwischen unten und oben gibt, der eine Nicht-Null-Abdeckung aufweist. Dies kann in O (log N) durchgeführt werden, indem eine Abfrage nach einem Intervall im Segmentbaum durchgeführt wird. Wenn die Summe in diesem Intervall größer als 0 ist, haben Sie eine Kreuzung.
%Vor%Sie sollten es sorgfältig umsetzen, indem Sie berücksichtigen, ob Sie eine Berührung für eine Kreuzung halten oder nicht, und dies wird Ihre Behandlung gleicher Zahlen beeinflussen. Wenn Sie Berührungen als Schnittpunkt betrachten, müssen Sie beim Sortieren von Y-Werten sicherstellen, dass von allen Punkten mit gleichen Koordinaten alle Oberseiten nach allen Unterseiten verlaufen und bei der Sortierung von X-Werten die gleiche von allen gleichwertigen x-Werten Linke gehen vor allen Rechten.
Warum probierst du keinen Plane-Sweep-Algorithmus? Plane Sweep ist ein Designparadigma, das in der Computergestützten Geometrie weit verbreitet ist. Es hat also den Vorteil, dass es gut untersucht ist und viele Dokumentationen online verfügbar sind. Schauen Sie sich das an. Das Liniensegmentschnittproblem sollte Ihnen einige Ideen geben, auch den Bereich der Vereinigung von Rechtecken.
Lesen Sie über Bentley-Ottman Algorithmus für Linienschnitt, das Problem ist sehr ähnlich deins und es hat O ((n + k) logn) wobei k die Anzahl der Schnittpunkte ist, da Ihre Rechtecke jedoch parallel zur x- und y-Achse sind, ist es viel einfacher, so dass Sie Bentley-Ottman zum Ausführen modifizieren können in O (nlogn + k), da Sie den Event-Heap nicht aktualisieren müssen, da alle Schnittpunkte nach dem Besuch des Rechtecks erkannt werden können und die Reihenfolge der Sweep-Zeilen nicht geändert wird, sodass die Ereignisse nicht beibehalten werden müssen. Um alle sich schneidenden Rechtecke mit dem neuen Rechteck zu erhalten, empfehle ich, einen Bereichsbaum auf dem ymin und ymax für jedes Rechteck zu verwenden gebe dir alle Punkte, die in dem Intervall liegen, das durch ymin und ymax des neuen Rechtecks definiert ist, und somit die Rechtecke, die es schneiden.
Wenn Sie mehr Details benötigen, sollten Sie sich das zweite Kapitel von M. de Berg, et. al Algorithmisches Geometrie-Buch . Werfen Sie auch einen Blick auf dieses Papier , Sie zeigen, wie man alle Überschneidungen zwischen konvexen Polygonen in O (nlogn + k) findet, es könnte sich als einfacher erweisen als meine obige Anregung, da alle Datenstrukturen dort erklärt werden und Ihre Rechtecke konvex sind, eine sehr gute Sache in diesem Fall.
>Sie können es besser machen, indem Sie eine neue Liste von Rechtecken erstellen, die sich nicht überschneiden. Nehmen Sie aus der Menge der Rechtecke den ersten und fügen Sie ihn zur Liste hinzu. Es überschneidet sich offensichtlich nicht mit anderen, weil es der einzige in der Liste ist. Nimm den nächsten aus dem Set und sieh nach, ob er sich mit dem ersten in der Liste überschneidet. Wenn dies der Fall ist, true zurück; Andernfalls fügen Sie es zur Liste hinzu. Wiederholen Sie dies für alle Rechtecke in der Gruppe.
Jedes Mal vergleichen Sie das Rechteck r mit den Rechtecken r-1 in der Liste. Dies kann in O(n*(n-1)/2) oder O((n^2-n)/2) erfolgen. Sie können diesen Algorithmus sogar auf den ursprünglichen Satz anwenden, ohne eine neue Liste erstellen zu müssen.
Tags und Links algorithm