Необходимо расставить случайным образом N-ое кол-во прямоугольников на ограниченной координатной плоскости таким образом чтобы исключить пересечения. Основная трудность состоит в том, что расставлять нужно случайным образом, и при неблагоприятной расстановке все прямоугольники не влезут на плоскость чтобы не пересекать другие. Но при удачном сценарии все могут вместиться. Все прямоугольники - квадраты и имеют случайные размеры от 1x1 до 5x5. Сейчас это происходит так, что цикл (do) выбрасывает случайные координаты для каждого нового прямоугольника, и проверяет пересекаются ли они с уже созданными прямоугольника, и так до тех пор (while) пока не выпадут удачные цифры координат. Но при увеличении числа прямоугольников, может случиться что координат, не пересекающихся с другими прямоугольниками, уже не будет существовать, тогда цикл станет бесконечным и это нарушит работу скрипта. То есть прямоугольники нужно расставлять компактно, избегая ненужных "пустот" на плоскости и "экономя" место. Есть ли какой-то алгоритм который можно использовать для решения этой задачи? Один за одним от 0,0 координаты расставлять нельзя. Нужно располагать прямоугольники как можно ближе к середине плоскости. Грубо говоря требуется строить здания начиная от центра города в разные стороны, при том что город ограничен в размерах и если строить в шахматном порядке то все здания не влезут. P.S. Когда-то видел скриншоты одной программы, там прямоегольники строились отражая рамер файла, выглядело это так: может. Тут прямоугольники компактно и красиво заполняют область. Но важно, чтобы одни и те же прямоугольники располагались иначе при повторном запуске генерации, или точно так же, но как совпадение.
Не совсем. Нету иерархичности. Есть родительский прямоугольник, скажем 200x200 и внутри него нужно набросать от 50 до 100 других, разного размера от 1x1 до 5x5, как можно более компактно и близко к центру. Кроме того нужны именно координаты для каждого взятого прямоугольника.
иерархичность, как раз, так или иначе присутствует. Ведь при любом решении задачи вы же сначала ставите прямоугольник в центр плоскости, а потом достраиваете смежные (если построение города должно происходить так как вы описали). Поэтому да, как указал тов. @denis01, почему бы не решить её иерархическим деревом квадратов. Особенность дерева, как мне кажется, будет в том, что оно не будет симметричным и отдельные листочки могут в итоге не иметь дочерних, а иные будут иметь большее их количество чем другие.