pythonlinear-programmingcircle-pack

Remove Overlapping Circles by Keeping Only Largest


Given a set of circles with random centers and radii, I would like to be able to prune this set so that if overlap between circles occurs, only the largest circle is retained. This is a similar question to the one answered here, but the problem listed there seeks to retain the maximum number of non-overlapping circles, from what I understand. I'd like to be able to adapt the ILP solution given there to my needs, if possible, although a brute-force "search and remove"-type approach would be fine too. The latter is what I've tried so far, but failed to accomplish.

import matplotlib.pyplot as plt
from numpy.random import rand, seed

seed(1)

N = 25 # number of circles
L = 10 # domain size

Rmin = 0.5 # min radius
Rmax = 1 # max radius

cx = rand(N)*(L-2*Rmax) + Rmax
cy = rand(N)*(L-2*Rmax) + Rmax
r  = rand(N)*(Rmax-Rmin) + Rmin

# Plotting
for i in range(N): 
  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()

enter image description here

Desired Result:

enter image description here


Solution

  • It got a bit messy, but this creates the Output you wanted.

    import matplotlib.pyplot as plt
    from numpy.random import rand, seed
    import math
    import numpy as np
    import pandas as pd
    
    def find_larger(df_circles_2, idx):
        found_greater = False
        for i,row in df_circles_2.iterrows():
            if i != idx:
                distance = math.sqrt( (row['x'] - df_circles_2['x'][idx])**2 + (row['y'] - df_circles_2['y'][idx])**2  )
                if distance < (row['r'] + df_circles_2['r'][i]):             
                    if row['r'] > df_circles_2['r'][idx] and (row['keep'] != "discard"):
                        if df_circles['keep'][i] == "keep":
                            return "discard"
                        found_greater = True
        if found_greater:
            return "undecided"
        else:            
            return "keep"
                        
    
    seed(1)
    
    N = 25 # number of circles
    L = 10 # domain size
    
    Rmin = 0.5 # min radius
    Rmax = 1 # max radius
    
    cx = rand(N)*(L-2*Rmax) + Rmax
    cy = rand(N)*(L-2*Rmax) + Rmax
    r  = rand(N)*(Rmax-Rmin) + Rmin
    
    # Plotting
    for i in range(N): 
      plt.gca().add_artist(plt.Circle((cx[i], cy[i]), r[i], ec='black', fc='white'))
      plt.gca().add_artist(plt.Text(cx[i], cy[i], text = str(i)))
    plt.axis('image')
    plt.xlim(0,L)
    plt.ylim(0,L)
    plt.show()
    
    # Searching:
    df_circles = pd.DataFrame(np.array([cx, cy, r]).T, columns = ['x', 'y', 'r'])
    df_circles['keep'] = "undecided"
    
    while(df_circles['keep'].str.contains('undecided').any()):
        for i, row in df_circles.iterrows():
            if row['keep'] == "undecided":
                df_circles.at[i, 'keep'] = find_larger(df_circles, i)
        
    
    # Plotting 2
    plt.figure(2)
    for i in range(N): 
      if df_circles['keep'][i] == "keep":
          plt.gca().add_artist(plt.Circle((cx[i], cy[i]), r[i], ec='black', fc='black'))
      else:
          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()