Упаковка пачки прямоугольников в прямоугольник

• Описываемая вами задача - это вариация Bin Packing Problem, для которой доказана ее NP-полнота.

Соответственно, из теории алгоритмов напрямую следует, что задача о проверке того, поместятся ли ваши {rect(w, h)} внутрь RECT(W, H) — тоже NP-полная.

• Более того, применение эвристики в этом случае не гарантирует того, что ответ "да / нет" сохранится для исходной задачи, т.е. тот факт, что эвристический алгоритм не смог найти способа упаковки {rect(w, h)} в RECT(W, H) не гарантирует того, что этого способа не существует.

В связи с этим, если говорить формально, единственный способ точного решения поставленной задачи - это взять какой-нибудь точный алгоритм со сложностью O(2^n) и совершить проверку с его помощью.

• На практике (а вы наверняка пакуете текстуры / спрайты), думаю, можно каким-то образом прикрутить эвристический алгоритм(ы) и действительно смотреть на fill rate — все-таки мы имеем дело с NP-полнотой.

• В плохом случае для конкретной эвристики вы получите неоптимальное разбиение, что, в общем-то, кажется мне не слишком критичным. Ну да, не получилось сэкономить 20 пикселей в файле с запакованными текстурами, ничего страшного.

• Вот еще один неплохой референс по теме, который мне удалось найти.