Ich suche nach einem Algorithmus, der bestimmt, ob ein neues Rechteck vollständig von einer Menge vorhandener Rechtecke überdeckt wird. Eine andere Möglichkeit, die Frage zu stellen, ist, ob das neue Rechteck vollständig mit der Fläche existiert, die von den vorhandenen Rechtecken abgedeckt wird?
Es scheint viele Algorithmen zu geben, um die Rechtecküberlappung zu bestimmen, aber ich kann wirklich nichts finden, das genau dieses Problem löst.
Die Rechtecke werden mit x, y Koordinaten dargestellt. Dieses Problem betrifft die geografische Zuordnung.
Bearbeiten - aus dem Kommentar des OP:
Die Rechtecke sind auf der X / Y-Achse ausgerichtet
Wenn die Rechtecke alle denselben Winkel haben; dann könnte das Folgende effizienter und einfacher zu programmieren sein:
Bestimmen Sie für jede y-Koordinate, welche Rechtecke diese y-Koordinate abdecken (Sie müssen dies nur für y-Koordinaten tun, bei denen sich die Abdeckung ändert; d. h., die der oberen oder unteren Grenze eines Rechtecks entsprechen). Sobald Sie das wissen, lösen Sie das Problem für jede solche y-Koordinate (d. H. Prüfen Sie, ob alle x-Werte durch die Rechtecke abgedeckt sind, die für diese Y-Koordinate "aktiv" sind).
Edit: Ich denke, das ist O (n ^ 2 log (n) ^ 2) Komplexität, da zwei Arten die harte Arbeit sind, die Sie tun müssen
R-Struktur kann nützlich sein. Wenn sich Rechtecke rotieren lassen, können Sie sie in umschließende Rechtecke einschließen.
Ich habe in der Vergangenheit etwas ähnliches gemacht. Die Idee war, das neue Rechteck mit jedem der vorhandenen (eins nach dem anderen) zu vergleichen
Wenn es einen Schnittpunkt gibt, verwerfen Sie ihn (den geschnittenen Teil) und fügen Sie einem Rechteck-Array nicht aufgedeckte Segmente hinzu
Als nächstes suchen Sie nach dem Schnittpunkt zwischen den neuen Segmenten und anderen vorhandenen (noch nicht markierten) Rechtecken.
Führen Sie den Algorithmus rekursiv aus, um die Schnittpunkte zu verwerfen und nur die unbedeckten Teile zu belassen.
am Ende, wenn es keine Rechtecke im Array gibt, haben Sie eine vollständige Überlappung
Wenn es noch einige Rechtecke im Array gibt, ist die Überlappung nicht voll, da noch Teile übrig sind.
hoffe das hilft
Ich kann versuchen, meinen Code zu finden, wenn Sie danach suchen. Ich denke, es ist in C #
Eine andere Idee besteht darin, alle vorhandenen Rechtecke in ein Polygon umzuwandeln und dann zu prüfen, ob sich ein neues Rechteck innerhalb des Polygons befindet. Ich würde dies jedoch nicht empfehlen, wenn Sie keine Sprache (oder ein Framework) verwenden Polygone.
Versuchen Sie es
Quellrechteck: X0, Y0, Breite, Höhe
// Grundsätzlich Kanten vergleichen
falls (((X0 & gt; = xi) & amp; & amp; (X0 + Breite & lt; = Xi)) & amp; & amp; ((Y0 & gt; = Yi) & amp; & amp; (Y0 + Höhe & lt; = Yi)) { // betrachte das Rechteck } sonst { // verwerfen }
Hier ist mein Code, wie Sie angefordert haben:
Die erste Methode "subtrahiert" (gibt unbedeckte Teile zurück) von 2 Rechtecken.
Die zweite Methode subtrahiert eine Liste von Rechtecken vom Basisrechteck.
in Ihrer Fallliste enthält vorhandene Rechtecke, und das neue ist Basis
Um zu überprüfen, ob es eine vollständige Schnittmenge gibt, sollte die von der zweiten Methode zurückgegebene Liste keine Elemente enthalten.
%Vor% Sie können den Algorithmus verwenden, der zur Berechnung des Vereinigungsbereichs von Rechtecken verwendet wird. Wie Sie überprüfen möchten, ob das Rechteck a durch Rechtecke B = {b_1, b_2, ...,} abgedeckt ist. Zuerst berechnen Sie den Union-Bereich der Rechtecke in B, wir erhalten als Wert den Bereich br>
Dann berechnen Sie den Union-Bereich von Rechtecken in B + {a}, wir erhalten Area_2 als Wert.
Wenn also Bereich_1 == Bereich_2 ist, dann sind Sie sicher, dass Rechteck a von Rechtecken B bedeckt ist. Andernfalls ist die Antwort falsch.
Das Hauptproblem ist also, wie Union-Bereich von Rechtecken zu berechnen. Dieses Problem kann durch einen existierenden exzellenten Algorithmus gelöst werden. Dieser Algorithmus kann kurz eingeführt werden, um zuerst den Wert von Punkten von Rechtecken zu diskretisieren und dann den Segmentierungsbaum zu verwenden, um die Berechnung von Bereichen jedes Blocks zu beschleunigen.