Minimierung der Überlappung in zufälligen Rechtecken
https://stackoverflow.com/questions/2246150
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe eine Reihe möglicherweise überlappender Rechtecke, von zufälliger Größe und Position innerhalb einer festen Ebene. Da diese Rechtecke zufällig sind, überlappen sich einige möglicherweise nicht:
|-----
| | |----|
|----| | |
|----|
Einige können sich nur um eine Ecke überlappen:
|-----| | |--|--| |--|--| | |-----|
Einige können in einem anderen Rechteck enthalten sein:
|----------------| | | | |-----| | | | | | | |-----| | |----------------|
Einige können durch ein anderes Rechteck gehen:
|----------------| | | |--|-------------------| | | | | |--|-------------------| |----------------|
usw.
Ich versuche, einen Algorithmus zu finden, der mir eine Reihe von Rechtecken gibt, die den gleichen Bereich wie der Eingangssatz darstellen, jedoch ohne zu überlappen. Einige Fälle sind offensichtlich - Rechtecke, die in einem größeren Rechteck enthalten sind, können verworfen werden, und Rechtecke, die sich an einer Ecke überlappen, können in drei Rechtecke aufgeteilt werden, ebenso wie Rechtecke, die durch ein anderes Rechteck gehen. Was ich suche, ist ein generischer Algorithmus, der sich mit all diesen Fällen befasst. Es ist mir egal, ob es nicht brillant effizient ist - der Eingangssatz ist ziemlich klein (höchstens 25 Rechtecke)
Es ist einfach, Rechtecke zu finden, die sich überlappen, aber von dort aus wird es schnell schwieriger, insbesondere wenn man bedenkt, dass ein Rechteck mit mehreren anderen Rechtecken überlappen kann.
Das macht meinen Kopf hinein. Irgendwelche Vorschläge?
Aktualisieren:
Ich habe gerade noch eine Sache bemerkt:
Ich kann diesen Algorithmus entweder zum Zeitpunkt der hinzugefügten Rechtecke ausführen, das er nach und nach oder nach allen Rechtecken hinzugefügt wurde. Es kann einfacher sein, dies zu tun, wenn die Rechtecke hinzugefügt werden, da Sie nur ein Rechteck in Betracht ziehen müssen, aber Sie müssen dennoch die Situation berücksichtigen, in der ein einzelnes Rechteck mehrere andere Rechtecke überlappt.
Lösung
Sind die Rechtecke parallel zu den X & Y -Achsen? Ich nehme an.
Sie können versuchen zu verwenden KD-Bäume.
Oder wenn Sie etwas einheimisches und nicht unbedingt effizientes wünschen, können Sie "rechteckig" und dann bei Bedarf Rechtecke zurückführen.
Mit 'Rechteck' Ich meine, du findest zuerst ein größeres Rechteck, in das alle Rechtecke passen (im Grunde das Rechteck, das durch die am wenigsten linke Kante gebildet wird, die rechte Kante, die am wenigsten untere Kante, die größte Oberkante).
Strecken Sie nun alle Ränder der Rechtecke aus, um das große Rechteck zu schneiden. Sie haben jetzt eine "Rechteckung". Grundsätzlich bedeutet dies, dass Sie die vertikalen Kanten und die horizontalen Kanten sortieren und benachbarte Paare für ein kleines Rechteck auswählen. Für jedes kleine Rechteck können Sie nun überprüfen, ob dies Teil des interessanten Bereichs ist oder nicht, und es ablehnen, wenn dies nicht der Fall ist (es ist entweder innen oder vollständig draußen voll).
Jetzt haben Sie eine Liste kleiner Rechtecke (möglicherweise o (n^2), in Ihrem Fall vielleicht ~ 2500), die den Bereich Ihres Interesses ausmachen. Wenn die Zahl für Ihre zukünftige Verarbeitung ausreichend klein genug ist, können Sie diese einfach verwenden oder sie zusammenführen, um die Anzahl der Rechtecke zu verringern.
Um zusammenzuarbeiten, können Sie ein Rechteck in Betracht ziehen und 4 Möglichkeiten für eine Zusammenführung betrachten (angrenzendes Rechteck der gleichen Höhe nach rechts oder links oder angrenzendes Rechteck von gleicher Breite oben oder unten).
Sie könnten eine gewisse Verarbeitung (nicht nur während der Zusammenführung) beschleunigen, indem Sie eine sortierte Liste von Kanten (sowohl horizontal als auch parallel) und möglicherweise einige Hashtables beibehalten.
Andere Tipps
Sehr interessante Frage - Ich denke, es ist am besten, das Problem jeweils ein Paar Rechtecke zu lösen, anstatt 3 oder mehr gleichzeitig zu betrachten. Beginnen Sie damit, diejenigen innerhalb anderer Rechtecke zu verwerfen. Jetzt haben Sie nur 3 Arten von Kreuzungen - Ecküberlappung und überlappen und teilweise überlappend (wobei das Rechteck nicht ganz durchlaufen). Diese erstellen jeweils einen neuen Satz von Rechtecken, oder?
Zahlen Sie Ihre Startrechte von 1 nach N. Beginnend mit dem Rechteck 1 Zyklus durch, bis Sie ein sich überschneidendes Rechteck finden. Erstellen Sie neue Rechtecke. Löschen Sie die beiden sich kreuzenden Rechtecke und fügen Sie die 3 oder mehr neu erstellten Rechtecke zu Ihrem Set hinzu und beginnen Sie erneut.
Das Ergebnis wird eine ganze Reihe nicht überlappender Rechtecke sein. Erzeugt dies die wenigsten Rechtecke? Wahrscheinlich nicht, aber Sie haben nicht angegeben, dass es wichtig war, die Anzahl der Rechtecke zu minimieren. Übernimmt es o (n^2) Zeit? Wahrscheinlich.
Erstellen Sie zunächst den Satz aller "atomaren" Rechtecke in der Komposition, dh Bereiche, die durch die Rechteckkreuzungen gebildet werden und sich nicht selbst unterteilt haben. Jedes tatsächliche Rechteck deckt 1 oder mehr atomare Rechtecke ab. Führen Sie dann einen kombinatorischen Optimierungsalgorithmus aus, z.
Hier eine Illustration des Ansatzes. Sie haben drei Rechtecke (a, b, c). Sie schaffen 5 atomare Regionen (1-5):
+---------+A
| 1 |
| +----+-----+B
| | 2 | 3 |
| | +-+---+C|
| | |4| | |
+----+--+-+ 5 | |
| +-----+ |
+--+-------+
Die Rechtecke decken die atomaren Regionen gemäß dieser Tabelle ab:
A {1,2,4}
B {2,3,4,5}
C {4,5}
Das SetCover -Problem besteht nun darin, eine minimale Teilmenge der Rechtecke {a, b, c} auszuwählen, damit alle atomaren Regionen abgedeckt werden, wenn Sie die von den Rechtecken abgedeckten atomaren Regionen zusammenstellen. Die minimale Lösung ist (offensichtlich)
A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5}
Beachten Sie, dass die Bereiche hier nicht respektular sind, z. B. Bereich 3 eine komplexe Form. Sie können dieses Problem durch den folgenden Ansatz beseitigen: Nehmen Sie alle unterschiedlichen X-Koordinaten der Eckpunkte der ursprünglichen Rechtecke und betrachten sie als X-Koordinaten eines Gitters und tun dasselbe für die Y-Koordinaten. Dann deckt jedes Rechteck eine Reihe von Gitterquadraten ab, die niemals unterteilt sind, dh:
+---------+A -
| 1 |
| +----+-----+B -
| | 2 | 3 |
| | +-+---+C| -
| | |4| | |
+----+--+-+ 5 | | -
| +-----+ | -
+--+-------+ -
| | | | | |
Das gibt Ihnen das folgende 5x5 -Gitter:
AAA A = rectangle A only
A**BB B = rectangle B only
A*#CB * = A and B
BCCB C = rectangles C and B
BBBB # = All
Daraus können Sie die 5 Regionen leicht extrahieren; Tatsächlich wurden sie bereits markiert :) (a, b, c,*,#)
Wenn Sie keine Einschränkungen für die Anzahl der Rechtecke haben, die Ihr Algorithmus erzeugen sollte, können Sie in Ihrer Behandlung definitiv vorschnell sein!
1. einfachste Lösung aller Zeiten
Erstellen Sie einen Satz aller Quadrate (von Bereich 1), die von den Rechtecken des Eingangssatzes bedeckt sind. Ein Quadrat ist ein Rechteck ... da bist du!
2. Minimalistische Lösung?
Okay, das war Hautausschlag, aber ich glaube nicht, dass Sie sich um den Eingangssatz sorgen sollten. Ihr Problem ist in der Tat anders:
Nehmen Sie einen zusammenhängenden Bereich mit einer komplexen Form und versuchen Sie, ihn genau mit Rechtecken abzudecken, um ihre Anzahl zu minimieren und sich nicht zu überlappen.
Natürlich ist Ihr Gebiet möglicherweise nicht angrenzend, bedeutet jedoch nur, dass Sie mehrere zusammenhängende Bereiche haben, an denen Sie unabhängig arbeiten können.
Jetzt gebe ich frei zu, dass ich die beste Lösung für dieses Problem nicht kenne, es gibt verschiedene Ansätze, die ich mir vorstellen kann, und ich kenne ihre Leistungen oder ihre Ergebnisse nicht. KD-Tree Sollte eine Lösung ergeben, wissen Sie nicht, ob es der minimalistische ist!
Wenn Sie noch keine Rechtecke haben, können Sie es aus anderen Art und Weise nähern - Beginnen Sie mit einem großen Rechteck und unterteilen Sie es, bis Sie ein Satz haben, mit dem Sie arbeiten können -, mit dem Sie keine Überschneidungen haben.
Beginnen Sie mit einem ganzen Rechteck
--------
| |
| |
| |
| |
| |
--------
Spalten Sie an einem zufälligen Punkt auf und speichern Sie die beiden Rechtecke.
--------
| |
|------|
| |
| |
| |
--------
Teilen Sie ein zufälliges Rechteck an einem zufälligen Punkt auf
--------
| |
|------|
| | |
| | |
| | |
--------
wiederholen . . .
--------
| |
|------|
| | |
| |----|
| | |
--------
Stoppen Sie, wenn Sie die erforderliche Anzahl von Rechtecken haben.
Sie könnten dies zu einer Art „Zufälligkeit“ erzeugen, die Sie möchten, indem Sie das Rechteck ausgewählt haben, das Sie jedes Mal aufteilen werden, wenn ETCC
