Apa algoritma dapat digunakan untuk kemasan persegi panjang dengan ukuran yang berbeda ke dalam persegi panjang terkecil yang mungkin yang cukup optimal?

Lihat halaman ini pada BUSUR proyek untuk survei solusi, ada trade-off antara kompleksitas implementasi/waktu dan optimalitas, tetapi ada berbagai macam algoritma untuk memilih dari. Berikut ini's ekstrak algoritma:

1. Pertama-Fit Penurunan Tinggi (FFDH) algoritma FFDH paket item berikutnya R (non-meningkatkan tinggi) pada tingkat pertama dimana R cocok. Jika tidak ada tingkat yang dapat menampung R, tingkat yang baru dibuat. Kompleksitas waktu dari FFDH: O(n·log n). Pendekatan rasio: FFDH(I)<=(17/10)·MEMILIH(I)+1; asymptotic terikat 17/10 ketat.
2. Next-Fit Penurunan Tinggi (NFDH) algoritma NFDH paket item berikutnya R (non-meningkatkan tinggi) pada tingkat saat ini jika R cocok. Sebaliknya, tingkat saat ini adalah "tutup" dan tingkat yang baru dibuat. Kompleksitas waktu O(n·log n). Pendekatan rasio: NFDH(I) <= 2·MEMILIH(I)+1; asymptotic bound 2 lebih ketat.
3. Best-Fit Decreasing Tinggi (BFDH) algoritma BFDH paket item berikutnya R (non-meningkatkan tinggi) pada tingkat, di antara mereka yang dapat menampung R, yang sisa ruang horisontal adalah minimum. Jika tidak ada tingkat yang dapat menampung R, tingkat yang baru dibuat.
4. Kiri bawah (BL) Algoritma BL urutan pertama item dengan non-meningkatkan lebar. BL paket item berikutnya sebagai dekat dengan bagian bawah seperti itu akan cocok dan kemudian sebagai dekat ke kiri karena dapat pergi tanpa tumpang tindih dengan dikemas item. Perhatikan bahwa BL adalah bukan tingkat berorientasi packing algoritma. Kompleksitas waktu O(n^2). Pendekatan rasio: BL(I) <= 3·MEMILIH(saya).
5. Baker's Atas-Bawah (UD) algoritma UD menggunakan kombinasi dari BL dan generalisasi dari NFDH. Lebar strip dan barang-barang yang dinormalisasi sehingga strip dari unit lebar. UD pesanan barang-barang non-meningkatkan lebar dan kemudian membagi item menjadi lima kelompok, masing-masing dengan lebar di kisaran (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. Jalur ini juga dibagi menjadi lima wilayah R1, ··· , R5. Pada dasarnya, beberapa item lebar di kisaran (1/i+1, 1/i], untuk 1 <= i <= 4, yang dikemas untuk wilayah Ri oleh BL. Sejak BL meninggalkan ruang meningkatkan lebar dari atas ke bawah pada sisi kanan jalur, UD mengambil keuntungan ini dengan terlebih dahulu packing barang untuk Rj untuk j = 1, ··· , 4 (dalam rangka) dari atas ke bawah. Jika tidak ada ruang, barang dikemas untuk Ri oleh BL. Akhirnya, barang-barang dari ukuran yang paling banyak 1/5 dikemas dengan ruang-ruang di R1, ··· , R4 oleh (generalized) NFDH algoritma. Lagi jika tidak ada ruang di wilayah ini, barang dikemas untuk R5 menggunakan NFDH. Pendekatan rasio: UD(I) <= (5/4) · MEMILIH(I)+(53/8)H, dimana H adalah ketinggian maksimum dari barang-barang; asymptotic terikat 5/4 ketat.
6. Sebaliknya-fit (RF) algoritma RF juga menormalkan lebar strip dan barang-barang jadi yang strip dari unit lebar. RF pertama tumpukan semua item lebar lebih besar dari 1/2. Sisa barang diurutkan dalam non-meningkatkan tinggi dan akan dikemas di atas ketinggian H0 yang dicapai oleh orang-orang yang lebih besar dari 1/2. Kemudian RF mengulangi proses berikut. Secara kasar, RF paket barang dari kiri ke kanan dengan mereka bawah di sepanjang garis ketinggian H0 sampai tidak ada lebih banyak ruang. Kemudian paket barang dari kanan ke kiri dan dari atas ke bawah (disebut reverse-level) sampai total lebar setidaknya 1/2. Kemudian terbalik-tingkat turun ke bawah sampai (minimal) salah satu dari mereka menyentuh beberapa item di bawah ini. Drop down entah bagaimana diulang. Pendekatan rasio: RF(I) <= 2·MEMILIH(saya).
7. Steinberg's algoritma Steinberg's algoritma, dinotasikan sebagai M di atas kertas, perkiraan batas atas dari ketinggian H yang diperlukan untuk pak semua barang-barang seperti itu hal ini membuktikan bahwa input item yang dapat dikemas menjadi persegi panjang dari lebar W dan tinggi H. Mereka kemudian menetapkan tujuh prosedur (dengan tujuh kondisi), masing-masing untuk membagi masalah ke dua yang lebih kecil dan menyelesaikannya secara rekursif. Hal ini telah menunjukkan bahwa setiap penurut masalah memenuhi salah satu dari tujuh kondisi. Pendekatan rasio: M(I) <= 2·MEMILIH(saya).
8. Split-Fit algorithm (SF) SF membagi item menjadi dua kelompok, L1 dengan lebar lebih besar dari 1/2 dan L2 di sebagian besar 1/2. Semua barang dari L1 adalah pertama dikemas oleh FFDH. Kemudian mereka diatur sedemikian rupa sehingga semua item dengan lebar lebih dari 2/3 berada di bawah mereka dengan lebar paling sedikit 2/3. Hal ini menciptakan sebuah persegi panjang R ruang dengan lebar 1/3. Item yang tersisa di L2 kemudian dikemas untuk R dan ruang di atas mereka dikemas dengan L1 menggunakan FFDH. Tingkat dibuat di R dianggap di bawah ini yang dibuat di atas packing L1. Pendekatan rasio: SF(I) <= (3/2) ·MEMILIH(I) + 2; asymptotic terikat 3/2 ketat.
9. Sleator's algoritma Sleater's algoritma ini terdiri dari empat langkah:
10. Semua item lebar lebih besar dari 1/2 dikemas di atas satu sama lain di bawah strip. Misalkan h0 ketinggian yang dihasilkan packing Semua kemasan berikutnya akan terjadi di atas h0.
11. Item yang tersisa diperintahkan oleh non-meningkatkan ketinggian. Tingkat produk yang dikemas (non-meningkatkan ketinggian order) dari kiri ke kanan sepanjang garis ketinggian h0.
12. Garis vertikal kemudian ditarik di tengah untuk memotong jalur menjadi dua bagian yang sama (perhatikan baris ini dapat memotong item yang dikemas secara parsial di bagian kanan). Menggambar dua garis horizontal segmen panjang satu setengah, satu di kiri setengah (disebut baseline) dan satu di bagian kanan (disebut hak dasar) serendah mungkin sehingga dua baris tidak melewati setiap item.
13. Memilih kiri atau kanan baseline yang dari ketinggian yang lebih rendah dan paket tingkat barang-barang ke tempat yang sesuai setengah strip sampai item berikutnya adalah terlalu lebar. Baseline baru terbentuk dan Langkah (4) diulang pada bagian bawah baseline sampai semua barang yang dikemas. Kompleksitas waktu O(n ·log n). Pendekatan rasio Sleator's algoritma adalah 2,5 yang lebih ketat.

Cepat dan kotor pertama melewati larutan adalah selalu salah besar untuk mulai dengan, sebagai perbandingan jika tidak ada yang lain.

Serakah penempatan dari besar ke kecil.

Menempatkan terbesar persegi panjang yang tersisa ke dikemas daerah. Jika hal ini dapat't cocok di mana saja, tempat itu di tempat yang meluas pack wilayah sesedikit mungkin. Ulangi sampai anda selesai dengan persegi panjang terkecil.

It's tidak sempurna sama sekali tapi itu's mudah dan bagus baseline. Itu masih akan pack asli anda misalnya dengan sempurna, dan memberikan anda sebuah setara jawaban untuk kedua juga.

Silahkan lihat di packing masalah. Saya pikir anda berada di bawah '2D bin packing.' Anda harus dapat belajar banyak dari solusi untuk itu dan kemasan lainnya masalah.

Lihat juga: Kemasan persegi panjang data gambar menjadi persegi tekstur.

Ada literatur yang luas pada masalah ini. Baik greedy heuristik adalah untuk menempatkan persegi dari luas terbesar ke terkecil, dalam posisi ke arah bawah dan kiri dari wadah. Berpikir gravitasi menarik semua barang-barang ke pojok kiri bawah. Untuk keterangan ini google "Chazelle kiri bawah kemasan".

Untuk solusi yang optimal, negara-of-the-art teknik dapat paket lebih dari 20 persegi panjang dalam beberapa detik. Huang an algoritma yang memisahkan masalah untuk menemukan yang terkecil melampirkan bounding box dari masalah memutuskan apakah atau tidak satu set persegi panjang yang dapat disimpan dalam sebuah kotak batas ukuran tertentu. Anda memberikan program satu set persegi panjang, dan ia memberitahu anda terkecil melampirkan kotak batas yang diperlukan untuk paket mereka.

Untuk kasus anda, anda outer loop harus beralih dari yang terkecil mungkin bounding box ke atas (dengan lebar dan tinggi berturut-turut meningkat oleh kekuatan dari dua). Untuk masing-masing bounding box, tes untuk melihat apakah anda dapat menemukan kemasan untuk persegi panjang. Anda akan mendapatkan banyak "tidak" jawaban, sampai pertama "ya" jawaban, yang akan dijamin untuk menjadi solusi yang optimal.

Untuk inner loop algoritma anda-salah satu yang jawaban "ya" atau "tidak" untuk bounding box dari ukuran tertentu, saya akan mencari Huang referensi dan hanya menerapkan algoritma-nya. Ia mencakup banyak optimasi di atas dasar algoritma, tetapi anda hanya benar-benar membutuhkan dasar daging dan kentang. Karena anda ingin menangani rotasi, pada setiap titik cabang selama pencarian anda, hanya mencoba kedua rotasi dan mundur ketika rotasi tidak menghasilkan solusi.

I'm cukup yakin bahwa ini adalah NP-hard problem, sehingga, untuk solusi optimal, anda'd harus menerapkan algoritma backtracking yang mencoba setiap kombinasi yang mungkin.

Kabar baiknya adalah bahwa karena kebutuhan untuk paket 2D persegi panjang di ruang 2D, anda dapat memangkas banyak kemungkinan pada awal, jadi itu mungkin tidak akan seburuk ITU.

Yang anda butuhkan adalah di https://github.com/nothings/stb/blob/master/stb_rect_pack.h

contoh:

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

Solusi umum adalah non-sepele (matematika berbicara untuk benar-benar ****ing mustahil) Umumnya orang-orang menggunakan algoritma genetika untuk mencoba kombinasi yang mungkin, tetapi dapat anda lakukan dengan cukup baik dengan meletakkan terbesar dalam bentuk pertama dan kemudian mencoba tempat yang berbeda untuk terbesar berikutnya dan seterusnya.

I'm menggunakan salah satu dari:

https://codereview.stackexchange.com/questions/179565/incremental-2d-rectangle-bin-packer?newreg=cce6c6101cf349c58423058762fa12b2

Menerapkan guillotine algoritma dan membutuhkan sebagai masukan satu dimensi dan mencoba untuk mengoptimalkan lain (anda juga dapat mengatur maksimum dengan sedikit perubahan pada kode). Mungkin jika anda mencoba berbagai kekuatan dari dua nilai itu akan bekerja untuk anda.

Hal ini tidak optimal dalam cara apapun, tapi itu kecil, portabel (.jam saja), dan tidak memiliki ketergantungan lainnya dari C++ dan STL.