Dados n círculos con radios r1 ... rn, colóquelos de tal manera que no se superpongan círculos y el círculo delimitador sea de radio "pequeño".

El programa toma una lista [r1, r2, ... rn] como entrada y da salida a los centros de los círculos.

Pido "pequeño" porque el radio "mínimo" lo convierte en un problema mucho más difícil (ya se ha demostrado que la versión mínima es NP difícil / completa - ver nota al pie cerca del final de la pregunta). No necesitamos el mínimo. Si la forma hecha por los círculos parece ser bastante circular, eso es lo suficientemente bueno.Puede suponer que Rmax / Rmin <20 si ayuda.Una preocupación de baja prioridad: el programa debería ser capaz de manejar más de 2000 círculos. Para empezar, incluso 100-200 círculos deberían estar bien.Es posible que hayas adivinado que los círculos no necesitan estar apretados o incluso tocarse entre sí.

El objetivo es llegar a una disposición visualmente agradable de los círculos dados que pueda caber dentro de un círculo más grande y no dejar demasiado espacio vacío. (como los círculos en unimagen de prueba de daltonismo)

Puede usar el siguiente código de Python como punto de partida (necesitaría numpy y matplotlib para este código: "sudo apt-get install numpy matplotlib" en 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)

Información adicional: el algoritmo de empaque circular conocido comúnmente en los resultados de búsqueda de Google no es aplicable a este problema.

El enunciado del problema del otro "algoritmo de empaquetamiento circular" es así: dado un complejo K (los gráficos en este contexto se denominan complejos simpliciales, o complejo en resumen) y las condiciones de contorno apropiadas, calcule los radios del empaque circular correspondiente para K .. ..

Básicamente comienza a partir de un gráfico que indica qué círculos se tocan entre sí (los vértices del gráfico denotan círculos y los bordes denotan la relación táctil / tangencial entre los círculos). Uno tiene que encontrar los radios y las posiciones del círculo para satisfacer la relación conmovedora indicada por el gráfico.

El otro problema tiene una observación interesante (independiente de este problema):

Teorema de embalaje circular - Cada empaque circular tiene un gráfico plano correspondiente (esta es la parte fácil / obvia), y cada gráfico plano tiene un empaque circular correspondiente (la parte no tan obvia). Los gráficos y los empaques son duales entre sí y son únicos.

No tenemos un gráfico plano o una relación tangencial para comenzar en nuestro problema.

Este papel -Robert J. Fowler, Mike Paterson, Steven L. Tanimoto: el embalaje y la cobertura óptimos en el avión son NP-completos - prueba que la versión mínima de este problema es NP-complete. Sin embargo, el documento no está disponible en línea (al menos no fácilmente).