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

У нас есть 2d комната определенной длинной и шириной. Также у нас есть n прямоугольников разного размера. Нужно расположить прямоугольники как можно плотнее, и их должно влезть как можно больше.

Искал способы решения, но нашел лишь такое решение, которое мне непонятно:
http://www.blackpawn.com/texts/lightmaps/

Помогите или разобраться с ссылкой или же предложите свой вариант.

http://www.gamedev.ru/pages/coriolis...king_Lightmaps
Собственно перевод, если поможет.
А вообще суть такая.
1. Сортируем полигоны по убыванию площади.
2. Ставил полигон в первый незанятый узел дерева, обход идет в глубину, слева направо.
3. Добавляем в дерево новый узел.

Соответственно в узле хранится информация о положении и текстура.

Собственно все остальное - только конкретная реализация.
И конкретизируй как то вопрос, что именно непонятно.

Про двоичную кучу. Как ею пользоваться этим массивом. Как заносить новый элемент. Как сравнивать и с чем.

Это обычное бинарное дерево, примеров реализации полно в интернете.

1. Сортируем полигоны по убыванию площади. Это обязательно? Я пропускал этот шаг и у меня не выходило ничего.

Ну без сортировки алгоритм будет работать, но плохо) Суть в том чтобы, пока больше незанятого места, вначале вставлять большие элементы, т.к. потом они могут не поместиться.

Хорошо, спасибо. А можно обойтись без бинарного дерева? Двумя массивами (с состояниями и объектами) или еще чем-нибудь...

И вообще как бы не обязательно чтобы алгоритм упаковал прям все элементы, главное получить максимальную плотность.

ну мне это и надо в большей мере.

Ну если сможешь правильно реализовать алгоритм, то ну суть что использовать, но на массивах это сложнее будет. Сама суть алгоритма в использовании бинарного дерева, если будешь реализовывать на массивах то по сути ты все равно реализуешь дерево, только менее удобным способом.