|
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Размещение прямоугольников на поле
Привет. Тут такая задача: есть прямоугольное поле и в него надо суметь сложить некоторое количество прямоугольников так, чтобы они друг на друга не накладывались и а края не вылезали. Посмотрел тут алгоритмы упаковки, задачу о ранце и пр. - не похоже на то что нужно.
Мое предположение: при каждой постановке прямоугольника в области создавать список свободных прямоугольных областей. При постановке следующего, перебирать список полученных областей, в поисках той, чья площадь больше, либо равна площади устанавливаемого прямоугольника и переразбивать на области еще раз. Надо велосипед изобретать или есть уже готовые алгоритмы? |
|
|||||
Регистрация: Apr 2009
Сообщений: 409
|
да, идея правильная. алгоритмов упаковки атласов много гуглится, вот первый http://gamedevblogs.ru/blog/actionscript/906.html
это самый простой, есть и более продвинутые |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Но мне не атласы паковать ) мне надо на рандом натыкать домиков на карту ) Ну, то есть мне нет необходимости оптимально их ужать, нужно чтобы они просто поместились друг друга не перекрывая
|
|
|||||
Тут описан интересный способ расположить прямоугольники на карте.
https://habrahabr.ru/post/275727/
__________________
Гоночка |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Похоже плохо выразил мысль (
В общем, смотрите, есть какая-то ограниченная прямоугольная область. Есть прямоугольные домики, различных соотношений сторон. Задача в том, чтобы случайным образом расположить эти домики, но так, чтобы они не вылезли за пределы и не пересекали друг друга. По моему алгоритму у меня появились еще пара дополнений (пока не знаю насколько соответствующих реальной жизни). Я предполагаю, что каждый прямоугольник разбивает пространство вокруг не более чем на четыре прямоугольные области (слева, справа, сверху, снизу), ограниченные близлежащими прямоугольниками. На 1000 прямоугольников это будет уже 4000 областей, многие из которых вероятно будут дублировать друг друга. Поиски ближайших скорее всего потребуют работы по написанию двоичного дерева (чего мне хотелось бы избежать), плюс, мне кажется, что должен существовать какой-то механизм вставки, чтобы не перерасчитывать все-все области по новой, но у меня абсолютно 0 идей о том как это воплотить. Мне кажется это задача лежащая где-то в области графов, но я очень плохо с ними знаком и даже не знаю в какую сторону посмотреть. |
|
|||||
Попробуйте погуглить по запросу "Texture atlas algorithm".
Вот например: http://gamedev.stackexchange.com/que...king-algorithm
__________________
Дети не должны знать о своих родителях |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Господа, еще раз, задача НЕ на упаковку. Я вот даже иллюстрацию прикрепил.
1) Пустое поле 2) Поставили прямоугольник в ПРОИЗВОЛЬНОЕ место Области A, B, C, D (да, они ПЕРЕСЕКАЮТСЯ) обозначают места, в которые можно поставить новый прямоугольник площадью меньшей чем площадь этой области. Так вот, вопрос о том, как найти эти области наименьшими затратами. НЕ О ТОМ как упаковать сами прямоугольники таким образом, чтобы они занимали наименьшую площадь. |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Еще раз привет, в этот раз я пришел к вам с более продуманным планом и более аккуратными картинками.
Вот как я вижу выполнение алгоритма (пока руками) 1) пустое поле 2) поставили новый прямоугольник 3) рассчитали 4 такие области в которых можно расположить новые прямоугольники в любом свободном месте 4) поставили новый прямоугольник 5) определили с какими уже существующими областями он пересекается и удалили эти области 6) рассчитали 5 новых областей в которых можно расположить новые прямоугольники в любом свободном месте Собственно у меня вызывают вопросы пункты 3 и 6, потому что я не знаю КАК рассчитать эти области. То есть я не могу пока придумать алгоритм, который рассчитывал бы эти цветные области. Последний раз редактировалось Фенёк; 30.01.2016 в 17:39. |
|
|||||
Вообщем, что то такое я набросал, вариант правда далёк от завершения.
Думаю, сперва лучше забить всё поле квадратами, а затем для каждой из сторон искать свободную площадь. В примере ищется площадь для верхней стороны квадратов. Клик мышки - обновить: Код: 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; } */ } }
__________________
Дети не должны знать о своих родителях |
|
|||||
Регистрация: May 2011
Сообщений: 221
|
Ого! Вам было не влом поковыряться с вопросом! Да, пожалуй пока не совсем то, но похоже на движение в правильную строну. Спасибо! Попробую покопать в эту сторону
|
Часовой пояс GMT +4, время: 10:59. |
|
« Предыдущая тема | Следующая тема » |
|
|