Поместите N кругов разных радиусов внутри большего круга без перекрытия

Ответ 1

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

Похоже, они пересекаются в центре, но они этого не делают. Я украсил функцию размещения вложенным циклом, который проверяет каждый круг на каждый другой круг (дважды) и поднимает AssertionError, если есть пересечение.

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

Идея состоит в том, чтобы смотреть только на отдельные точки, в которых может жить круг, и перебирать их с помощью следующего генератора:

def base_points(radial_res, angular_res):
    circle_angle = 2 * math.pi
    r = 0
    while 1:
        theta = 0
        while theta <= circle_angle:
            yield (r * math.cos(theta), r * math.sin(theta))
            r_ = math.sqrt(r) if r > 1 else 1
            theta += angular_res/r_
        r += radial_res

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

Я положу некоторые идеи, которые у меня есть, и сделаю это mo`bettah. Это может послужить хорошим первым шагом для идеи, основанной на физике, потому что вы начинаете без дублирования. Конечно, он может быть достаточно плотным, чтобы у вас не было много места.

Кроме того, я никогда не играл с numpy или matplotlib, поэтому я пишу только ванильный python. Там может быть что-то, что заставит его работать намного быстрее, мне придется посмотреть.

Ответ 2

Не решение, а просто идея мозгового штурма: IIRC - один из распространенных способов получить приблизительные решения для TSP - это начать с произвольной конфигурации, а затем применить локальные операции (например, "обменивать" два ребра на пути), чтобы попытаться получить более короткие и короткие пути. (ссылка Википедии)

Я думаю, что что-то подобное можно было бы здесь:

• Начните со случайных позиций в центре.
• "Оптимизируйте" эти позиции, поэтому нет перекрывающихся кругов, поэтому круги максимально приближены, увеличивая расстояние между перекрывающимися кругами и уменьшая расстояние между другими кругами, пока они не будут плотно упакованы. Это может быть сделано путем минимизации энергии, или может быть более эффективное жадное решение.
• Примените оператор итерационного улучшения к центральным позициям
• Перейти к 2, прорваться после максимального количества итераций или если последняя итерация не нашла улучшения

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

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

Другие возможные операции, о которых я мог подумать:

• Возьмите один из кругов с наибольшим удалением от центра (один касаясь граничного круга) и произвольно перемещайте его в другое место:
• Выберите набор циркуль, которые находятся близко друг к другу (например, если их центры лежат в случайно выбранном круге) и поверните их на случайный угол.
• Другим вариантом (хотя и немного сложнее) было бы измерение площади между кругами, когда они плотно упакованы:

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

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

Ответ 3

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

Ответ 4

Звучит как проблема упаковки кругов, вот некоторая информация:

• Кругная упаковка Wolfram MathWorld
• Алгоритмы упаковки круга Google Scholar
• Программное обеспечение CirclePack

Ответ 5

http://en.wikipedia.org/wiki/Apollonian_gasket

Это похоже на то, что вы пытаетесь сделать, и может предоставить вам некоторые потенциальные ограничения.

Ответ 6

Вы можете попробовать использовать библиотеку физики 2d и просто налить свои круги 2d в более крупный круглый контейнер - и дождаться их установки на место.