Как случайно расположить прямоугольник с минимальным перекрытием и хорошей дисперсией

Question

Я бы хотел поместить произвольное количество прямоугольников в родительский элемент фиксированного размера, так чтобы они были:

1. Случайно размещенный
2. Случайно повернут с точностью до заданного диапазона градусов
3. Красиво рассредоточены по центральной точке (не все сгруппированы в один угол)
4. Не перекрывается без необходимости из-за недостатка места
5. С минимальным перекрытием, когда это необходимо

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

Поиск в Google привел меня к созданию различных алгоритмов упаковки и т. Д., Но на самом деле ничто не отвечает моим требованиям.

У кого-нибудь есть хорошие идеи?

Answer 1

Это не должно быть намного сложнее, чем:

1. Поместите новый прямоугольник в случайное место со случайным вращением. Это следует сделать, просто используя три случайных значения (x, y, r), если только вам не нужен случайный размер (в этом случае вам также понадобятся w и h). Это не должно приводить к сбою углов (случайным является случайный).
2. Для каждого уже размещенного прямоугольника проверьте наличие столкновений. Вот один из способов. Также проверьте наличие столкновений со стороной окна (если вы не хотите, чтобы объекты выходили за пределы экрана); размещение четырех фиктивных прямоугольников вокруг границы может быть дешевым способом сделать это.
3. Если есть какие-либо столкновения, то есть два варианта: либо переместить новый прямоугольник в новое случайное место, либо переместить новый прямоугольник и блокирующий прямоугольник друг от друга, пока они больше не соприкасаются. И то, и другое имеет и «да», и «нет» - перемещение нового происходит быстрее и проще, хотя, возможно, он не найдет место, которое подходит, если страница действительно заполнена; перемещение обоих почти наверняка будет успешным, но это займет больше времени и может привести к столкновениям с цепной реакцией, которые должны были бы быть отсортированы рекурсивно.

В любом случае вы захотите сохранить небольшое количество прямоугольников, потому что количество сравнений может быстро стать действительно большим. Использование короткого замыкания (например, «если они находятся на полпути по экрану, тогда не пытайтесь внимательно посмотреть») может помочь, но не гарантировано.

РЕДАКТИРОВАТЬ: Хорошо, поэтому требование № 5. Скорее всего, рекурсивный метод добавления новых прямоугольников методом push-оба-прямоугольника до тех пор, пока он не перестанет сталкиваться, окажется самым простым способом сделать это - просто обрезать цикл после нескольких тысяч итераций, и все будет пытались отойти как можно дальше от всего остального, оставляя минимальное перекрытие. Или оставьте метод запущенным в отдельном потоке, чтобы пользователь мог видеть, как они растекаются по мере добавления новых (также не давая ему выглядеть так, будто он блокируется, пока думает), останавливаясь, когда ни один прямоугольник не переместился больше, чем на X единиц в одном итерации.

Answer 2

Как насчет этого?Рассмотрим прямоугольники, которые вы должны поместить в форме заряженных частиц, которые отталкиваются друг от друга и также отталкиваются от стенок контейнера.Вы можете начать с (случайного) распределения их (и присвоения им случайных углов) в контейнере, а затем запустить симуляцию, в которой каждая «частица» движется в ответ на силы, действующие на нее (углы будут меняться в соответствии с моментами вращения этих сил).Остановитесь, когда вы нажмете конфигурацию в пределах ваших допусков.

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

Answer 3

Я не понимаю требования 2. Вы говорите, что сами прямоугольники вращаются вокруг центральной точки прямоугольника или что прямоугольники покрывают только часть 360-градусного круга вокруг центральной точки всех прямоугольников.

Я не уверен, что случайный путь - это путь.

Просто разделите желаемое количество прямоугольников на 360 градусов. Это количество градусов для смещения каждого прямоугольника при его рисовании. Это должно охватывать требования 3, 4 и 5.