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

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

Я прошу «маленький», потому что «минимальный» радиус превращает его в гораздо более сложную задачу (минимальная версия уже доказала, что она сложная / полная NP - см. Сноску в конце вопроса). Нам не нужен минимум. Если форма, сделанная кругами, кажется довольно круглой, это достаточно хорошо.Вы можете предположить, что Rmax / Rmin <20, если это помогает.Проблема с низким приоритетом - программа должна обрабатывать более 2000 кругов. Для начала, даже 100-200 кругов должно быть хорошо.Вы могли догадаться, что круги не должны быть плотно упакованы или даже касаться друг друга.

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

Вы можете использовать приведенный ниже код 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 f,orm (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-Complete - доказывает, что минимальная версия этой задачи является NP-полной. Тем не менее, бумага не доступна онлайн (по крайней мере, не легко).