Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 24.01.2012, 16:38
Lyso вне форума Посмотреть профиль Отправить личное сообщение для Lyso Посетить домашнюю страницу Lyso Найти все сообщения от Lyso
  № 1  
Ответить с цитированием
Lyso

Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
Отправить сообщение для Lyso с помощью Skype™
The bomb! Упаковка прямоугольников в комнате

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

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

Помогите или разобраться с ссылкой или же предложите свой вариант.
__________________
Humanity.push(new Man());

Старый 24.01.2012, 17:16
Stitch512 вне форума Посмотреть профиль Отправить личное сообщение для Stitch512 Найти все сообщения от Stitch512
  № 2  
Ответить с цитированием
Stitch512

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

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

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


Последний раз редактировалось Stitch512; 24.01.2012 в 17:18.
Старый 24.01.2012, 17:19
Lyso вне форума Посмотреть профиль Отправить личное сообщение для Lyso Посетить домашнюю страницу Lyso Найти все сообщения от Lyso
  № 3  
Ответить с цитированием
Lyso

Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
Отправить сообщение для Lyso с помощью Skype™
Про двоичную кучу. Как ею пользоваться этим массивом. Как заносить новый элемент. Как сравнивать и с чем.
__________________
Humanity.push(new Man());

Старый 24.01.2012, 17:22
Stitch512 вне форума Посмотреть профиль Отправить личное сообщение для Stitch512 Найти все сообщения от Stitch512
  № 4  
Ответить с цитированием
Stitch512

Регистрация: Nov 2010
Сообщений: 150
Это обычное бинарное дерево, примеров реализации полно в интернете.

Старый 24.01.2012, 17:22
Lyso вне форума Посмотреть профиль Отправить личное сообщение для Lyso Посетить домашнюю страницу Lyso Найти все сообщения от Lyso
  № 5  
Ответить с цитированием
Lyso

Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
Отправить сообщение для Lyso с помощью Skype™
1. Сортируем полигоны по убыванию площади. Это обязательно? Я пропускал этот шаг и у меня не выходило ничего.
__________________
Humanity.push(new Man());

Старый 24.01.2012, 17:25
Stitch512 вне форума Посмотреть профиль Отправить личное сообщение для Stitch512 Найти все сообщения от Stitch512
  № 6  
Ответить с цитированием
Stitch512

Регистрация: Nov 2010
Сообщений: 150
Ну без сортировки алгоритм будет работать, но плохо) Суть в том чтобы, пока больше незанятого места, вначале вставлять большие элементы, т.к. потом они могут не поместиться.

Старый 24.01.2012, 17:26
Lyso вне форума Посмотреть профиль Отправить личное сообщение для Lyso Посетить домашнюю страницу Lyso Найти все сообщения от Lyso
  № 7  
Ответить с цитированием
Lyso

Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
Отправить сообщение для Lyso с помощью Skype™
Хорошо, спасибо. А можно обойтись без бинарного дерева? Двумя массивами (с состояниями и объектами) или еще чем-нибудь...
__________________
Humanity.push(new Man());

Старый 24.01.2012, 17:26
Stitch512 вне форума Посмотреть профиль Отправить личное сообщение для Stitch512 Найти все сообщения от Stitch512
  № 8  
Ответить с цитированием
Stitch512

Регистрация: Nov 2010
Сообщений: 150
И вообще как бы не обязательно чтобы алгоритм упаковал прям все элементы, главное получить максимальную плотность.

Старый 24.01.2012, 17:28
Lyso вне форума Посмотреть профиль Отправить личное сообщение для Lyso Посетить домашнюю страницу Lyso Найти все сообщения от Lyso
  № 9  
Ответить с цитированием
Lyso

Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
Отправить сообщение для Lyso с помощью Skype™
ну мне это и надо в большей мере.
__________________
Humanity.push(new Man());

Старый 24.01.2012, 17:29
Stitch512 вне форума Посмотреть профиль Отправить личное сообщение для Stitch512 Найти все сообщения от Stitch512
  № 10  
Ответить с цитированием
Stitch512

Регистрация: Nov 2010
Сообщений: 150
Код AS3:
А можно обойтись без бинарного дерева? Двумя массивами (с состояниями и объектами) или еще чем-нибудь...
Ну если сможешь правильно реализовать алгоритм, то ну суть что использовать, но на массивах это сложнее будет. Сама суть алгоритма в использовании бинарного дерева, если будешь реализовывать на массивах то по сути ты все равно реализуешь дерево, только менее удобным способом.

Создать новую тему Ответ Часовой пояс GMT +4, время: 16:11.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 16:11.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.