2D-Formen effizient in ein Rechteck platzieren. Wie man es angehen kann?
Ich habe in den sieben Internetnetzen weit und breit gesucht und habe nichts erreicht. Das, was ich am meisten benötige, scheint Das Problem mit dem Schnittmaterial , nur in 2D (was für Wikipedia nicht enttäuschend ist) geben Sie irgendwelche Richtungen an, wie man das löst). Ein anderes Doppelgänger-Problem wäre UV-Entpacken . Es gibt Lösungen, aber nur solche, die Sie von Add-Ons auf verschiedenen 3D-Software erhalten.
Das kurze Wort kurz schneiden - was ich will, ist folgendes: Bei einem Rechteck bekannter Breite und Höhe muss ich herausfinden, wie viele Formen (Polygone) bekannter Größe (die beliebig rotiert werden können) hineinpassen kann dieses Rechteck.
Zum Beispiel könnte ich ein T-förmiges Stück wählen und im selben Rechteck könnte ich beides auf effiziente Weise verpacken, was zu 4 Formen pro Rechteck führt.
sowie Tiling sie basierend auf ihren Bounding-Boxen, Fall, in dem ich nur 3 passen konnte
Aber natürlich ist dies nur ein Beispiel ... und ich denke nicht, dass es viel nützen würde, diesen speziellen Fall zu lösen. Die einzigen Ansätze, die ich mir jetzt vorstellen kann, sind entweder die Zurückverfolgung ihrer Komplexität oder die Lösung nur bestimmter Fälle dieses Problems. Also ... irgendwelche Ideen?
2 Antworten
beachte, was die andere Antwort gesagt hat, indem du die t's in ein Quadrat platzierst, aber anstatt es einfach als ein Quadrat zu belassen, setze die Formen in eine Liste. Verwenden Sie dann True und False, um die verschachtelte Liste als die Form zu füllen, d. H. [[True, True, True], [False, True, False]] für Ihre T-Form. Verwenden Sie dann eine Funktion, um die Formen auf dem Raster zu platzieren. Um die Ergebnisse zu optimieren, erstellen Sie einen Tracker, der darauf achtet, wie viele False in einer neuen Form sich mit den bereits vorhandenen Werten aus früheren Shapes überschneiden. Die Funktion platziert die Form an der Stelle mit den meisten Überlappungen. Es muss Modifikationen geben, um höhere und höhere Optimierungen zu erzeugen, aber das ist die allgemeine Prämisse, nach der Sie suchen.
Irgendjemand für ein Spiel von Tetris (eine Teilmenge deines Problems)?
Dies wird als Verpackungsproblem bezeichnet. Ohne zu wissen, welchen Formen Sie im Voraus begegnen werden, kann es sehr schwierig oder gar unmöglich sein, einen Algorithmus zu finden, der Ihnen die beste Antwort gibt. Mehr als wahrscheinlich, es sei denn, Ihre Polygone sind "nette" Polygone (Kreise, Quadrate, gleichseitige Dreiecke, etc.), müssen Sie sich wahrscheinlich mit einer Heuristik begnügen, die Ihnen meistens die ungefähre Lösung gibt.
Eine allgemeine Heuristik (obwohl sie nicht optimal ist, abhängig von der Form des Eingabe-Polygons) wäre, das Problem zu vereinfachen, indem Sie ein Rechteck um das Polygon ziehen, so dass das Rechteck gerade groß genug wäre, um das Polygon abzudecken. (Als Beispiel im Diagramm unten zeichnen wir ein rotes Rechteck um ein blaues Polygon.)
Sobald wir das getan haben, können wir das Rechteck nehmen und versuchen, so viele von diesem Rechteck wie möglich in das große Rechteck zu passen. Dies vereinfacht das Problem in einem Rechteck-Verpackungsproblem, das leichter zu lösen ist und den Kopf einwickelt. Ein Beispiel für einen Algorithmus hierfür ist der folgende Link:
>Nun ist diese Heuristik offensichtlich nicht optimal, wenn das fragliche Polygon nicht annähernd dieselbe Form wie ein Rechteck hat, aber es gibt Ihnen eine minimale Basislinie, mit der Sie arbeiten können, besonders wenn Sie nicht viel wissen, was Sie tun Das Polygon wird so aussehen (oder es gibt eine hohe Varianz in dem, wie das Polygon aussehen wird). Mit diesem Algorithmus würde ein großes Rechteck wie folgt gefüllt:
Hier ist das gleiche Bild ohne die Zwischenrechtecke:
Für den Fall dieser T-förmigen Polygone ist die Heuristik nicht die beste, die sie sein könnte (in der Tat könnte es fast ein Worst-Case-Szenario für diese vorgeschlagene Annäherung sein), aber sie würde sehr gut für andere Arten von Polygonen funktionieren .
Tags und Links algorithm 2d uv-mapping texture-packing