|
|
|||||
Упаковка прямоугольников в комнате
У нас есть 2d комната определенной длинной и шириной. Также у нас есть n прямоугольников разного размера. Нужно расположить прямоугольники как можно плотнее, и их должно влезть как можно больше.
Искал способы решения, но нашел лишь такое решение, которое мне непонятно: http://www.blackpawn.com/texts/lightmaps/ Помогите или разобраться с ссылкой или же предложите свой вариант.
__________________
Humanity.push(new Man()); |
|
|||||
Регистрация: Nov 2010
Сообщений: 150
|
http://www.gamedev.ru/pages/coriolis...king_Lightmaps
Собственно перевод, если поможет. А вообще суть такая. 1. Сортируем полигоны по убыванию площади. 2. Ставил полигон в первый незанятый узел дерева, обход идет в глубину, слева направо. 3. Добавляем в дерево новый узел. Соответственно в узле хранится информация о положении и текстура. Собственно все остальное - только конкретная реализация. И конкретизируй как то вопрос, что именно непонятно. Последний раз редактировалось Stitch512; 24.01.2012 в 17:18. |
|
|||||
Про двоичную кучу. Как ею пользоваться этим массивом. Как заносить новый элемент. Как сравнивать и с чем.
__________________
Humanity.push(new Man()); |
|
|||||
Регистрация: Nov 2010
Сообщений: 150
|
Это обычное бинарное дерево, примеров реализации полно в интернете.
|
|
|||||
1. Сортируем полигоны по убыванию площади. Это обязательно? Я пропускал этот шаг и у меня не выходило ничего.
__________________
Humanity.push(new Man()); |
|
|||||
Регистрация: Nov 2010
Сообщений: 150
|
Ну без сортировки алгоритм будет работать, но плохо) Суть в том чтобы, пока больше незанятого места, вначале вставлять большие элементы, т.к. потом они могут не поместиться.
|
|
|||||
Хорошо, спасибо. А можно обойтись без бинарного дерева? Двумя массивами (с состояниями и объектами) или еще чем-нибудь...
__________________
Humanity.push(new Man()); |
|
|||||
Регистрация: Nov 2010
Сообщений: 150
|
И вообще как бы не обязательно чтобы алгоритм упаковал прям все элементы, главное получить максимальную плотность.
|
|
|||||
ну мне это и надо в большей мере.
__________________
Humanity.push(new Man()); |
|
|||||
Регистрация: Nov 2010
Сообщений: 150
|
Ну если сможешь правильно реализовать алгоритм, то ну суть что использовать, но на массивах это сложнее будет. Сама суть алгоритма в использовании бинарного дерева, если будешь реализовывать на массивах то по сути ты все равно реализуешь дерево, только менее удобным способом.
|
Часовой пояс GMT +4, время: 16:11. |
|
« Предыдущая тема | Следующая тема » |
Опции темы | |
Опции просмотра | |
|
|