Eliminar superposición de círculos manteniendo sólo el más grande

Answer

1. 

   davy.ai

   July 19, 2023 at 1:10 pm

   Solución para podar círculos superpuestos

   El problema en cuestión consiste en podar un conjunto de círculos y retener solo aquellos que no se superponen. El enfoque que sugiero es similar al sugerido en esta respuesta, pero con algunas modificaciones en la PLI.

   Formulación de la PLI

   Podemos modelar el problema como una PLI con una variable de decisión binaria x_i para cada círculo i en el conjunto. La variable toma el valor 1 si se retiene el círculo i y 0 en caso contrario.

   Función Objetivo

   La función objetivo de la PLI es maximizar el área total de los círculos que se retienen. Esto se puede expresar como:

   maximizar sum(x[i] * pi * r[i]^2)
   

   donde r[i] es el radio del círculo i.

   Restricciones

   El problema tiene dos tipos de restricciones: restricciones de superposición y restricciones binarias.

   Restricciones de Superposición

   Para cada par de círculos (i, j), debemos asegurarnos de que no se superpongan. Esto se puede expresar como:

   (x[i] + x[j]) * (2 * r[i] + 2 * r[j]) <= d[i,j]
   

   donde d[i,j] es la distancia entre los centros de los círculos i y j.

   Restricciones Binarias

   Las restricciones binarias garantizan que la variable de decisión tome solo valores binarios (0 o 1). Esto se puede expresar como:

   x[i] ∈ {0,1}, para todo i en [1..N]
   

   Implementación de la PLI

   Podemos utilizar la biblioteca PuLP en Python para implementar la PLI. Aquí está el código modificado:

   !pip install pulp
   
   import pulp
   
   prob = pulp.LpProblem("Círculos No Superpuestos", pulp.LpMaximize)
   
   # variables de decisión
   N = 25
   x = pulp.LpVariable.dicts("x", range(N), cat=pulp.LpBinary)
   
   # radio y coordenadas del centro de los círculos
   Rmin = 0.5
   Rmax = 1
   cx = rand(N)*(L-2*Rmax) + Rmax
   cy = rand(N)*(L-2*Rmax) + Rmax
   r  = rand(N)*(Rmax-Rmin) + Rmin
   
   # función objetivo
   ganancia = sum([pulp.lpSum([x[i] * pulp.lpSum([r[i]**2 * pulp.LpVariable("pi", cat=pulp.LpBinary)])])])
   prob += ganancia
   
   # restricciones
   for i in range(N):
       for j in range(i+1, N):
           dist = ((cx[i]-cx[j])**2 + (cy[i]-cy[j])**2)**0.5
           prob += (x[i] + x[j]) * (2 * r[i] + 2 * r[j]) <= dist, f"Restricción de Superposición ({i},{j})"
   
   # resolver el problema
   prob.solve()
   
   # graficar la solución
   for i in range(N):
       if x[i].value() == 1:
           plt.gca().add_artist(plt.Circle((cx[i], cy[i]), r[i], ec='black', fc='white'))
   
   plt.axis('image')
   plt.xlim(0,L)
   plt.ylim(0,L)
   plt.show()
   

   El código primero define las variables de decisión, que son variables binarias x_i para cada círculo i. Luego, establece la función objetivo, que es maximizar el área total de los círculos que se retienen. A continuación, se agregan las restricciones: recorremos cada par de círculos y agregamos una restricción de superposición si se intersectan. Finalmente, resolvemos el problema usando prob.solve() y graficamos la solución.

   La salida debería lucir como el resultado deseado:

   

Comments are closed.