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

Question

Учитывая n окружностей с радиусами r1 ... rn, расположите их так, чтобы ни одна окружность не перекрывалась, а ограничивающая окружность имела «маленький» радиус.

Программа принимает список [r1,r2, ... rn] в качестве входа и выхода центров окружностей.

1. Я прошу "маленький", потому что "минимальный" радиус превращает его в гораздо более сложную проблему (минимальная версия ужебыло доказано, что NP трудный / полный - см. сноску в конце вопроса).Нам не нужен минимум.Если форма, сделанная из кружков, кажется достаточно круглой, это достаточно хорошо.
2. Можно предположить, что Rmax / Rmin <20, если это поможет. </li>
3. Задача с низким приоритетом - программадолжен уметь обрабатывать более 2000 кругов.Для начала, даже 100-200 кругов должны быть в порядке.
4. Возможно, вы уже догадались, что круги не должны быть плотно упакованы или даже касаться друг друга.

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

Вы можете использовать приведенный ниже код Python в качестве отправной точки (для этого кода вам понадобятся numpy и matplotlib - "sudo apt-get install numpy matplotlib" в linux) ...

import pylab
from matplotlib.patches import Circle
from random import gauss, randint
from colorsys import hsv_to_rgb

def plotCircles(circles):
    # input is list of circles
    # each circle is a tuple of the form (x, y, r)
    ax = pylab.figure()
    bx = pylab.gca()
    rs = [x[2] for x in circles]
    maxr = max(rs)
    minr = min(rs)
    hue = lambda inc: pow(float(inc - minr)/(1.02*(maxr - minr)), 3)

    for circle in circles:
        circ = Circle((circle[0], circle[1]), circle[2])
        color = hsv_to_rgb(hue(circle[2]), 1, 1)
        circ.set_color(color)
        circ.set_edgecolor(color)
        bx.add_patch(circ)
    pylab.axis('scaled')
    pylab.show()

def positionCircles(rn):
    # You need rewrite this function
    # As of now, this is a dummy function
    # which positions the circles randomly
    maxr = int(max(rn)/2)
    numc = len(rn)
    scale = int(pow(numc, 0.5))
    maxr = scale*maxr

    circles = [(randint(-maxr, maxr), randint(-maxr, maxr), r)
               for r in rn]
    return circles

if __name__ == '__main__':
    minrad, maxrad = (3, 5)
    numCircles = 400

    rn = [((maxrad-minrad)*gauss(0,1) + minrad) for x in range(numCircles)]

    circles = positionCircles(rn)
    plotCircles(circles)

---

Добавлена ​​информация: Алгоритм упаковки кругов, обычно упоминаемый в результатах поиска Google, не применим к этой проблеме.

Постановка задачи другого "Упаковка кругов"Алгоритм "таким образом: учитывая комплекс K (графы в этом контексте называются симплициальные комплексы, или комплекс вкратце) и соответствующие граничные условия, вычислить радиусы соответствующей упаковки окружности для K ....

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

Другая проблема имеет интересное наблюдение (независимо от этой проблемы):

Теорема об упаковке кругов - Каждая упаковка кругов имеет соответствующий плоский граф (это простая / очевидная часть), и каждый плоский граф имеет соответствующую упаковку кругов (не очень очевидная часть).Графики и упаковки двойственны друг другу и уникальны.

У нас нет плоского графа или тангенциального отношения, с которого можно начать в нашей задаче.

Эта статья - Robert JФаулер, Майк Патерсон, Стивен Л. Танимото: Оптимальная упаковка и покрытие на плоскости являются NP-полными - доказывает, что минимальная версия этой задачи NP-полна.Тем не менее, бумага не доступна онлайн (по крайней мере, не легко).

Answer 1

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

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

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

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

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

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

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

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

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

Answer 2

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

Похоже, они пересекаются в центре, но это не так. Я украсил функцию размещения вложенным циклом, который проверяет каждый круг против каждого второго круга (дважды) и поднимает 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

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

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

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

Answer 3

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

Answer 4

Похоже на проблему с круговой упаковкой, вот некоторая информация:

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

Answer 5

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

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

Answer 6

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