删除最小数量的重叠圆？

debugcn 发表于 Dev

和

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

问题插图：

我想删除重叠的圆圈，但要保持最大的效果。对于上述问题，结果应为：

我试图通过创建每个圆的组合来进行硬编码，然后计算相交和不相交的数量。但是，这花费了太长时间。有没有针对这种问题的快速解决方案？

罗曼F

请尝试这样做，它应该可以工作；）您需要安装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))

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。