Welcher Algorithmus kann verwendet werden, um Rechtecke unterschiedlicher Größe auf optimale Weise in das kleinstmögliche Rechteck zu packen?

273

Ich habe ein paar rechteckige Objekte, die ich auf kleinstem Raum einpacken muss (die Abmessungen dieses Raums sollten Zweierpotenzen sein).

Mir sind verschiedene Packalgorithmen bekannt, mit denen die Elemente so gut wie möglich in einen bestimmten Raum gepackt werden. In diesem Fall muss der Algorithmus jedoch auch herausfinden, wie groß dieser Raum sein sollte.

Angenommen, ich habe die folgenden Rechtecke

  • 128 * 32
  • 128 * 64
  • 64 * 32
  • 64 * 32

Sie können in einen 128 * 128-Raum gepackt werden

 _________________
| 128 * 32 |
| ________________ |
| 128 * 64 |
| |
| |
| ________________ |
| 64 * 32 | 64 * 32 |
| _______ | ________ |

Wenn es jedoch auch eine 160 * 32 und eine 64 * 64 gäbe, würde sie 256 * 128 Speicherplatz benötigen

 ________________________________
| 128 * 32 | 64 * 64 | 64 * 32 |
| ________________ | | _______ |
| 128 * 64 | | 64 * 32 |
| | _______ | _______ |
| | |
| ________________ | ___ |
| 160 * 32 | |
| ____________________ | ___________ |

Welche Algorithmen können eine Reihe von Rechtecken packen und die erforderliche Größe für den Container bestimmen (mit einer Potenz von 2 und innerhalb einer bestimmten maximalen Größe für jede Dimension)?

Fire Lancer
quelle
6
Ist die zweite Lösung nicht nicht optimal? Sollte es nicht 128 mal 224 sein?
Mantas Vidutis
"Die Dimensionen dieses Raums sollten Zweierpotenzen sein." Es macht also keinen Unterschied, denn was dies war / ist, denn ich kann nicht davon ausgehen, dass die Nicht-Zweierpotenz bedingungslos von der zugrunde liegenden Hardware unterstützt wird.
Fire Lancer
2
Wie auch immer, es hat den Algorithmus am Ende einfacher gemacht (versuchen Sie, alles in 32x32 zu passen, wenn nicht, dann versuchen Sie es mit 64x32, dann 64x64, 128x64 usw.) :)
Fire Lancer
Ich habe hier eine Art von Brute-Force-Lösung veröffentlicht. Stackoverflow.com/a/47698424/1641247
Sean

Antworten:

67

Die schnelle und schmutzige First-Pass-Lösung ist immer eine großartige Lösung, zum Vergleich, wenn nichts anderes.

Gierige Platzierung von groß nach klein.

Legen Sie das größte verbleibende Rechteck in Ihren gepackten Bereich. Wenn es nirgendwo passt, platzieren Sie es an einem Ort, der den Packbereich so wenig wie möglich erweitert. Wiederholen, bis Sie mit dem kleinsten Rechteck fertig sind.

Es ist überhaupt nicht perfekt, aber es ist einfach und eine schöne Grundlinie. Es würde Ihr ursprüngliches Beispiel immer noch perfekt verpacken und Ihnen auch für das zweite eine gleichwertige Antwort geben.

SPWorley
quelle
1
Ich habe gerade mit so etwas auf einem Stück Papier gespielt, sieht jetzt in den meisten Fällen ziemlich optimal aus, auch ohne die Rechtecke oder irgendetwas zu drehen
Fire Lancer
1
Ich habe es implementiert und eine Reihe von Testdaten durchlaufen, scheint einen ziemlich guten Job zu machen und nur ein wenig verschwendete Daten zu hinterlassen. Jetzt muss ich nur noch meine Implementierung umschreiben, um effizienter zu sein als eine lineare Suche nach jedem Rechteck durch den verfügbaren Speicherplatz. Dabei wird überprüft, ob jedes Pixel blockiert ist (gegen alle vorhandenen Rechtecke) ...
Fire Lancer
4
Eine optimale Lösung finden Sie in jair.org/media/3735/live-3735-6794-jair.pdf
Jim Balter
2
Es fiel mir schwer, mir vorzustellen, wie optimal dies funktionieren könnte. Also habe ich es codiert (mit einer quadratischen Form) und die Ergebnisse sind großartig. Hier ist eine Demo-Animation: imgur.com/ISjxuOR
Attila Tanyi
@ JimBalter quadratisch Platz ... wahrscheinlich ... in Bezug auf Geschwindigkeit und Skalierbarkeit? Nicht wirklich?
Arek Bal
86

Auf dieser Seite des ARC-Projekts finden Sie eine Übersicht über Lösungen. Es gibt einen Kompromiss zwischen Komplexität / Zeit der Implementierung und Optimalität, aber es steht eine breite Palette von Algorithmen zur Auswahl.

Hier ist ein Auszug der Algorithmen:

  1. FFDH-Algorithmus (First-Fit Decreasing Height)
    FFDH packt das nächste Element R (in nicht zunehmender Höhe) in die erste Ebene, in die R passt. Wenn keine Ebene R aufnehmen kann, wird eine neue Ebene erstellt.
    Zeitkomplexität von FFDH: O (n · log n).
    Approximationsverhältnis: FFDH (I) <= (17/10) · OPT (I) +1; Die asymptotische Grenze von 17/10 ist eng.

  2. NFDH-Algorithmus (Next-Fit Decreasing Height)
    NFDH packt das nächste Element R (in nicht zunehmender Höhe) auf die aktuelle Ebene, wenn R passt. Andernfalls wird die aktuelle Ebene "geschlossen" und eine neue Ebene erstellt.
    Zeitkomplexität: O (n · log n).
    Approximationsverhältnis: NFDH (I) <= 2 · OPT (I) +1; Die asymptotische Grenze von 2 ist eng.

  3. BFDH-Algorithmus (Best-Fit Decreasing Height)
    BFDH packt das nächste Element R (in nicht zunehmender Höhe) auf die Ebene unter denjenigen, die R aufnehmen können, für die der verbleibende horizontale Raum das Minimum ist. Wenn keine Ebene R aufnehmen kann, wird eine neue Ebene erstellt.

  4. Bottom-Left (BL) -Algorithmus
    BL Elemente erster Ordnung durch nicht zunehmende Breite. BL verpackt den nächsten Artikel so nah wie möglich am Boden und dann so nah wie möglich links, ohne sich mit einem verpackten Artikel zu überlappen. Beachten Sie, dass BL kein pegelorientierter Packungsalgorithmus ist.
    Zeitkomplexität: O (n ^ 2).
    Approximationsverhältnis: BL (I) <= 3 · OPT (I).

  5. Baker's Up-Down (UD) -Algorithmus
    UD verwendet eine Kombination aus BL und einer Verallgemeinerung von NFDH. Die Breite des Streifens und der Elemente wird normalisiert, sodass der Streifen die Einheitsbreite hat. UD ordnet die Artikel in nicht zunehmender Breite und unterteilt sie dann in fünf Gruppen mit einer Breite im Bereich (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3) ], (1 / 5,1 / 4], (0,1 / 5]. Der Streifen ist auch in fünf Bereiche R1, ···, R5 unterteilt. Grundsätzlich einige Elemente mit einer Breite im Bereich (1 / i +) 1, 1 / i] für 1 <= i <= 4 werden von BL in den Bereich Ri gepackt. Da BL auf der rechten Seite des Streifens einen Raum mit zunehmender Breite von oben nach unten lässt, nutzt UD diesen Vorteil zunächst Verpacken des Artikels nach Rj für j = 1, ···, 4 (in der Reihenfolge) von oben nach unten. Wenn kein solcher Platz vorhanden ist, wird der Artikel von BL nach Ri verpackt. Schließlich werden Artikel mit einer Größe von höchstens 1/5 werden durch den (verallgemeinerten) NFDH-Algorithmus in die Räume in R1, ···, R4 gepackt.
    Approximationsverhältnis: UD (I) <= (5/4) · OPT (I) + (53/8) H, wobei H die maximale Höhe der Gegenstände ist; Die asymptotische Grenze von 5/4 ist eng.

  6. Reverse-Fit (RF) -Algorithmus
    RF normalisiert auch die Breite des Streifens und der Elemente, so dass der Streifen die Einheitsbreite hat. RF stapelt zuerst alle Elemente mit einer Breite von mehr als 1/2. Die verbleibenden Gegenstände werden in nicht zunehmender Höhe sortiert und über der Höhe H0 verpackt, die von denjenigen erreicht wird, die größer als 1/2 sind. Dann wiederholt RF den folgenden Vorgang. Grob gesagt packt RF Gegenstände von links nach rechts mit ihrem Boden entlang der Linie der Höhe H0, bis kein Platz mehr vorhanden ist. Verpackt dann die Artikel von rechts nach links und von oben nach unten (als umgekehrte Ebene bezeichnet), bis die Gesamtbreite mindestens 1/2 beträgt. Dann wird die umgekehrte Ebene abgesenkt, bis (mindestens) einer von ihnen einen Gegenstand darunter berührt. Das Dropdown wird irgendwie wiederholt.
    Approximationsverhältnis: RF (I) <= 2 · OPT (I).

  7. Steinbergs Algorithmus Der
    Steinberg-Algorithmus, der in der Arbeit als M bezeichnet wird, schätzt eine Obergrenze der Höhe H, die zum Packen aller Elemente erforderlich ist, so dass bewiesen ist, dass die eingegebenen Elemente in ein Rechteck mit der Breite W und der Höhe H gepackt werden können Definieren Sie sieben Prozeduren (mit sieben Bedingungen), um ein Problem in zwei kleinere zu unterteilen und diese rekursiv zu lösen. Es wurde gezeigt, dass jedes nachvollziehbare Problem eine der sieben Bedingungen erfüllt.
    Approximationsverhältnis: M (I) <= 2 · OPT (I).

  8. Split-Fit-Algorithmus (SF) SF unterteilt Elemente in zwei Gruppen, L1 mit einer Breite von mehr als 1/2 und L2 höchstens 1/2. Alle Artikel von L1 werden zuerst von FFDH verpackt. Dann werden sie so angeordnet, dass alle Elemente mit einer Breite von mehr als 2/3 unter denen mit einer Breite von höchstens 2/3 liegen. Dies erzeugt ein Rechteck R des Raums mit einer Breite von 1/3. Die verbleibenden Elemente in L2 werden dann mit FFDH in R und den Raum über den mit L1 gepackten Elementen gepackt. Die in R erstellten Ebenen liegen unter denen, die über der Packung von L1 erstellt wurden.
    Approximationsverhältnis: SF (I) <= (3/2) · OPT (I) + 2; Die asymptotische Grenze von 3/2 ist eng.

  9. Sleator-Algorithmus Der
    Sleater-Algorithmus besteht aus vier Schritten:

    1. Alle Gegenstände mit einer Breite von mehr als 1/2 werden unten im Streifen übereinander gepackt. Angenommen, h0 ist die Höhe der resultierenden Packung. Alle nachfolgenden Packungen erfolgen oberhalb von h0.

    2. Die verbleibenden Artikel sind nach nicht zunehmender Höhe sortiert. Eine Ebene von Gegenständen wird (in nicht ansteigender Höhenreihenfolge) von links nach rechts entlang der Höhenlinie h0 verpackt.

    3. In der Mitte wird dann eine vertikale Linie gezeichnet, um den Streifen in zwei gleiche Hälften zu schneiden (beachten Sie, dass diese Linie einen Gegenstand schneiden kann, der teilweise in der rechten Hälfte verpackt ist). Zeichnen Sie zwei horizontale Liniensegmente mit einer Länge von einer Hälfte, eines über die linke Hälfte (als linke Grundlinie bezeichnet) und eines über die rechte Hälfte (als rechte Grundlinie bezeichnet) so niedrig wie möglich, sodass die beiden Linien kein Element kreuzen.

    4. Wählen Sie die linke oder rechte Grundlinie mit einer niedrigeren Höhe und packen Sie eine Ebene von Elementen in die entsprechende Hälfte des Streifens, bis das nächste Element zu breit ist.

    Eine neue Grundlinie wird gebildet und Schritt (4) wird auf der unteren Grundlinie wiederholt, bis alle Gegenstände verpackt sind.
    Zeitkomplexität: O (n · log n).
    Das Approximationsverhältnis des Sleator-Algorithmus beträgt 2,5, was eng ist.

Undefiniertes Verhalten
quelle
6
All dies erfordert die Kenntnis der Breite des Raums.
Quantum7
1
@ Quantum7 ist möglicherweise nicht allzu wichtig, da OP erfordert, dass die Seiten Zweierpotenzen sind, sodass wir einfach eine Reihe von Dimensionen mit genügend Fläche ausprobieren können.
Ciro Santilli 5 冠状 病 六四 事件 5
19

Schauen Sie sich Verpackungsprobleme an . Ich denke, Ihre fällt unter "2D-Behälterverpackung". Sie sollten in der Lage sein, viel aus Lösungen für dieses und andere Verpackungsprobleme zu lernen.

Siehe auch: Packen rechteckiger Bilddaten in eine quadratische Textur.

aib
quelle
Hier ist ein weiteres schönes Beispiel für einen optimierenden Algorithmus zum Packen von Rechtecken: codeproject.com/Articles/210979/…
Anderson Green
Problem auch erwähnt in: en.wikipedia.org/wiki/… Insbesondere beschränkt dies das Verpacken von Behältern auf einen einzelnen Behälter unbekannter Größe. Ich frage mich, ob es dort noch NP-vollständig ist.
Ciro Santilli 5 冠状 病 六四 事件 5
17

Zu diesem Problem gibt es umfangreiche Literatur. Eine gute gierige Heuristik besteht darin, Rechtecke vom größten zum kleinsten Bereich an der ersten verfügbaren Position unten und links vom Container zu platzieren. Denken Sie an die Schwerkraft, die alle Gegenstände in die untere linke Ecke zieht. Für eine Beschreibung dieser Google "Chazelle unten links Verpackung".

Für optimale Lösungen können die neuesten Techniken in wenigen Sekunden über 20 Rechtecke packen. Huang hat einen Algorithmus , der das Problem des Findens des kleinsten umschließenden Begrenzungsrahmens vom Problem der Entscheidung trennt, ob ein Satz Rechtecke in einen Begrenzungsrahmen einer bestimmten Größe passen kann oder nicht. Sie geben seinem Programm eine Reihe von Rechtecken und es zeigt Ihnen den kleinsten umschließenden Begrenzungsrahmen, der zum Packen erforderlich ist.

In Ihrem Fall sollte Ihre äußere Schleife vom kleinstmöglichen Begrenzungsrahmen nach oben iterieren (wobei Breite und Höhe sukzessive um Zweierpotenzen zunehmen). Testen Sie für jeden dieser Begrenzungsrahmen, ob Sie eine Packung für Ihre Rechtecke finden können. Sie erhalten eine Reihe von "Nein" -Antworten bis zur ersten "Ja" -Antwort, die garantiert die optimale Lösung darstellt.

Für die innere Schleife Ihres Algorithmus - die, die auf einen Begrenzungsrahmen bestimmter Größe mit "Ja" oder "Nein" antwortet - würde ich die Huang-Referenz nachschlagen und nur seinen Algorithmus implementieren. Er enthält viele Optimierungen zusätzlich zum grundlegenden Algorithmus, aber Sie brauchen wirklich nur das grundlegende Fleisch und die Kartoffeln. Da Sie Rotationen an jedem Verzweigungspunkt während Ihrer Suche verarbeiten möchten, versuchen Sie einfach beide Rotationen und den Backtrack, wenn beide Rotationen keine Lösung ergeben.

Eric
quelle
9

Ich bin mir ziemlich sicher, dass dies ein NP-hartes Problem ist. Um eine optimale Lösung zu finden, müssten Sie einen Backtracking-Algorithmus implementieren, der jede mögliche Kombination ausprobiert.

Die gute Nachricht ist, dass Sie aufgrund der Notwendigkeit, 2D-Rechtecke in einem begrenzten 2D-Raum zu packen, viele Möglichkeiten frühzeitig beschneiden können, sodass es möglicherweise nicht so schlimm ist.

Blind
quelle
3
Du meinst wahrscheinlich NP-vollständig.
Starblue
7
Nun, wenn es NP vollständig ist, dann ist es einfach zu lösen, lösen Sie einfach eine äquivalente Instanz des reisenden Verkäufers, und los geht's. Es ist jedoch trivial zu zeigen, dass dies nicht der Fall ist, da NP-vollständige Probleme Entscheidungsprobleme sind (Sie erhalten Ja / Nein-Antworten zurück) und einen polynomiellen Zeitverifizierungsalgorithmus haben. Die Frage "
Eclipse
2
@Eclipse ist korrekt. Von jair.org/media/3735/live-3735-6794-jair.pdf "Das Optimierungsproblem ist NP-schwer, während das Problem der Entscheidung, ob ein Satz von Rechtecken in einen bestimmten Begrenzungsrahmen gepackt werden kann, NP-vollständig ist. über eine Reduktion aus der Müllverpackung (Korf, 2003). " Beachten Sie jedoch, dass das OP nach "einem ziemlich optimalen Weg" gefragt hat, und es gibt Lösungen dafür in P, für ausreichend breite Definitionen von "fair".
Jim Balter
Ich vermute auch NP-Härte, aber wir brauchen eine Referenz / einen Beweis.
Ciro Santilli 5 冠状 病 六四 事件 5
2
Heiliger Faden Nekro, Batman. Dies ist ein Verpackungsproblem, und es hat sich bereits als bestenfalls NP-schwer erwiesen: en.wikipedia.org/wiki/Packing_problems
Blindy
2

Was Sie brauchen, ist bei https://github.com/nothings/stb/blob/master/stb_rect_pack.h

Stichprobe:

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}
Orbitus007
quelle
1

Eine allgemeine Lösung ist nicht trivial (Mathematik spricht für völlig unmöglich). Im
Allgemeinen verwenden die Leute einen genetischen Algorithmus, um mögliche Kombinationen auszuprobieren. Sie können dies jedoch recht gut tun, indem Sie einfach die größte Form zuerst eingeben und dann verschiedene Stellen für die ausprobieren nächstgrößere und so weiter.

Martin Beckett
quelle