Czy istnieje źródło C++/lib do rozwiązania Pakowania Bin 2D z prostokątnym pojemnikiem (nie kwadratem) i obrotem?

Question

Jak już napisano, potrzebuję kodu źródłowego C/C++ lub biblioteki, której mogę użyć do rozwiązania problemu pakowania kosza z prostokątnymi kształtami 2D, gdzie pojemnik jest również prostokątny, a prostokąty są również obracane o 90 °, aby pasowały lepiej . Mam już wszystkie wymagane wartości, więc nie potrzebuję żadnego algorytmu pakowania online.

Znalazłem tylko bibliotekę, która zajmuje się kwadratowym pojemnikiem i bez rotacji, która nie jest wystarczająco wydajna dla moich potrzeb.

Naprawdę doceniam wszystko, co C/C++ obsługuje prostokątny pojemnik i obrót.

Dzięki.

PS: Wymagany czas do obliczenia nie jest ważny, tylko wynik jest.

PPS: To musi być C lub C++, a nie mogę znaleźć coś pożytecznego szukają stackoverflow ...

Answer 1

http://clb.demon.fi/files/RectangleBinPack.pdf jest kluczem. To jest odniesienie na opakowaniu 2d bin.

Możesz tam zmodyfikować jeden z algorytmów, aby zaspokoić swoje potrzeby. Wątpię, aby rotacja była potrzebna, algorytmy są dość zaawansowane, tak jak są. Ten przykład (https://github.com/Lalaland/PixelPacker/blob/master/src/algoMaxRects.cpp) jest przykładem sposobu implementacji algorytmu MaxRects.

Modyfikacja, którą prawdopodobnie musiałbyś wykonać, znajduje się na górze algorytmu, kiedy wybierasz następny prostokąt do użycia. Po prostu spójrz także na różną orientację prostokątów i jazdę na rowerze po całej liście.

Answer 2

Znalazłem ten wątek kilka tygodni temu, po skim czytania PDF odpowiedź i toying wokół z kodem autorów, Zrobiłem re-write, który bardziej nadaje się do moich potrzeb (tekstury atlas opakowania)

Jeśli ktoś jest zainteresowany ... https://github.com/chris-stones/BinPack2D

• Pozwala użytkownikowi na pakiet danych o strukturze złożonych z prostokątów (nazwa pliku orig, etc)
• Paczka wiele pojemników (2D tablicy tekstury atlas - GL_EXT_texture_array)

Ponadto, zamiast śledzić dzielenie i łączenie wolnych prostokątów, śledzę i sortuję wolne górne lewe rogi. Zauważyłem, że jest znacznie łatwiejsze do wdrożenia, z równie dobrymi wynikami.

Brak dokumentacji, patrz PrzykładProgram() w górnej części pliku nagłówkowego.