Нарисуйте n одинаковых кругов без наложения и центра тяжести

Question

Я смотрел на набор из 100 слайдов PowerPoint, которые имеют красные круги одинакового размера, причем первый слайд имел 1 кружок, а 100-й слайд имел 100 кружков.На каждом слайде круги не перекрываются, и, хотя они расположены почти случайно, они имеют тенденцию тяготеть к центру и не слишком близко друг к другу (я не вижу экстремальных выбросов).Вы можете сами посмотреть слайды здесь ).

Они, кажется, были созданы вручную (что, должно быть, заняло очень много времени!), И я задумался оКак лучше всего было бы программно создать что-то вроде этого (интересная проблема с игрушкой - автоматизировать скучные вещи)?

Я думал так:

Для каждого слайда до nкруги:

1. Создание координат для круга в произвольной точке на холсте.
2. Рассчитайте больший диаметр (для некоторого значения большего) для этого круга и всех других, уже находящихся на холсте, и убедитесь, что новый круг не перекрывается с какими-либо существующими кругами, используя вычисленные большие диаметры (чтобы остановить кругибыть слишком близко друг к другу).Двигайтесь дальше, если все в порядке, в противном случае начинайте снова с 2. 2. 1014 *
3. Чтобы остановить выбросы, сделайте какую-нибудь проверку, чтобы убедиться, что вновь созданный круг находится не дальше, чем x на расстоянии от центров 3 (?) Существующих кругов?
4. Если все проверки сохраняются, сохраняйте новый круг и начинайте с 1, пока не наберете достаточно кругов.
5. Найдите способ сгенерировать png или что-то для каждого холста.

Также нужно было бы найти способ, по крайней мере, для первых нескольких кругов, стремящихся к центру.

Но хотя мне нравится думать о проблемах, мои кодировки должны работать и должен быть какой-то отличный алгоритмили что-то для того, чтобы сделать это правильно?

Рад за любые указатели или за то, чтобы кто-то смог это сделать - особенно хотел бы почитать некоторые реализации на python, чтобы поучиться у них.

[Я знаю, что это можетне совсем подходит для стиля StackOverflow, но не уверен, куда еще обратиться, чтобы получить идеи по проблеме].

Answer 1

Ваши требования в основном означают, что вы хотите выбрать центры окружностей, используя выборку Пуассона:

https://www.jasondavies.com/poisson-disc/

... так что, по крайней мере, об этом много литературы.

Это дает вам все, кроме "центра тяжести".Есть несколько способов сделать это, но самый простой способ - создать круги в меньшей области, а затем растянуть края.

Например, вы можете переместить каждый круг от центраскользить так, чтобы круг на расстоянии d перемещался на расстояние d ^ 1,5 или около того.

Answer 2

Итеративное расслабление было бы обычным подходом к чему-то подобному.

По сути, вы начинаете со случайного размещения n кружков.Затем вы делаете несколько итераций, чтобы попытаться переместить круги в более приятную конфигурацию.

Для каждого круга C вы измеряете расстояние до других кругов, а для каждого круга рассчитываете силу C, которая отталкивает C от этого другого круга.Направление силы будет противоположно направлению к другому кругу, а величина будет, как правило, обратно пропорциональна расстоянию.(Таким образом, сила будет вести себя подобно гравитации, но в противоположном направлении.) Вы суммируете все силы на C, аналогично суммируете силы на всех других кругах, а затем немного перемещаете каждый круг, основываясь на общей силе наЭто.(Вам также понадобится сила, удерживающая круги от краев.) Это одна итерация, и после этого круги должны быть в немного лучшей конфигурации, чем они были раньше.

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

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