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

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

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

1. Я прошу «маленький», потому что «минимальный» радиус превращает его в гораздо более сложную задачу (минимальная версия уже доказала, что она NP трудная / полная - см. Сноску в конце вопроса). Нам не нужен минимум. Если форма, образованная кругами, кажется довольно круглой, этого достаточно.
2. Вы можете предположить, что Rmax / Rmin <20, если это поможет.
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 ....

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

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

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

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

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