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

Question

У меня есть квадрат 500 х 400 пикселей с сеткой 100 пикселей внутри.Теперь я хочу заполнить этот квадрат меньшим квадратом случайного размера, привязанным к сетке.Это означает, что квадраты меньшего размера могут иметь размер 100, 200, 300 или 400 пикселей.Их размер и положение должны быть случайными, поэтому при каждом запуске вывод будет выглядеть по-разному.

На этом изображении показан большой квадрат, его сетка и возможный вывод с меньшими квадратами, которые я пытаюсь выполнить.create.

Я генерирую это в Ruby / Sinatra с DIV, но я предполагаю, что вопрос более общий в отношении реального используемого алгоритма.

Любые предложения о том, как сделать это с наименьшим количеством кода?

Answer 1

Этот метод занял бы лот кода, но я думаю, что я бы сделал, используя алгоритм Дональда Кнута Dancing Links (DLX) (или какой-то другой алгоритм), чтобы найти все возможное расположение квадратов. Вы можете рассчитать аранжировки заранее, а затем быстро / случайно выбрать один позже, когда они вам понадобятся.

Вы можете прочитать его статью об алгоритме и его применении к пентомино (что очень похоже на вашу проблему) здесь:

http://www -cs-faculty.stanford.edu / ~ уно / документы / танцы-color.ps.gz

http://en.wikipedia.org/wiki/Dancing_Links

Answer 2

Один простой рекурсивный подход, который вы могли бы использовать, который бы дал довольно хорошее случайное распределение, работает следующим образом: в качестве базового случая любая сетка размером 100x100 должна быть заполнена квадратом 100x100. В противном случае, если сетка имеет размер n x n для некоторого n, достаточно маленького, чтобы вместить квадрат, вы можете выбрать его с квадратом такого размера. В противном случае выберите сторону прямоугольника, размер которой не равен 100, выберите случайное место, кратное 100, затем разделите его пополам и рекурсивно разбейте на две половины.

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

Это может не всегда давать хорошие результаты, но код очень легко закодировать (я бы предположил, что может быть 15-25 строк кода) и его можно легко настроить, чтобы изменить вывод.

Надеюсь, это поможет!