Jakiego algorytmu można użyć do pakowania prostokątów o różnych rozmiarach w możliwie najmniejszy prostokąt w dość optymalny sposób?

Mam kilka prostokątnych przedmiotów, które muszę spakować na możliwie najmniejszą przestrzeń (wymiary tej przestrzeni powinny być potęgami dwóch).

Zdaję sobie sprawę z różnych algorytmów pakowania, które najlepiej zapakują elementy w dane miejsce, jednak w tym przypadku potrzebuję algorytmu, aby dowiedzieć się, jak duże powinno być również to miejsce.

Powiedzmy, że mam następujące prostokąty

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

Mogą być zapakowane w przestrzeń 128 * 128

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

Jednak jeśli byłby również 160 * 32 i 64 * 64, potrzebowałby 256 * 128 miejsca

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

Jakie są algorytmy, które są w stanie spakować wiązkę prostokątów i określić wymagany rozmiar pojemnika (do potęgi 2 i w ramach danego maksymalnego rozmiaru dla każdego wymiaru)?

Szybkie i brudne rozwiązanie pierwszego przejścia zawsze jest świetnym rozwiązaniem na początek, dla porównania, jeśli nic innego.

Chciwe umieszczenie od dużego do małego.

Umieść największy prostokąt pozostały w spakowanym obszarze. Jeśli nie można go nigdzie zmieścić, umieść go w miejscu, które jak najmniej rozszerza region paczki. Powtarzaj, aż skończysz z najmniejszym prostokątem.

To wcale nie jest idealne, ale jest łatwe i przyjemne. Nadal idealnie spakuje twój oryginalny przykład i da ci równoważną odpowiedź również na drugi.

Zobacz tę stronę w projekcie ARC, aby uzyskać przegląd rozwiązań, istnieje kompromis między złożonością / czasem wdrożenia a optymalnością, ale istnieje szeroki wybór algorytmów do wyboru.

Oto wyciąg z algorytmów:

1. Algorytm
   FFDH First-Fit malejącej wysokości (FFDH) pakuje następny element R (w wysokości niewzrastającej) na pierwszym poziomie, na którym pasuje R. Jeśli żaden poziom nie pomieści R, tworzony jest nowy poziom.
   Złożoność czasowa FFDH: O (n · log n).
   Współczynnik aproksymacji: FFDH (I) <= (17/10) · OPT (I) +1; asymptotyczna granica 17/10 jest ciasna.

2. Algorytm Next-Fit malejącej wysokości (NFDH)
   NFDH pakuje następny element R (w wysokości niewzrastającej) na bieżącym poziomie, jeśli R pasuje. W przeciwnym razie bieżący poziom zostanie „zamknięty” i zostanie utworzony nowy poziom.
   Złożoność czasowa: O (n · log n).
   Współczynnik aproksymacji: NFDH (I) <= 2 · OPT (I) +1; asymptotyczna granica 2 jest ciasna.

3. Algorytm Best-Fit malejącej wysokości (BFDH)
   BFDH pakuje następny element R (w wysokości niewzrastającej) na poziomie, wśród tych, które mogą pomieścić R, dla których pozostała przestrzeń pozioma jest minimalna. Jeśli żaden poziom nie pomieści R, tworzony jest nowy poziom.

4. Algorytm u dołu po lewej stronie (BL)
   Elementy pierwszego rzędu BL według nie zwiększającej się szerokości. BL pakuje następny element tak blisko dna, jak to pasuje, a następnie tak blisko lewej, jak to możliwe, bez nakładania się na żaden spakowany przedmiot. Zauważ, że BL nie jest algorytmem pakowania zorientowanym na poziom.
   Złożoność czasowa: O (n ^ 2).
   Współczynnik aproksymacji: BL (I) <= 3 · OPT (I).

5. Algorytm Baker's Up-Down (UD)
   UD używa kombinacji BL i uogólnienia NFDH. Szerokość paska i elementów są znormalizowane, dzięki czemu pasek ma szerokość jednostkową. UD zamawia elementy o nie zwiększającej się szerokości, a następnie dzieli je na pięć grup, każda o szerokości w zakresie (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. Pasek jest również podzielony na pięć obszarów R1, ···, R5. Zasadniczo niektóre elementy o szerokości w zakresie (1 / i + 1, 1 / i], dla 1 <= i <= 4, są pakowane do obszaru Ri przez BL. Ponieważ BL pozostawia przestrzeń o rosnącej szerokości od góry do dołu po prawej stronie paska, UD wykorzystuje tę zaletę najpierw pakowanie przedmiotu do Rj dla j = 1, ···, 4 (w kolejności) od góry do dołu. Jeśli nie ma takiej przestrzeni, przedmiot jest pakowany do Ri przez BL. Wreszcie, przedmioty o rozmiarze co najwyżej 1/5 są spakowane do spacji w R1, ···, R4 za pomocą (uogólnionego) algorytmu NFDH.
   Współczynnik przybliżenia: UD (I) <= (5/4) · OPT (I) + (53/8) H, gdzie H jest maksymalną wysokością przedmiotów; asymptotyczna granica 5/4 jest ciasna.

6. Algorytm odwrotnego dopasowania (RF)
   RF normalizuje również szerokość paska i elementów, dzięki czemu pasek ma szerokość jednostkową. RF najpierw układa wszystkie elementy o szerokości większej niż 1/2. Pozostałe elementy są sortowane według rosnącej wysokości i będą pakowane powyżej wysokości H0 osiągniętej przez te większe niż 1/2. Następnie RF powtarza następujący proces. Z grubsza mówiąc, RF pakuje przedmioty od lewej do prawej, z ich dnem wzdłuż linii wysokości H0, aż nie będzie już miejsca. Następnie pakuje przedmioty od prawej do lewej i od góry do dołu (zwane poziomem odwrotnym), aż całkowita szerokość będzie wynosić co najmniej 1/2. Następnie poziom wsteczny jest opuszczany, aż (przynajmniej) jeden z nich dotknie jakiegoś elementu poniżej. Rozwijane menu jest w jakiś sposób powtarzane.
   Współczynnik aproksymacji: RF (I) <= 2 · OPT (I).

7. Algorytm
   Steinberga Algorytm Steinberga, oznaczony w artykule jako M, szacuje górną granicę wysokości H wymaganą do spakowania wszystkich przedmiotów w taki sposób, że udowodniono, że elementy wejściowe można upakować w prostokąt o szerokości W i wysokości H. zdefiniuj siedem procedur (z siedmioma warunkami), każda z nich, aby podzielić problem na dwie mniejsze i rozwiązać je rekurencyjnie. Wykazano, że każdy możliwy do rozwiązania problem spełnia jeden z siedmiu warunków.
   Współczynnik aproksymacji: M (I) <= 2 · OPT (I).

8. Algorytm Split-Fit (SF) SF dzieli elementy na dwie grupy, L1 o szerokości większej niż 1/2 i L2 co najwyżej 1/2. Wszystkie elementy L1 są najpierw pakowane przez FFDH. Następnie są ułożone tak, aby wszystkie przedmioty o szerokości większej niż 2/3 znajdowały się poniżej tych o szerokości co najwyżej 2/3. To tworzy prostokąt R przestrzeni o szerokości 1/3. Pozostałe przedmioty w L2 są następnie pakowane do R, a przestrzeń powyżej tych wypełnionych L1 za pomocą FFDH. Poziomy utworzone w R są uważane za niższe niż poziomy utworzone powyżej upakowania L1.
   Współczynnik aproksymacji: SF (I) <= (3/2) · OPT (I) + 2; asymptotyczna granica 3/2 jest ciasna.

9. Algorytm
   Sleater Algorytm Sleater składa się z czterech kroków:

   1. Wszystkie elementy o szerokości większej niż 1/2 są pakowane jeden na drugim w dolnej części paska. Załóżmy, że h0 jest wysokością wynikowego opakowania. Wszystkie kolejne opakowania będą występować powyżej h0.

   2. Pozostałe elementy są uporządkowane według wysokości niewzrastającej. Poziom przedmiotów jest pakowany (w kolejności rosnącej) od lewej do prawej wzdłuż linii wysokości h0.

   3. Następnie na środku narysowana jest pionowa linia, aby przeciąć pasek na dwie równe połowy (zwróć uwagę, że ta linia może przeciąć przedmiot, który jest częściowo zapakowany w prawej połowie). Narysuj dwa segmenty linii poziomej o długości jedna połowa, jeden przez lewą połowę (zwaną lewą linią bazową) i jeden przez prawą połowę (zwaną prawą linią bazową) tak nisko, jak to możliwe, aby dwie linie nie przecinały żadnego elementu.

   4. Wybierz lewą lub prawą linię bazową o niższej wysokości i zapakuj poziom przedmiotów w odpowiednią połowę paska, aż następny element będzie zbyt szeroki.

   Utworzona zostaje nowa linia bazowa i etap (4) powtarza się na dolnej linii bazowej, aż wszystkie elementy zostaną spakowane.
   Złożoność czasowa: O (n · log n).
   Współczynnik przybliżenia algorytmu Sleator wynosi 2,5, co jest ścisłe.

Zobacz problemy z pakowaniem . Myślę, że twój należy do „pakowania bin 2D”. Powinieneś być w stanie wiele nauczyć się od rozwiązań tego i innych problemów z pakowaniem.

Zobacz także: Pakowanie prostokątnych danych obrazu w kwadratową teksturę.

Istnieje obszerna literatura na ten temat. Dobrym zachłannym heurystycznym jest umieszczanie prostokątów od największego obszaru do najmniejszego w pierwszej dostępnej pozycji w kierunku dolnej i lewej strony pojemnika. Pomyśl o grawitacji ciągnącej wszystkie przedmioty do lewego dolnego rogu. Opis tego google „Chazelle u dołu po lewej stronie opakowania”.

Aby uzyskać optymalne rozwiązania, najnowocześniejsze techniki mogą spakować ponad 20 prostokątów w kilka sekund. Huang ma algorytm, który oddziela problem znajdowania najmniejszej otaczającej ramki granicznej od problemu decydowania, czy zestaw prostokąta może zmieścić się w ramce granicznej o określonym rozmiarze. Dajesz jego programowi zestaw prostokątów, a to mówi ci o najmniejszej otaczającej ramce granicznej wymaganej do ich spakowania.

W twoim przypadku zewnętrzna pętla powinna iterować od najmniejszej możliwej ramki ograniczającej w górę (z szerokością i wysokością sukcesywnie zwiększaną o potęgę dwóch). Dla każdego z tych obwiedni sprawdź, czy możesz znaleźć opakowanie dla swoich prostokątów. Otrzymasz mnóstwo odpowiedzi „nie”, aż do pierwszej odpowiedzi „tak”, która z pewnością będzie optymalnym rozwiązaniem.

W przypadku wewnętrznej pętli twojego algorytmu - tej, która odpowiada „tak” lub „nie” na ramkę ograniczającą określonego rozmiaru, sprawdziłbym referencję Huanga i po prostu zaimplementowałem jego algorytm. Zawiera wiele optymalizacji oprócz podstawowego algorytmu, ale tak naprawdę potrzebujesz tylko podstawowego mięsa i ziemniaków. Ponieważ chcesz obsługiwać obroty, w każdym punkcie rozgałęzienia podczas wyszukiwania po prostu wypróbuj oba obroty i cofnij się, gdy oba obroty nie przyniosą rozwiązania.

Jestem całkiem pewien, że jest to trudny problem NP , więc dla optymalnego rozwiązania musiałbyś zaimplementować algorytm cofania, który wypróbuje każdą możliwą kombinację.

Dobrą wiadomością jest to, że ze względu na potrzebę pakowania prostokątów 2D w ograniczonej przestrzeni 2D, możesz przycinać wiele możliwości na wczesnym etapie, więc może nie być tak źle.

To czego potrzebujesz to https://github.com/nothings/stb/blob/master/stb_rect_pack.h

próba:

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);
}

Ogólne rozwiązanie nie jest trywialne (matematyka mówi całkowicie niemożliwie)
Generalnie ludzie używają algorytmu genetycznego, aby wypróbować możliwe kombinacje, ale możesz zrobić to całkiem dobrze, ustawiając najpierw największy kształt, a następnie próbując różnych miejsc dla następny największy i tak dalej.