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

@Fennec · Регистрация: 10.02.2010

Студворк — интернет-сервис помощи студентам

Привет!

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

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

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

Чтобы был ясен контекст задачи - я расставляю в случайные места карты домики, соотвествкенно после постановки одного, мне нужно узнать куда я могу поставить новый.

@Fennec · 30.01.2016, 22:35 **[ТС]**

Сообщение от Excalibur921

Проценты.

Что вы вкладываете в эти проценты?

Сообщение от Excalibur921

Не две а новую ячейку для дома. Адаптивная рекурсия.

так и не понял откуда должна появиться новая ячейка. Где как и какого размера вы собираетесь генерировать новую ячейку?

Сообщение от Excalibur921

Не проще нарисовать?

уже нарисовал аж 14 раз

Сообщение от Excalibur921

И ненужно, генератор заполнит достаточно плотно.

Не нужно плотно. Нужно произвольно.

Сообщение от Excalibur921

Так… давайте перефразируем. Вам не нравится простое решение, не хотите его улучшить и продумать нюансы и варианты.

Это не простое решение. Это решение не соответствующее условиям. Это решение для другой задачи.

Приведу цитату из задания

разместить в произвольное свободное место

Это значит что там где стык у ваших двух областей вы ТЕХНИЧЕСКИ НЕ МОЖЕТЕ поставить домик с таким алгоритмом. Вы задаете дополнительные ограничения системе, что прямо противоречит задаче ПРОИЗВОЛЬНОГО размещения.

Еще раз - если вы пытаетесь разместить что-то на сетке из непересекающихся прямоугольников - вы получаете эту проблему. Я уже не знаю как еще объяснить.

@Igor3D · 31.01.2016, 07:01

Сообщение от Fennec

Методы разрешения коллизий для начала могут выталкивать объект не в том направлении (например в сторону с еще большим количеством препятствий или вообще за края области) либо даже если направление будет выбрано верное необходимо будет сделать огромное количество проверок в случае если мы будет пытаться поставить новый прямоугольник в самый низ этого полузаполненного сосуда. Тем более, если руководствоваться именной идеей физических движков, то они обычно работают так, что будут пытаться растолкнуть объекты вокруг свеже созданного, чего мне совсем не хотелось бы.

Насколько я понял, идея в следующем

- накидать пр-ков "как получится" и определить правила взаимодействия (напр притяжение/отталкивания)

- запустить симуляцию, т.е сделать N шагов, каждый пр-к будет смещаться согласно правилам и в конце-концов система "само-сбалансируется"

Если так, то нечто подобное я недавно делал, и, к моему удивлению, ожидаемого "провала по скорости" не последовало

Но устраивает ли Вас это? Ведь такая расстановка совсем не "последовательная"

@Fennec · 31.01.2016, 12:18 **[ТС]**

Тут все бы хорошо, только вот в задании говорится, что карту нужно не только сгенерировать, но и уметь в рантайме поставить домик на свободное место. В итоге я сейчас использую совсем плохое решение - тыкаю "пальцем в небо" и смотрю, можно ли было туда поставить домик или нет, если нет, то следует еще один тычок в случайное место и так до тех пор, пока свободное место не будет найдено. Ну или не пройдет 100 попыток.

@Igor3D · 31.01.2016, 13:11

Сообщение от Fennec

Тут все бы хорошо, только вот в задании говорится, что карту нужно не только сгенерировать, но и уметь в рантайме поставить домик на свободное место. В итоге я сейчас использую совсем плохое решение - тыкаю "пальцем в небо" и смотрю, можно ли было туда поставить домик или нет, если нет, то следует еще один тычок в случайное место и так до тех пор, пока свободное место не будет найдено. Ну или не пройдет 100 попыток.

Я бы не назвал это совсем плохим решением. Смущает баланс цель/средства - писать достаточно сложный алгоритм лишь для того чтобы... случайно поставить пр-к.

Хорошо, вернемся к Вашей постановке. Я пытался вспомнить как я действовал, но это было неск лет назад, все очень смутно. Я хранил "уголки" - пр-ков, но не все и не только. Базовый алгоритм примерно такой.

- берем уголок у которого есть свободная область справа и/или снизу. Находим все уголки образующие с ним пр-к не содержащий др уголков. Все это быстрые операции по 2 сортированным контейнерам.

Дальше я пытался "расширять" найденный пр-к так и сяк, но это хлопотливо и найденные пр-ки повторяются. Правильно взять "хорошие" уголки. Словами затрудняюсь объяснить, см аттач. Точка A - вроде бы "уголок", но на деле выясняется что нет, "правильный" уголок A1 (хотя он вовсе не уголок пр-ка). Поэтому сначала нужно отбросить ненужные уголки и добавить новые, а потом просто "брать пары" (базовый алгоритм). Дальше - ниче не помню

@Excalibur921 · 31.01.2016, 16:44

Покажите часть карты которую рисовали.

@Fennec · 31.01.2016, 17:04 **[ТС]**

окей, спасибо!

Видимо все-таки дальше решение на мне

echs · 02.02.2016, 11:26

Fennec
А почему бы вам не задать числовую матрицу.
0 - клетка свободна. 1 - клетка занята
Имея матрицу несложно определить и прямоугольник
нужного вам размера, если таковой существует.
Все просто. Вы берете в матрице нулевой элемент и
начинаете присоединять к нему со всех четырех сторон
свободные клетки (строки и столбцы), если таковые
имеются в наличии. В конечном счете вы получите 4
индекса (по сути местоположение прямоугольника)
Кроме того Вы можете контролировать заполненность
исходного прямоугольника, вычисляя количество
ненулевых элементов матрицы.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@Fennec 1 / 1 / 0 Регистрация: 10.02.2010 Сообщений: 36

	Разместить прямоугольники внутри прямоугольника 29.01.2016, 17:43. Показов 25326. Ответов 26 Метки нет (Все метки) Привет! Решаю следующую задачу: есть прямоугольная область определенных размеров, в нее нужно добавлять в случайные места другие прямоугольники, так, чтобы они не вылезали за пределы области и не наползали друг на друга. Пожалуйста, обратите внимание, что это НЕ задача о ранце, мне НЕ нужно набить как можно больше прямоугольников в наименьшую площадь. Задача в том, чтобы после постановки очередного прямоугольника в область разбить ее на свободные прямоугольные подобласти. Приложил иллюстрацию к тому что хочу сделать. 1) Пустое поле 2) Поставили прямоугольник в ПРОИЗВОЛЬНОЕ место Области A, B, C, D (да, они ПЕРЕСЕКАЮТСЯ) обозначают места, в которые можно поставить новый прямоугольник площадью меньшей чем площадь этой области. Чтобы был ясен контекст задачи - я расставляю в случайные места карты домики, соотвествкенно после постановки одного, мне нужно узнать куда я могу поставить новый. Миниатюры 0

@Fennec 1 / 1 / 0 Регистрация: 10.02.2010 Сообщений: 36
	31.01.2016, 12:18 [ТС]
	Тут все бы хорошо, только вот в задании говорится, что карту нужно не только сгенерировать, но и уметь в рантайме поставить домик на свободное место. В итоге я сейчас использую совсем плохое решение - тыкаю "пальцем в небо" и смотрю, можно ли было туда поставить домик или нет, если нет, то следует еще один тычок в случайное место и так до тех пор, пока свободное место не будет найдено. Ну или не пройдет 100 попыток. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	31.01.2016, 16:44
	Покажите часть карты которую рисовали. 0

@Fennec 1 / 1 / 0 Регистрация: 10.02.2010 Сообщений: 36
	31.01.2016, 17:04 [ТС]
	окей, спасибо! Видимо все-таки дальше решение на мне 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	02.02.2016, 11:26
	Fennec А почему бы вам не задать числовую матрицу. 0 - клетка свободна. 1 - клетка занята Имея матрицу несложно определить и прямоугольник нужного вам размера, если таковой существует. Все просто. Вы берете в матрице нулевой элемент и начинаете присоединять к нему со всех четырех сторон свободные клетки (строки и столбцы), если таковые имеются в наличии. В конечном счете вы получите 4 индекса (по сути местоположение прямоугольника) Кроме того Вы можете контролировать заполненность исходного прямоугольника, вычисляя количество ненулевых элементов матрицы. 0

Опции темы

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

Решение