algorithm - mide - diametro y radio

Posiciona N círculos de diferentes radios dentro de un círculo más grande sin superposición

Question

Dado n círculos con radios r1 ... rn, ubíquelos de tal manera que no haya círculos superpuestos y el círculo delimitador sea de radio "pequeño".

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

1. Solicito "pequeño" porque el radio "mínimo" lo convierte en un problema mucho más difícil (la versión mínima ya ha demostrado ser NP dura / completa; consulte la nota al pie de página 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.
2. Puede suponer que Rmax / Rmin <20 si ayuda.
3. Una preocupación de baja prioridad: el programa debe ser capaz de manejar más de 2000 círculos. Para empezar, incluso 100-200 círculos deberían estar bien.
4. Es posible que haya adivinado que no es necesario que los círculos estén empacados juntos o incluso que se toquen entre sí.

El objetivo es llegar a un arreglo visualmente agradable de los círculos dados que puedan caber dentro de un círculo más grande y no dejar demasiado espacio vacío. (como los círculos en una imagen de prueba de ceguera de color ).

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

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

La declaración del problema del otro "algoritmo de empaquetamiento circular" es, por lo tanto: dada una K compleja (las gráficas en este contexto se denominan complejos de simplicidad, o complejo en breve) y las condiciones de contorno apropiadas, calculan los radios del empaquetado 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 indican contacto / relación tangencial entre círculos). Uno tiene que encontrar el radio del círculo y las posiciones 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 empaquetamiento de círculos: cada empaquetamiento de círculos tiene un gráfico planar correspondiente (esta es la parte fácil / obvia), y cada gráfico planar tiene un empaquetado de círculos correspondiente (la parte no tan obvia). Los gráficos y las empaquetaduras son duales entre sí y son únicos.

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

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

Answer 1

¿Puede tratar los círculos como partículas cargadas en una cavidad cargada y buscar una solución estable? Es decir, los círculos se repelen entre sí según la proximidad, pero son atraídos hacia el origen. Unos pocos pasos de simulación pueden darte una respuesta decente.

Answer 2

No es una solución, solo una idea de intercambio de ideas: IIRC una forma común de obtener soluciones aproximadas para el TSP es comenzar con una configuración aleatoria, y luego aplicar operaciones locales (por ejemplo, "intercambiar" dos bordes en el camino) para intentar acortarlo y caminos más cortos ( Enlace de Wikipedia )

Creo que algo similar sería posible aquí:

1. Comenzar con posiciones centrales aleatorias
2. "Optimice" estas posiciones, para que no haya círculos superpuestos y, por lo tanto, los círculos estén lo más cerca posible, aumentando la distancia entre círculos superpuestos y reduciendo la distancia entre otros círculos, hasta que estén apretados. Esto podría hacerse mediante algún tipo de minimización de energía, o podría haber una solución codiciosa más eficiente.
3. Aplicar un operador de mejora iterativo a las posiciones centrales.
4. Ir a 2, romper después de un número máximo de iteraciones o si la última iteración no encontró ninguna mejora

La pregunta interesante es: ¿qué tipo de "operador de mejora iterativa" podría usar en el paso 3? Podemos suponer que las posiciones en esa etapa son óptimas a nivel local , pero podrían mejorarse reorganizando una gran parte de los círculos. Mi sugerencia sería elegir arbitrariamente una línea a través de los círculos. Luego tome todos los círculos "a la izquierda" de la línea y espérelos en algún eje perpendicular a esa línea: Probablemente probaría varias líneas y escogiera la que lleve a la solución más compacta.

La idea es que, si algunos de los círculos ya están en o cerca de su configuración óptima, es probable que esta operación no los moleste.

Otras posibles operaciones que podría pensar:

• Tome uno de los círculos con la distancia más alta desde el centro (uno tocando el círculo del límite), y muévalo al azar a otro lugar:
• Elija un conjunto de círculos que estén cerca uno del otro (por ejemplo, si sus centros se encuentran en un círculo elegido al azar) y gírelos en un ángulo aleatorio.
• Otra opción (aunque un poco más compleja) sería medir el área entre los círculos, cuando están apretados:

Luego, puede elegir uno de los círculos adyacentes al área entre círculos más grande (el área roja, en la imagen) y cambiarlo por otro círculo, o moverlo a algún lugar hasta el límite.

(Respuesta al comentario :) Tenga en cuenta que cada una de estas "mejoras" está casi garantizada para crear superposiciones y / o espacio innecesario entre círculos. Pero en la siguiente iteración, el paso 2 moverá los círculos para que estén bien empaquetados y no se superpongan de nuevo. De esta manera, puedo tener un paso para las optimizaciones locales (sin preocuparme por las globales) y otro para las optimizaciones globales (que podrían crear soluciones localmente subóptimas). Esto es mucho más fácil que tener un paso complejo que hace ambas cosas.

Answer 3

Puede intentar usar una biblioteca de física 2d y simplemente verter sus círculos 2d en un contenedor circular más grande, y esperar a que se acomoden en su lugar.

Answer 4

Suena como un problema de Circle Packing, aquí hay algo de información:

• Empaquetado Círculo Wolfram MathWorld
• Circle Packing Algorithms Google Académico
• Software CirclePack

Answer 5

Tengo una solution bastante ingenua de una pasada (sobre los radios) que produce buenos resultados, aunque definitivamente hay margen de mejora. Tengo algunas ideas en esa dirección, pero creo que también podría compartir lo que tengo en caso de que alguien más quiera piratearlo también.

Parece que se cruzan en el centro, pero no lo hacen. Decoré la función de colocación con un bucle anidado que verifica cada círculo contra cada otro círculo (dos veces) y levanta un AssertionError si hay una intersección.

Además, puedo obtener el borde casi perfecto simplemente invirtiendo la clasificación de la lista, pero no creo que el centro se vea bien de esa manera. Es (prácticamente lo único) discutido en los comentarios al código.

La idea es mirar solo los puntos discretos en los que podría vivir un círculo e iterar sobre ellos usando el siguiente generador:

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

Esto simplemente comienza en el origen y traza puntos a lo largo de círculos concéntricos alrededor de él. Procesamos los radios ordenándolos de acuerdo con algunos parámetros para mantener los círculos grandes cerca del centro (principio de la lista) pero suficientes pequeños cerca del principio para llenar los espacios. Luego iteramos sobre los radios. dentro del bucle principal, primero hacemos un bucle sobre los puntos que ya hemos visto y guardado. Si ninguno de ellos es adecuado, comenzamos a extraer nuevos puntos del generador y los guardamos (en orden) hasta que encontremos un lugar adecuado. Luego colocamos el círculo y repasamos nuestra lista de puntos guardados sacando todos los que caen dentro del nuevo círculo. Entonces repetimos. en el siguiente radio.

Pondré algunas ideas que tengo en juego y las pondré en orden. Esto podría servir como un buen primer paso para una idea basada en la física, ya que puede comenzar sin superposiciones. Por supuesto, puede que ya esté lo suficientemente ajustado para que no tengas mucho espacio.

Además, nunca he jugado con numpy o matplotlib, así que escribo solo vainilla python. Puede que haya algo allí que lo haga correr mucho más rápido, tendré que mirar.

Answer 6

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

Esto parece algo relevante para lo que está tratando de hacer y puede proporcionarle algunas restricciones potenciales.