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

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

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 28.01.2016, 21:07
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 1  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Question Размещение прямоугольников на поле

Привет. Тут такая задача: есть прямоугольное поле и в него надо суметь сложить некоторое количество прямоугольников так, чтобы они друг на друга не накладывались и а края не вылезали. Посмотрел тут алгоритмы упаковки, задачу о ранце и пр. - не похоже на то что нужно.

Мое предположение: при каждой постановке прямоугольника в области создавать список свободных прямоугольных областей. При постановке следующего, перебирать список полученных областей, в поисках той, чья площадь больше, либо равна площади устанавливаемого прямоугольника и переразбивать на области еще раз.

Надо велосипед изобретать или есть уже готовые алгоритмы?

Старый 28.01.2016, 21:21
faraday вне форума Посмотреть профиль Отправить личное сообщение для faraday Найти все сообщения от faraday
  № 2  
Ответить с цитированием
faraday
 
Аватар для faraday

Регистрация: Apr 2009
Сообщений: 409
да, идея правильная. алгоритмов упаковки атласов много гуглится, вот первый http://gamedevblogs.ru/blog/actionscript/906.html
это самый простой, есть и более продвинутые

Старый 28.01.2016, 21:29
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 3  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Но мне не атласы паковать ) мне надо на рандом натыкать домиков на карту ) Ну, то есть мне нет необходимости оптимально их ужать, нужно чтобы они просто поместились друг друга не перекрывая

Старый 28.01.2016, 21:51
Alex Lexcuk вне форума Посмотреть профиль Отправить личное сообщение для Alex Lexcuk Посетить домашнюю страницу Alex Lexcuk Найти все сообщения от Alex Lexcuk
  № 4  
Ответить с цитированием
Alex Lexcuk

блогер
Регистрация: Mar 2008
Адрес: Донецк_city
Сообщений: 1,094
Записей в блоге: 5
Тут описан интересный способ расположить прямоугольники на карте.
https://habrahabr.ru/post/275727/
__________________
Гоночка

Старый 29.01.2016, 10:48
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 5  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Похоже плохо выразил мысль (

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

По моему алгоритму у меня появились еще пара дополнений (пока не знаю насколько соответствующих реальной жизни).

Я предполагаю, что каждый прямоугольник разбивает пространство вокруг не более чем на четыре прямоугольные области (слева, справа, сверху, снизу), ограниченные близлежащими прямоугольниками. На 1000 прямоугольников это будет уже 4000 областей, многие из которых вероятно будут дублировать друг друга. Поиски ближайших скорее всего потребуют работы по написанию двоичного дерева (чего мне хотелось бы избежать), плюс, мне кажется, что должен существовать какой-то механизм вставки, чтобы не перерасчитывать все-все области по новой, но у меня абсолютно 0 идей о том как это воплотить.

Мне кажется это задача лежащая где-то в области графов, но я очень плохо с ними знаком и даже не знаю в какую сторону посмотреть.

Старый 29.01.2016, 10:52
Tails вне форума Посмотреть профиль Отправить личное сообщение для Tails Найти все сообщения от Tails
  № 6  
Ответить с цитированием
Tails
 
Аватар для Tails

блогер
Регистрация: Dec 2008
Адрес: г. Чебоксары
Сообщений: 2,259
Записей в блоге: 6
Попробуйте погуглить по запросу "Texture atlas algorithm".
Вот например: http://gamedev.stackexchange.com/que...king-algorithm
__________________
Дети не должны знать о своих родителях

Старый 29.01.2016, 11:33
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 7  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Господа, еще раз, задача НЕ на упаковку. Я вот даже иллюстрацию прикрепил.

1) Пустое поле
2) Поставили прямоугольник в ПРОИЗВОЛЬНОЕ место

Области A, B, C, D (да, они ПЕРЕСЕКАЮТСЯ) обозначают места, в которые можно поставить новый прямоугольник площадью меньшей чем площадь этой области.

Так вот, вопрос о том, как найти эти области наименьшими затратами. НЕ О ТОМ как упаковать сами прямоугольники таким образом, чтобы они занимали наименьшую площадь.
Миниатюры
Нажмите на изображение для увеличения
Название: Untitled-1.png
Просмотров: 68
Размер:	31.4 Кб
ID:	32000  

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

Регистрация: May 2011
Сообщений: 221
Еще раз привет, в этот раз я пришел к вам с более продуманным планом и более аккуратными картинками.

Вот как я вижу выполнение алгоритма (пока руками)

1) пустое поле
2) поставили новый прямоугольник
3) рассчитали 4 такие области в которых можно расположить новые прямоугольники в любом свободном месте
4) поставили новый прямоугольник
5) определили с какими уже существующими областями он пересекается и удалили эти области
6) рассчитали 5 новых областей в которых можно расположить новые прямоугольники в любом свободном месте

Собственно у меня вызывают вопросы пункты 3 и 6, потому что я не знаю КАК рассчитать эти области. То есть я не могу пока придумать алгоритм, который рассчитывал бы эти цветные области.
Миниатюры
Нажмите на изображение для увеличения
Название: 3.jpg
Просмотров: 45
Размер:	135.7 Кб
ID:	32002  


Последний раз редактировалось Фенёк; 30.01.2016 в 17:39.
Старый 31.01.2016, 14:36
Tails вне форума Посмотреть профиль Отправить личное сообщение для Tails Найти все сообщения от Tails
  № 9  
Ответить с цитированием
Tails
 
Аватар для Tails

блогер
Регистрация: Dec 2008
Адрес: г. Чебоксары
Сообщений: 2,259
Записей в блоге: 6
Вообщем, что то такое я набросал, вариант правда далёк от завершения.
Думаю, сперва лучше забить всё поле квадратами, а затем для каждой из сторон искать свободную площадь. В примере ищется площадь для верхней стороны квадратов.

Клик мышки - обновить:
Test.swf   (1.5 Кб)


Код:
Код AS3:
package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.geom.Rectangle;
 
 
	/**
	 * Тест.
	 * @author Tails
	 */
	public class Main extends Sprite {
 
		// Приват
		private var _quadsTotal:uint;						// Количество квадратов.
		private var _space:Rectangle;						// Размер мира.
		private var _sprite:Sprite;							// Рисунок результата.
		private var _quads:Vector.<Rectangle>;				// Рассекающие квадраты.
		private var _result:Vector.<Rectangle>;				// Полученные области.
 
 
		public function Main() {
			if (stage === null)
				addEventListener(Event.ADDED_TO_STAGE, init);
			else
				init();
		}
		private function init(e:Event = null):void {
			removeEventListener(Event.ADDED_TO_STAGE, init);
 
			_sprite				= new Sprite;
			addChild(_sprite);
 
 
			stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
			onMouseDown();
		}
		private function onMouseDown(e:MouseEvent = null):void {
			var i:uint;
			var quad:Rectangle;
 
 
			// ГЕНЕРАЦИЯ МИРА
			// Общие параметры и свойства:
			_quadsTotal			= 5;
			_space				= new Rectangle(100, 100, 400, 300);
			_quads				= new Vector.<Rectangle>;
			_result				= new Vector.<Rectangle>;
 
			// Создаём рассекающие квадраты:
			i					= 0;
			while (i < _quadsTotal) {
				_quads[i]		= createRandomQuad();
				i ++;
			}
 
			//_quads.push(new Rectangle(200, 10, 10, 200));
			//_quads.push(new Rectangle(300, 150, 50, 30));
 
			// АЛГОРИТМ
			// Обходим каждую сторону получившегося квадрата, 
			// формируя прямоугольник свободного пространства:
			i					= _quadsTotal;
			while (i--) {
 
				// Получаем область для каждой стороны. (Может быть null, если области не существует)
				// Верхняя сторона:
				quad			= getFreeSpaceForTop(_quads[i]);
				if (quad !== null)
					_result.push(quad);
			}
 
 
			// РЕНДЕР.
			// Рисунок:
			_sprite.graphics.clear();
			_sprite.x			= _space.x;
			_sprite.y			= _space.y;
			addChild(_sprite);
 
			// Мир:
			_sprite.graphics.lineStyle(1, 0x999999);
			_sprite.graphics.drawRect(0, 0, _space.width, _space.height);
 
			// Результат:
			i					= _result.length;
			while (i--) {
				quad			= _result[i];
				_sprite.graphics.lineStyle(1, Math.random() * 0xcccccc);
				_sprite.graphics.drawRect(quad.x, quad.y, quad.width, quad.height);
			}
 
			// Квадраты:
			i					= _quadsTotal;
			_sprite.graphics.lineStyle(1, 0x0);
			_sprite.graphics.beginFill(0, 1);
			while (i--) {
				quad			= _quads[i];
				_sprite.graphics.drawRect(quad.x, quad.y, quad.width, quad.height);
			}
		}
 
 
		// ПРИВАТ
		private function createRandomQuad():Rectangle {
			const minSize:uint				= 10;		// Минимальный размер стороны квадрата.
			const maxSize:uint				= 50;		// Максимальный.
			const quad:Rectangle			= new Rectangle();
 
			quad.width			= Math.round(Math.random() * (maxSize - minSize) + minSize);
			quad.height			= Math.round(Math.random() * (maxSize - minSize) + minSize);
			quad.x				= Math.round(Math.random() * (_space.width - quad.width));
			quad.y				= Math.round(Math.random() * (_space.height - quad.height));
 
			return quad;
		}
		private function getFreeSpaceForTop(currentQuad:Rectangle):Rectangle {
			var i:uint;
			var quad:Rectangle;
			var free:Rectangle;
			var value:Number;
			var dx:Number;
			var dy:Number;
 
 
			// Получаем свободную область для верхней стороны.
			// Получаем будущий прямоугольник области:
			free				= new Rectangle(0, 0, _space.width, _space.height - (_space.height - currentQuad.y));
 
			// Обходим все имеющиеся прямоугольники:
			i					= _quadsTotal;
			while (i--) {
				quad			= _quads[i];
 
				// Проверка сама с собою пропускается:
				if (quad === currentQuad)
					continue;
 
				// Пересечение свободной области с квадратом.
				// Глубина пересечения по X:
				if (quad.x > free.x)
					dx			= free.x - quad.x + free.width;
				else
					dx			= quad.x - free.x + quad.width;
 
				// Глубина пересечения по Y:
				if (quad.y > free.y)
					dy			= free.y - quad.y + free.height;
				else
					dy			= quad.y - free.y + quad.height;
 
				// Обрезание по Y:
				if (dy > 0) {
					if (dx > 0) {
 
						// Есть пересечение.
						// Проверка типа пересечения, оно может быть частичным или сквозным:
						if (dy < free.height) {
 
							// Частичное пересечение.
							// Выбираем способ обрезания:
							if (quad.y > free.y) {
 
								// Блок ниже нас.
								// В зависимости от его расположения, обрезаемся справа или cлева:
								if (quad.x > currentQuad.x) {
									free.width			-= dx;
								}
								else {
									value				= quad.x + quad.width;
									if (value > free.x) {
										free.x			= value;
										free.width		= dx - quad.width;
									}
								}
							}
							else {
 
								// Блок выше нас.
								// Просто обрезаемся на величину пересечения:
								free.y			+= dy;
								free.height 	-= dy;
							}
						}
						else {
 
							// Сквозное пересечение.
							continue;
						}
					}
 
					// Нет пересечения по X.
					continue;
				}
 
				// Нет пересечения по Y.
				continue;
			}
 
			return free;
		}
		/*
		private function hitTest(a:Rectangle, b:Rectangle):Boolean {
			var value:Number;
 
 
			// Проверка пересечеения двух прямоугольников.
			// Приводим обоих в одну точку отсчёта, добавляя разницу к ширине и высоте.
 
			// Проверка пересечения по X:
			if (a.x > b.x)
				value			= b.x - a.x + b.width;
			else
				value			= a.x - b.x + a.width;
 
			if (value < 0)
				return false;
 
			// Проверка пересечения по Y:
			if (a.y > b.y)
				value			= b.y - a.y + b.height;
			else
				value			= a.y - b.y + a.height;
 
			if (value < 0)
				return false;
 
			// Блоки пересекаются:
			return true;
		}
		*/
	}
}
Вложения
Тип файла: swf Test.swf (1.5 Кб, 104 просмотров)
__________________
Дети не должны знать о своих родителях

Старый 31.01.2016, 18:16
Фенёк вне форума Посмотреть профиль Отправить личное сообщение для Фенёк Найти все сообщения от Фенёк
  № 10  
Ответить с цитированием
Фенёк

Регистрация: May 2011
Сообщений: 221
Ого! Вам было не влом поковыряться с вопросом! Да, пожалуй пока не совсем то, но похоже на движение в правильную строну. Спасибо! Попробую покопать в эту сторону

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

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

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


 


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


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