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()
Desired Result:
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()