通过仅保留最大的圆来移除重叠的圆

Question

给定一组具有随机中心和半径的圆，我希望能够修剪这组圆，这样如果圆之间发生重叠，则只保留最大的圆。这是一个与回答的问题类似的问题，但据我了解，那里列出的问题旨在保留最大数量的非重叠圆圈。如果可能的话，我希望能够根据我的需要调整那里提供的 ILP 解决方案，尽管蛮力“搜索和删除”类型的方法也可以。后者是我迄今为止尝试过的，但未能完成。

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()

想要的结果：

Answer 1

它有点乱，但这会创建您想要的输出。

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()

通过仅保留最大的圆来移除重叠的圆

Remove Overlapping Circles by Keeping Only Largest

python

linear-programming

circle-pack