Идеи для алгоритма случайного распределения кругов в квадрате

Я ищу концепцию для распределения кругов в квадрате случайным образом, чтобы они не перекрывались. Все круги имеют одинаковый размер. Площадь, покрываемая кругами, может быть высокой, вплоть до теоретического максимума ок. 90% площади (в которой они полностью упорядочены). Необходимо разместить около 200 кругов, и я хочу точно указать количество кругов. (Распределение необходимо в качестве входных данных для генерации модели FE-анализа, btw)

С помощью прямого алгоритма, который последовательно размещает круги на свободном месте, невозможно охватить более 54%, что не является неожиданностью, так как в какой-то момент просто нет места. Поэтому предыдущие SO-потоки действительно не покрывают мою проблему (закрытие: Размещение случайных кругов без перекрытия (и без использования грубой силы)?

При простом случайном смещении окружностей упорядоченного множества окружностей распределение кажется "не случайным".

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

Вторая идея - симуляция бильярда: поместите все круги в любой узор и имитируйте большой бильярд. Довольно грубая сила и численно очень дорогостоящая. Я немного боюсь проблем с дескретизацией.

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

Итак - наконец - вопрос: каковы ваши предложения по решению проблемы как можно более легкие? Вы знаете алгоритмы, на которые я должен обратить внимание, чтобы решить эту проблему? Каковы ваши замечания к моим идеям?

Спасибо вам всем заблаговременно! Я очень рад прочитать ваши ответы.

Ответ 1

Начните с использования основного алгоритма, чтобы привлечь как можно больше кругов, которые не сталкиваются. Когда он заканчивается (и он не может достигать 200 кругов), начните толкать круги. Я имею в виду физически подталкивать их физическим движком: http://www.sgtconker.com/2010/09/article-xna-farseer-platform-physics-tutorial/ (без использования силы тяжести).

Ответ 2

2 идеи:

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

или

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

Ответ 3

Возможно, вы можете найти геометрическое свойство, которое верно только для 200-упаковок, а не для 199-или-менее-упаковок. Затем постепенно наращивайте упаковку, сохраняя свойство.

Например, вы можете рассмотреть несколько доступных 200-упаковок и измерить максимальное расстояние между всеми центрами окружности - m. Затем поэтапно конструируем упаковку, сохраняя m.

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

Ответ 4

Если у вас иногда будет большое количество кругов, чтобы вы были близки к максимальной упаковке, или наилучшим решением, лучше всего начать с ваших кругов, максимально упакованных в какой-то угол (который, я думаю, имеет гексагональную упаковку) и затем выполните физическое моделирование, в котором вы добавляете некоторую "температуру", то есть вы произвольно нажимаете круги и позволяете им сталкиваться в течение некоторого конечного времени.

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

Ответ 5

Предположим, вы хотите n = 200 кругов. Мое предложение состоит в том, чтобы выбрать число умеренно больше, чем n, скажем m = 300, и создать много точек в случайных местах внутри квадрата. Этот набор m точек - ваш набор кандидатов из круга. Теперь создадим граф, содержащий m вершин, по одному для каждой точки, в котором две вершины связаны ребром тогда и только тогда, когда расстояние между их точками меньше диаметра окружности - именно в этой ситуации мы были бы запрещены чтобы включить оба круга в решение, потому что они будут перекрываться.

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

К сожалению, максимальная независимая проблема с множеством NP-hard, поэтому я не знаю, будет ли это возможно решить на 300-вершинном графике. (И, в свою очередь, я не знаю, даст ли 300 случайных центров достаточную гибкость, чтобы найти 200 неперекрывающихся кругов...) Но в любом случае вы обычно решаете максимальный независимый набор одним из двух способов:

Найдите минимальное покрытие вершин, затем возьмите каждую другую вершину как максимальный независимый набор
Произведите граф дополнений (т.е. график, в котором две вершины связаны ребром тогда и только тогда, когда они не связаны ребрами в исходном графе), а затем найдите максимальная клика в этом графике

Эти страницы в Википедии содержат ссылки на документы, описывающие алгоритмы для этих проблем, которые, хотя и экспоненциально-временные, намного быстрее, чем стандартный алгоритм "полного обратного отслеживания". Необходимо иметь в виду пару вещей:

На самом деле вам не нужен доказуемо максимальный независимый набор, только один >= n. Таким образом, эвристика может быть прекрасной; обратите внимание на особенно простую эвристику для минимального покрытия вершин на странице Википедии.
Остерегайтесь различий между "максимальными" (легкими) и "максимальными" (жесткими) кликами/обложками/независимыми наборами!

Ответ 6

@toto2 @cyborg @TokenMacGuy

Update:

Я реализовал решение billard с помощью FarseerPhysicsEngine и немного поиграл с ним. В процессе реализации решения я немного изменил проблему:): Вместо того, чтобы держать все круги внутри поля, я разрешаю кругам перемещаться за пределы границы и позволять внешней части снова появляться на противоположной стороне (почти как в игра oldschool астероидов). Это делает мое распределение подходящим для бесконечного повторения в направлениях x и y, что еще лучше для основной задачи моделирования конечных элементов. Это связано с некоторыми другими проблемами, связанными с физическим моделированием, и поскольку это не было частью первоначального вопроса, я опишу только те, если кто-то особенно заинтересован.

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

Результат : он хорошо работает для большого количества кругов.

Если выполняется с небольшим количеством кругов, они имеют тенденцию склеиваться. Я не могу объяснить, почему. Возможно, что Фрейзер не моделирует столкновение как идеально эластичное, так что энергия рассеивается. Я не знаю, есть ли, и где, где есть свойство для этого. Когда я устанавливаю трение на ноль для движения, это может привести к такому кластеризации:

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

Спасибо всем за участие!! Было весело получать все ваши данные! Если у вас есть дополнительные идеи или комментарии к решению, сообщите мне.