Как раскидать объекты по определенному объему без пересечения?
Собственно сабж: есть некий объём XYZ, и N объектов, которые должны уместиться в этом объёме. Как их раскидать рандомно так, чтобы они гарантированно не пересекались? Я придумал решение в лоб:
1) генерим рандомные координаты
2) помечаем, что эти координаты заняты
3) на следующей итерации смотрим не заняты ли координаты
4) если заняты, то повторяем всё заново
Это решение хреновое, т.к. где-то после 50 объектов комп начинает ощутимо задумываться. Можно ли как-то быстрее это сделать?
Если объекты единичного размера, то можно провести биекцию между точками в параллелепипеде объема XYZ и натуральными числами 1..XYZ, сгенерировать случайную перестановку и расставить объекты в позициях соответствующих первым N элементам перестановки. Сложность O(XYZ) и равномерное распределение.
1) генерим рандомные координаты
2) помечаем, что эти координаты заняты
3) на следующей итерации смотрим не заняты ли координаты
4) если заняты, то повторяем всё заново
Мне кажется алгоритм хороший, но допилить надо таким образом:
1) генерим рандомные координаты из всего диапазона пространства
2) помечаем, что эти координаты заняты
3) генерим рандомные координаты, при этом изключаем из диапазона рандомайза занятые точки (функцию рандома нужно составную для этого юзать)
4) если не достигли нужного количества координат, переходим на пункт 2
demolishka Хороший вариант посоветовал, более скоростной, но по моему, менее рандомайзный.
Тут вобщем ещё требования к рандомайзности процесса важны, и в часности пропорция размера пространства и размеров обьектов. Если обекты в тесном пространстве, то сильно не разрандомишся и можно выбирать из списка перестановки. Если пространство много больше размера обьектов, я бы выбрал генераицю рандомных координат.
