删除最少量的重叠圆圈？

Question

有什么方法可以删除最小重叠圆圈以获得最大不重叠圆圈？

问题说明：

我想删除重叠的圆圈，但保留结果最大值。对于上面的问题，结果应该是这样的：

我试图通过创建每个圆组合然后计算相交和不相交的数量来对其进行硬编码。然而，这需要太长时间。有什么快速解决此类问题的方法吗？

Answer 1

请试一下，它应该可以工作；) 您需要安装 pulp。脚本分为3个部分：

问题的参数化
随机生成圆（我制作了随机半径，但如果需要你可以使用固定半径）
pulp

from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable
import numpy as np
import matplotlib.pyplot as plt
from numpy.random import rand

#%% PARAMETRIZE the PROBLEM
N = 10 # number of circles
X = 15 # size on X
Y = 15 # size on Y

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

#%% GENERATE RANDOM CIRCLES

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

plt.figure(1)
plt.clf()
for i in range(N): plt.gca().add_artist(plt.Circle((cx[i], cy[i]), r[i], alpha=0.7))
plt.axis('image')
plt.xlim(0,X)
plt.ylim(0,Y)


#%% GET SOLUTION
model = LpProblem(name="small-problem", sense=LpMaximize)
var = [LpVariable(name="x%u"%i, lowBound=0,upBound=1,cat='Integer') for i in range(N)]

# Add objective function to model
model += lpSum(var)

# Add constraints
for i in range(N):
    for j in range(i+1,N):
        dij = np.sqrt((cx[i]-cx[j])**2 + (cy[i]-cy[j])**2)
        if dij < (r[i]+r[j]):
            model += (var[i]+var[j]<=1,"intersec %u - %u"%(i,j))


# Solve it
status = model.solve()
print(f"status: {model.status}, {LpStatus[model.status]}")
print(f"objective: {model.objective.value()}")
for v in model.variables():
    print(f"{v.name}: {v.value()}")
    if v.value():
        i = int(v.name[1])
        plt.gca().add_artist(plt.Circle((cx[i], cy[i]), r[i],fc='none',ec='C1',lw=2))

删除最少量的重叠圆圈？

Delete minimum amount of overlapping circle?

python

circle-pack