Geben Sie n Kreise mit den Radien r1 ... rn an und positionieren Sie sie so, dass sich keine Kreise überlappen und der Begrenzungskreis einen "kleinen" Radius hat.

Das Programm nimmt eine Liste [r1, r2, ... rn] als Eingabe und gibt die Zentren der Kreise aus.

Ich bitte um "klein", weil "minimaler" Radius es in ein viel schwierigeres Problem umwandelt (minimale Version hat sich bereits als NP hart / vollständig erwiesen - siehe Fußnote am Ende der Frage). Wir brauchen nicht das Minimum. Wenn die Form der Kreise ziemlich kreisförmig zu sein scheint, ist das gut genug.Sie können davon ausgehen, dass Rmax / Rmin <20 ist, wenn es hilft.Ein Problem mit niedriger Priorität - das Programm sollte in der Lage sein, über 2000 Kreise zu bearbeiten. Zu Beginn sollten sogar 100-200 Kreise in Ordnung sein.Sie haben vielleicht vermutet, dass die Kreise nicht dicht gepackt sein müssen oder sich sogar berühren müssen.

Ziel ist es, eine optisch ansprechende Anordnung der vorgegebenen Kreise zu finden, die in einen größeren Kreis passt und nicht zu viel Freiraum lässt. (wie die Kreise in einem Farbenblindheitstest Bild).

Sie können den folgenden Python-Code als Ausgangspunkt verwenden (für diesen Code benötigen Sie numpy und matplotlib - "sudo apt-get install numpy matplotlib" unter 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)

Info hinzugefügt: Der in Google-Suchergebnissen häufig verwendete Algorithmus zum Packen von Kreisen ist auf dieses Problem nicht anwendbar.

ie Problemstellung des anderen "Kreispackungsalgorithmus" lautet also: Berechnen Sie bei einem komplexen K (Graphen heißen in diesem Zusammenhang simpliziale Komplexe oder kurz komplex) und geeigneten Randbedingungen die Radien der entsprechenden Kreispackung für K. ...

Es beginnt im Wesentlichen mit einem Diagramm, das angibt, welche Kreise sich berühren (Scheitelpunkte des Diagramms bezeichnen Kreise, und die Kanten bezeichnen die Berührungs- / Tangentialbeziehung zwischen Kreisen). Man muss die Kreisradien und -positionen finden, um die durch den Graphen angegebene Berührungsbeziehung zu erfülle

Das andere Problem hat eine interessante Beobachtung (unabhängig von diesem Problem):

Circle Packing Theorem - Jede Kreispackung hat ein entsprechendes ebenes Diagramm (dies ist der einfache / offensichtliche Teil), und jede ebene Grafik hat ein entsprechendes Kreispackung (der nicht so offensichtliche Teil). Die Grafiken und Packungen sind doppelt und einzigartig.

Wir haben in unserem Problem keinen planaren Graphen oder keine tangentiale Beziehung.

Dieses Papier - Robert J. Fowler, Mike Paterson, Steven L. Tanimoto: Optimale Verpackung und Abdeckung im Flugzeug sind NP-Complete - beweist, dass die Mindestversion dieses Problems NP-vollständig ist. Das Papier ist jedoch nicht online verfügbar (zumindest nicht leicht).