Search code examples
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()