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

@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
индекса (по сути местоположение прямоугольника)
Кроме того Вы можете контролировать заполненность
исходного прямоугольника, вычисляя количество
ненулевых элементов матрицы.

Новые блоги и статьи Все статьи Все блоги /
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .

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

	Разместить прямоугольники внутри прямоугольника 29.01.2016, 17:43. Показов 25266. Ответов 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

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

Решение