Algoritma apa yang dapat digunakan untuk mengemas persegi panjang dengan ukuran berbeda ke dalam persegi panjang terkecil dengan cara yang cukup optimal?

Saya punya banyak objek persegi yang saya perlu masukkan ke ruang sekecil mungkin (dimensi ruang ini harus kekuatan dua).

Saya mengetahui berbagai algoritme pengemasan yang akan mengemas barang-barang sebaik mungkin ke dalam ruang yang diberikan, namun dalam hal ini saya perlu algoritme untuk mengetahui seberapa besar ruang yang seharusnya.

Misalnya katakanlah saya punya persegi panjang berikut

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

Mereka dapat dikemas ke dalam ruang 128 * 128

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

Namun jika ada juga 160 * 32 dan 64 * 64 yang membutuhkan ruang 256 * 128

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

Algoritma apa yang ada yang mampu mengemas sekelompok persegi panjang dan menentukan ukuran yang diperlukan untuk wadah (dengan kekuatan 2, dan dalam ukuran maksimum yang diberikan untuk setiap dimensi)?

Solusi first pass cepat dan kotor selalu bagus untuk memulai, sebagai perbandingan jika tidak ada yang lain.

Penempatan serakah dari besar ke kecil.

Masukkan persegi panjang terbesar yang tersisa ke area Anda. Jika tidak bisa muat di mana saja, letakkan di tempat yang memperluas wilayah paket sesedikit mungkin. Ulangi sampai Anda selesai dengan persegi panjang terkecil.

Ini tidak sempurna sama sekali tetapi mudah dan garis dasar yang bagus. Itu masih akan mengemas contoh asli Anda dengan sempurna, dan memberi Anda jawaban yang setara untuk yang kedua juga.

Lihat halaman ini pada proyek ARC untuk survei solusi, ada trade-off antara kompleksitas implementasi / waktu dan optimalitas, tetapi ada berbagai algoritma untuk dipilih.

Berikut adalah ringkasan algoritme:

1. Algoritma First-Fit Decreasing Height (FFDH)
   FFDH mengemas item R berikutnya (dalam ketinggian yang tidak bertambah) pada tingkat pertama di mana R cocok. Jika tidak ada level yang dapat menampung R, level baru dibuat.
   Kompleksitas waktu FFDH: O (n · log n).
   Rasio perkiraan: FFDH (I) <= (17/10) · OPT (I) +1; batas asimtotik 17/10 ketat.

2. Algoritma Next-Fit Decreasing Height (NFDH)
   NFDH mengemas item R berikutnya (dalam ketinggian yang tidak bertambah) pada level saat ini jika R cocok. Jika tidak, level saat ini "tertutup" dan level baru dibuat.
   Kompleksitas waktu: O (n · log n).
   Rasio perkiraan: NFDH (I) <= 2 · OPT (I) +1; batas asimptotik dari 2 adalah ketat.

3. Algoritma Best-Fit Decreasing Height (BFDH)
   BFDH mengemas item R berikutnya (dalam ketinggian yang tidak bertambah) pada level, di antara yang dapat mengakomodasi R, yang ruang horisontal residualnya adalah minimum. Jika tidak ada level yang dapat menampung R, level baru dibuat.

4. Algoritma Bawah-Kiri (BL)
   item urutan pertama BL dengan lebar tidak bertambah. BL mengemas item berikutnya sedekat mungkin dengan bagian bawahnya dan kemudian sedekat mungkin dengan yang tersisa tanpa tumpang tindih dengan barang yang dikemas. Perhatikan bahwa BL bukan algoritma pengemasan berorientasi level.
   Kompleksitas waktu: O (n ^ 2).
   Rasio perkiraan: BL (I) <= 3 · OPT (I).

5. Algoritma Baker's Up-Down (UD)
   UD menggunakan kombinasi BL dan generalisasi NFDH. Lebar strip dan item dinormalisasi sehingga strip adalah lebar unit. UD memesan item dengan lebar yang tidak bertambah dan kemudian membagi item menjadi lima kelompok, masing-masing dengan lebar dalam kisaran (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. Strip juga dibagi menjadi lima wilayah R1, ···, R5. Pada dasarnya, beberapa item lebar dalam kisaran (1 / i + 1, 1 / i], untuk 1 <= i <= 4, dikemas ke wilayah Ri oleh BL. Karena BL menyisakan ruang yang bertambah lebar dari atas ke bawah di sisi kanan strip, UD mengambil keuntungan ini dengan terlebih dahulu mengepak item ke Rj untuk j = 1, ···, 4 (dalam urutan) dari atas ke bawah. Jika tidak ada ruang seperti itu, item tersebut dikemas ke Ri oleh BL. Akhirnya, item ukuran paling banyak 1/5 dikemas ke spasi dalam R1, ···, R4 oleh algoritma NFDH (umum).
   Rasio perkiraan: UD (I) <= (5/4) · OPT (I) + (53/8) H, di mana H adalah ketinggian maksimum item; batas asimptotik 5/4 ketat.

6. Algoritma Reverse-fit (RF)
   RF juga menormalkan lebar strip dan item sehingga strip memiliki lebar unit. RF pertama-tama menumpuk semua item dengan lebar lebih besar dari 1/2. Item yang tersisa diurutkan dalam ketinggian yang tidak bertambah dan akan dikemas di atas ketinggian yang dicapai H0 oleh mereka yang lebih besar dari 1/2. Kemudian RF mengulangi proses berikut. Secara kasar, RF mengemas item dari kiri ke kanan dengan bagian bawahnya di sepanjang garis ketinggian H0 sampai tidak ada lagi ruang. Kemudian bungkus barang-barang dari kanan ke kiri dan dari atas ke bawah (disebut tingkat terbalik) hingga total lebar setidaknya 1/2. Kemudian level terbalik dijatuhkan hingga (setidaknya) salah satunya menyentuh beberapa item di bawah ini. Drop down entah bagaimana diulang.
   Rasio perkiraan: RF (I) <= 2 · OPT (I).

7. Algoritma
   Steinberg Algoritma Steinberg, dilambangkan sebagai M dalam makalah, memperkirakan batas atas ketinggian H yang diperlukan untuk mengemas semua item sehingga terbukti bahwa item input dapat dikemas ke dalam persegi panjang lebar W dan tinggi H. Mereka kemudian mendefinisikan tujuh prosedur (dengan tujuh kondisi), masing-masing untuk membagi masalah menjadi dua yang lebih kecil dan menyelesaikannya secara rekursif. Telah ditunjukkan bahwa setiap masalah yang bisa diselesaikan memenuhi salah satu dari tujuh syarat.
   Rasio perkiraan: M (I) <= 2 · OPT (I).

8. Algoritma Split-Fit (SF) SF membagi item menjadi dua kelompok, L1 dengan lebar lebih besar dari 1/2 dan L2 paling banyak 1/2. Semua item L1 pertama kali dikemas oleh FFDH. Kemudian mereka diatur sehingga semua item dengan lebar lebih dari 2/3 berada di bawah mereka dengan lebar paling banyak 2/3. Ini menciptakan ruang R persegi dengan lebar 1/3. Item yang tersisa di L2 kemudian dikemas ke R dan ruang di atas yang dikemas dengan L1 menggunakan FFDH. Level yang dibuat dalam R dianggap di bawah level yang dibuat di atas kemasan L1.
   Rasio perkiraan: SF (I) <= (3/2) · OPT (I) + 2; batas asimtotik 3/2 ketat.

9. Algoritma Sleator Algoritma
   Sleater terdiri dari empat langkah:

   1. Semua item dengan lebar lebih dari 1/2 dikemas di atas satu sama lain di bagian bawah strip. Misalkan h0 adalah ketinggian pengepakan yang dihasilkan Semua pengepakan berikutnya akan terjadi di atas h0.

   2. Barang yang tersisa dipesan dengan ketinggian yang tidak bertambah. Tingkat item dikemas (dalam urutan ketinggian tidak meningkat) dari kiri ke kanan sepanjang garis ketinggian h0.

   3. Garis vertikal kemudian ditarik di tengah untuk memotong strip menjadi dua bagian yang sama (perhatikan baris ini dapat memotong item yang dikemas sebagian di bagian kanan). Gambarkan dua segmen garis horizontal dengan panjang satu setengah, satu melintasi setengah kiri (disebut garis dasar kiri) dan satu melintasi setengah kanan (disebut garis dasar kanan) serendah mungkin sehingga kedua garis tidak melewati item apa pun.

   4. Pilih garis dasar kiri atau kanan yang memiliki ketinggian lebih rendah dan kemas tingkat item ke dalam setengah strip yang sesuai sampai item berikutnya terlalu lebar.

   Garis dasar baru terbentuk dan Langkah (4) diulangi pada garis dasar yang lebih rendah sampai semua barang dikemas.
   Kompleksitas waktu: O (n · log n).
   Rasio perkiraan algoritma Sleator adalah 2,5 yang ketat.

Lihatlah masalah pengepakan . Saya pikir milik Anda termasuk dalam 'pengemasan bin 2D.' Anda harus dapat belajar banyak dari solusi untuk itu dan masalah pengepakan lainnya.

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

Ada banyak literatur tentang masalah ini. Heuristik rakus yang baik adalah menempatkan persegi panjang dari area terbesar ke terkecil di posisi pertama yang tersedia di bagian bawah dan kiri wadah. Bayangkan gravitasi menarik semua benda ke sudut kiri bawah. Untuk deskripsi dari google ini "Chazelle packing kiri bawah".

Untuk solusi optimal, teknik canggih dapat mengemas lebih dari 20 persegi panjang dalam beberapa detik. Huang memiliki algoritme yang memisahkan masalah menemukan kotak pembatas terlampir terkecil dari masalah memutuskan apakah satu set persegi panjang dapat masuk ke dalam kotak pembatas dengan ukuran tertentu. Anda memberikan programnya satu set persegi panjang, dan itu memberi tahu Anda kotak terikat terlampir terkecil yang diperlukan untuk mengemasnya.

Untuk kasus Anda, loop luar Anda harus beralih dari kotak pembatas sekecil mungkin ke atas (dengan lebar dan tinggi berturut-turut meningkat dengan kekuatan dua). Untuk masing-masing kotak pembatas ini, ujilah untuk melihat apakah Anda dapat menemukan kemasan untuk persegi panjang Anda. Anda akan mendapatkan banyak jawaban "tidak", sampai jawaban "ya" pertama, yang akan dijamin menjadi solusi optimal.

Untuk loop dalam algoritma Anda - yang menjawab "ya" atau "tidak" ke kotak pembatas ukuran tertentu, saya akan mencari referensi Huang dan hanya mengimplementasikan algoritme-nya. Ia menyertakan banyak optimasi di atas algoritma dasar, tetapi Anda hanya benar-benar membutuhkan daging dan kentang. Karena Anda ingin menangani rotasi, di setiap titik cabang selama pencarian Anda, coba saja rotasi dan mundur ketika kedua rotasi tidak menghasilkan solusi.

Saya cukup yakin bahwa ini adalah masalah NP-hard , jadi, untuk solusi optimal, Anda harus menerapkan algoritma backtracking yang mencoba setiap kombinasi yang mungkin.

Kabar baiknya adalah bahwa karena kebutuhan untuk mengemas persegi panjang 2D dalam ruang 2D yang terbatas, Anda dapat memangkas banyak kemungkinan sejak awal, sehingga mungkin tidak terlalu buruk.

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

Sampel:

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 (berbicara matematika untuk benar-benar mustahil)
Secara umum orang menggunakan algoritma genetika untuk mencoba kombinasi yang mungkin tetapi Anda dapat melakukannya dengan cukup baik dengan hanya menempatkan bentuk terbesar di pertama dan kemudian mencoba tempat yang berbeda untuk terbesar berikutnya dan seterusnya.