Füllen Sie beliebige 2D-Form mit gegebenen Satz von Rechtecken
Habe ich eine Reihe von Rechtecken und beliebiger Form in 2D-Raum. Die Form ist nicht notwendig, ein polygon (es kann ein Kreis), und die Rechtecke haben unterschiedliche breiten und Höhen. Die Aufgabe ist die Angleichung der Form mit Rechtecken so nah wie möglich. Ich kann nicht ändern, Rechtecke Abmessungen, aber die rotation ist erlaubt.
Es klingt sehr ähnlich wie Verpackung problem und Belag problem, aber die Abdeckung Fläche ist nicht rechteckig...
Ich denke, es ist NP-problem, und ich bin mir ziemlich sicher, sollte es einige Papiere, die zeigen, dass gute Heuristiken, um es zu lösen, aber ich weiß nicht, was zu google? Wo sollte ich anfangen?
Update: Eine Idee kam in mein Verstand, aber ich bin mir nicht sicher, ob es sich lohnt zu untersuchen. Was ist, wenn wir Bedenken, umschließende Form, wie eine physische Form mit Wasser gefüllt. Jedes Rechteck ist, als ein positiv geladenes Teilchen mit der Größe. Legen Sie nun das kleinste Rechteck, um es. Fallen dann die nächste Größe bei zufälligen Punkt. Wenn die Rechtecke auch schließen Sie sich gegenseitig abstoßen. Halten Sie das hinzufügen, Rechtecke, bis alle verwendet werden. Könnte diese Methode funktionieren?
- Sind Sie versuchen, zu packen, so dicht wie möglich? Oder annähernd der Form so gut wie möglich? Gibt es eine mathematische Funktion, die Sie versuchen zu optimieren sind, oder ist es mehr ästhetik?
- Über diese berechnet Rechteck-Methode, ist es vielleicht nicht unbedingt die optimale Konfiguration, weil wir uns mit Randomisierung fallen Sie auf den ersten.
- Was ist die Priorität - Ablaufverfolgung die Grenze oder füllen Sie die Form? Ich meine, es ist okay, wenn sich die Rechtecke trace die Grenze perfekt, aber lassen Sie ein Loch in der Mitte irgendwo???
- Welche Lösung hast du am Ende mit?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ich denke, Sie Aussehen könnte, für die Verpackung und die automatische layout-Erzeugung algorithmen. Automatische VLSI-layout-generation algorithmen benötigen könnten, ähnliche Dinge, wie textile layout-Fragen...
Diesem Papier Hegedüs: Algorithmen zur Abdeckung der Polygone durch Rechtecke scheint-Adresse ein ähnliches problem. Und da dieses Papier ist von 1982, es könnte interessant sein zu schauen, die die Papiere, die zitieren Sie diese ein. Darüber hinaus dieses treffen zu sein scheint Erörterung wissenschaftlicher Probleme im Zusammenhang mit diesem, so könnte ein Ausgangspunkt für Stichworte oder Namen, die Forschung in diese Idee.
Ich weiß nicht, ob das computational geometry research hat die algorithmen für Ihren spezifischen problem, oder wenn diese algorithmen sind einfach/praktisch genug, um zu implementieren. Hier ist, wie würde ich Vorgehen, wenn ich musste es tun, ohne in der Lage zu schauen bisherigen Arbeit. Dies ist nur eine Richtung, bei weitem nicht die Lösung...
Formuliert als Optimierungsproblem. Sie haben diskrete Variablen, die Rechtecke, die Sie auswählen (ja oder Nein) und kontinuierliche Variablen (Lage und Orientierung der Dreiecke). Jetzt können Sie zwei unabhängige Optimierungen: diskrete Optimierung, wählt die Rechtecke; und eine kontinuierliche Optimierung für die Lage und Orientierung einmal Rechtecke gegeben sind. Verschachteln Sie diese beiden Optimierungen. Natürlich liegt die Schwierigkeit in der Formulierung von Optimierungen und die Gestaltung Ihrer Fehler von Energie, so dass Sie nicht stecken bleiben in einer seltsamen Konfigurationen (lokale minima). Ich würde versuchen, um die kontinuierliche als least-squares problem, so dass ich verwenden können, standard-Optimierungen Bibliotheken.
Ich denke, das problem ist für die Lösung mit genetischem Algorithmus und/oder evolutionäre Strategie Algorithmus. Ich habe getan, ähnliche Verpackung Problems mit Hilfe von evolutionären Strategie-Algorithmus in irgendeiner Form. Check this out in meinem blog.
Also, wenn Sie verwenden diese Vorgehensweise Kodieren, in den Chromosomen-box:
Dann versuchen, zu minimieren, wie fitness-Funktion-
Wahl der GEWICHTE w1,w2,w3 wie beeinflussen Bedeutung von Faktoren. Wenn genetische Algorithmus findet eine teilweise Lösung - entfernen Sie den Boxen, die immer noch überschneidungen zusammen oder sind aus der Form - und haben Sie mindestens den gesetzlichen (aber nicht notwendig optimale) Lösung.
Glück in diesem interessanten problem !
Ist es NP-schwer, ja und da hat es hi-tech-Anwendung, die einigermaßen efficients Ungefähre Strategien sind auch nicht in Patente, geschweige denn Papiere veröffentlicht.
Das beste, was Sie tun können, mit einem begrenzten budget zu beginnen ist durch die Begrenzung des Problems. Davon ausgehen, dass alle Rechtecke sind genau die gleichen, davon Ausgehen, dass alle Rechtecke, die binären Unterteilungen von Ihrem standard-Rechteck sind auch zulässig, da Sie effizient pre-pack Sie an Ihre core-division. Für extra-Punkte Sie können auch mehrere Feste Schemata für die Verklebung von Kern-Rechtecke decken ein paar größere Formen mit deutlich unterschiedlichen Anteilen. Angenommen, Sie ändern können Abmessungen der standard-Rechteck - /Zelle, solange der rest (pre-Verpackung und kleben schema) bleibt gleich, das gibt Sie Parameter, um zu entscheiden, Ungefähre Größe der core-Rechteck basiert auf Rechtecken, die Sie gegeben sind.
Jetzt können Sie spielen mit Seitenverhältnissen zur Angleichung der Fehler so begrenzten system garantieren könnten. Für die ersten Iterationen davon ausgehen, dass Sie es können 50% der Fehler mit einem einfachen sub-division-schema und ändern Sie dann-schema zu reduzieren, den Fehler aber ohne Erhöhung asymptotische Komplexität von pre-packing. Am Ende des Tages sind Sie immer nur der Zuordnung gegeben, Rechtecke, um Ihre pre-berechnet und jetzt korrigiert Netz-und Binär-sub-Divisionen - das bedeutet, Sie sind nicht versuchen zu tun, ein layout oder backtrack überhaupt - Sie sind immer glücklich, mit dem ersten annähernd passen in das raster.
Arbeit auf die Definition von Klassen von Rechtecken, die packen gut mit Ihrem schema - das ist wieder einmal halten den gesamten Prozess invertiert, Sie werden nie versuchen, eigentlich fit, was Sie gegeben sind - Sie definieren, was Sie haben gegeben werden, um die fir-es gut - dann Werft den rest als Fehler, da es Annäherung.
Dann können Sie versuchen, etwas mehr zu tun, aber nicht viel mehr - alle schlüpfen in backtracking oder nageln beliebig kleine Fehler und es ist exponentiell.
Wenn Sie an einer Forschungseinrichtung und einige supercomputer-Zeit - ausführen erschöpfende Suche mit pathologischen mischt es nur um zu sehen, wie die optimale Verpackung Aussehen kann und um zu sehen, ob man ableiten kann, ein paar mehr sub-division-schemas und/oder Klassen von Rechteck-sets.
Das sollte reichen für die ersten 2 Jahre oder Forschung 🙂