Как случайно разместить объекты в плоскости?

Question

[satahippy]

Задача: случайно разместить объекты в плоскости (пространстве), так, чтобы они не пересекались.
Объекты разных размеров. подскажите, как это можно сделать? Есть какие-нибудь алгоритмы?

Comments

[0re1]

Если количество/размер объектов достаточно мало по отношению к размеру плоскоси, то можно многократно случайно размещать объекты в плоскости до тех пор пока они не перестанут пересекаться. Либо поочередно укладывать объекты на плоскость в случайные позиции в которых они не пересекаются с предыдущими.

[satahippy]

@0re1 всё так. но объектов много относительно размеров плоскости

Answer 1

[Андрей]

Если у Вас есть риск, что из-за высокой плотности заполнения возникает проблема уместить все объекты, то это "3D bin packing problem". Задача NP-полная, материалов по ее решениям много - в основном эвристики.
Масса идей есть вот здесь.
После плотной упаковки (когда первая часть задачи "поместить всё" - решена) можете "порастаскивать" случайным образом объекты чтобы придать хаотичность.

Comments

[satahippy]

спасибо, интересный метод

Answer 2

[Михаил Алексеев]

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

Comments

[satahippy]

ок, их и предполагалось вписывать в параллелепипеды

я не про определение пересечений, а об алгоритме случайного размещения этих параллелепипедов

[Михаил Алексеев]

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

[satahippy]

да, сейчас примерно так и происходит, только это не самый хороший вариант

при таком раскладе либо долго отрабатываться будет (если объектов много и все они должны быть размещены), либо будет теряться часть объектов