случайное размещение прямоугольников без наложений

Question

Я ищу звуковой алгоритм, который бы произвольно помещал заданное количество прямоугольников одинакового размера в больший прямоугольник (холст).

Я вижу два способа сделать это:

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

2. использовать сетку и размещать прямоугольники в ячейках случайным образом.Это все еще может выглядеть как размещение сетки.Мне тоже это не нравится.

есть ли лучшие способы сделать это?«лучше» означает более эффективный или более визуально «случайный», чем сеточный подход.лучше в любом отношении.

Answer 1

Вот простая эвристика. Это будет непересекающимся и случайным.

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

Вы можете попробовать разные стратегии. Вы можете попытаться поместить прямоугольники близко к углам. Или вы можете разместить их вокруг центра регионов. Мы не можем обсуждать оптимальность, потому что вы ввели случайность.

Answer 2

Я создаю внутренние комнаты, похожие на подземелья, используя следующий метод.

1) Разбросать N точек случайным образом, но не в нескольких пикселях друг от друга. 2) Для каждой точки по очереди расширьте, если это возможно, во всех четырех направлениях. прекращение расширяется, если вы нажмете другой прямоугольник. 3) Прекратите алгоритм, когда комнаты не могут расширяться.

В результате получается N прямоугольников с небольшим количеством прямоугольников.

Код находится в библиотеке двоичных изображений

https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/dungeongenerator3.c #

Answer 3

Вы можете найти Quadtrees или R-деревья полезными для вашей цели.