Bin-Packing Problem

Opisani su i analizirani osnovni egzaktni, heuristički i aproksimativni algoritmi za Bin-packing problem u jednoj i dvije dimenzije. Za Bin-packing problem u tri dimenzije dan je kratak pregled algoritama koji se koriste. Implementirana je programska podrška za rješavanje 1D i 2D problema opisanim algoritmima. Također je implementiran algoritam za pakiranje slika (tekstura) u jednu veću (engl. \textit{texture atlas}), koja može rasti po potrebi. Takvo pakiranje slika često se koristi u razvoju videoigara, jer poboljšava performanse prikazivanja slika. Implementirani algoritmi evaluirani su na nasumično generiranim instancama problema, a rezultati su prezentirani te je na osnovu njih napravljena usporedba performansi algoritama.Basic exact, heuristic, and approximation algorithms for one and two-dimensional Bin-Packing are described and analyzed. For three-dimensional Bin-Packing problem a short overview of existing algorithms is given. Software for solving 1D and 2D instances with the described algorithms is provided. An algorithm for packing smaller images (textures) into a larger, resizable image (texture atlas) is implemented. Such packing of images is often used in video game development, as it speeds up the rendering process. An evaluation of implemented algorithms on randomly generated problem instances is given, accompanied by the comparative analysis of the performances of the tested algorithms