如何在python中包装球体？

Question

我正在尝试使用python在正方形中对随机封闭的包装球进行建模.球体不应重叠, 但我不知道如何做到这一点

我到目前为止:

码:

import random, math, pylab

def show_conf(L, sigma, title, fname):
    pylab.axes()
    for [x, y] in L:
        for ix in range(-1, 2):
            for iy in range(-1, 2):
                cir = pylab.Circle((x + ix, y + iy), radius=sigma,  fc='r')
                pylab.gca().add_patch(cir)
    pylab.axis('scaled')
    pylab.xlabel('eixo x')
    pylab.ylabel('eixo y')
    pylab.title(title)
    pylab.axis([0.0, 1.0, 0.0, 1.0])
    pylab.savefig(fname)
    pylab.close()

L = []
N = 8 ** 2

for i in range(N):
    posx = float(random.uniform(0, 1))
    posy = float(random.uniform(0, 1))
    L.append([posx, posy])

print L

N = 8 ** 2
eta = 0.3
sigma = math.sqrt(eta / (N * math.pi))
Q = 20
ltilde = 5*sigma

N_sqrt = int(math.sqrt(N) + 0.5)


titulo1 = '$N=$'+str(N)+', $\eta =$'+str(eta)
nome1 = 'inicial'+'_N_'+str(N) + '_eta_'+str(eta) + '.png'
show_conf(L, sigma, titulo1, nome1)

Answer 1

这是一个非常难的问题(可能是np-hard).应该有很多资源可用.

在我提出一些更一般的方法之前,请查看这个维基百科网站,了解当前最知名的一些N(一个正方形中的N个圆圈)的包装模式.

你很幸运,python中存在一个圆形包装实现(启发式!),它基于现代优化理论(凸函数 + 凹凸过程的差异).

• 这里描述了使用的方法(学术论文和软件链接; 2016年!)
• 使用的软件包在这里
  • 有一个示例目录circle_packing.py(下面与输出一起发布)
• 以下示例也适用于不同形状的圆

以上软件包为例(Xinyue Shen的例子)

__author__ = 'Xinyue'
from cvxpy import *
import numpy as np
import matplotlib.pyplot as plt
import dccp

n = 10
r = np.linspace(1,5,n)

c = Variable(n,2)
constr = []
for i in range(n-1):
    for j in range(i+1,n):
        constr.append(norm(c[i,:]-c[j,:])>=r[i]+r[j])
prob = Problem(Minimize(max_entries(max_entries(abs(c),axis=1)+r)), constr)
#prob = Problem(Minimize(max_entries(normInf(c,axis=1)+r)), constr)
prob.solve(method = 'dccp', ccp_times = 1)

l = max_entries(max_entries(abs(c),axis=1)+r).value*2
pi = np.pi
ratio = pi*sum_entries(square(r)).value/square(l).value
print "ratio =", ratio
print prob.status

# plot
plt.figure(figsize=(5,5))
circ = np.linspace(0,2*pi)
x_border = [-l/2, l/2, l/2, -l/2, -l/2]
y_border = [-l/2, -l/2, l/2, l/2, -l/2]
for i in xrange(n):
    plt.plot(c[i,0].value+r[i]*np.cos(circ),c[i,1].value+r[i]*np.sin(circ),'b')
plt.plot(x_border,y_border,'g')
plt.axes().set_aspect('equal')
plt.xlim([-l/2,l/2])
plt.ylim([-l/2,l/2])
plt.show()

产量

修改任务:大小相等的圆圈

只需更换:

r = np.linspace(1,5,n)

附:

r = [1 for i in range(n)]

产量

有趣的例子有64个圆圈(这需要一些时间!)